前言

数组是一种最基本的数据结构，它占据一块连续的内存，并按照顺序存储的方式存储数据。
为了解决数组空间效率不高的问题，动态数组出现了，典型的代表是 vector。思想是先为动态数组预先分配一块内存空间，等到数组容量不足时重新开辟一块内存空间，并复制原数组到新空间，最后释放旧内存空间。对于Vector 来说，每次扩容为之前的 2 倍。由于该操作对时间性能影响较大，因此使用动态数组应该尽量避免改变数组容量大小的次数。

数组和指针的区别

• 使用指针访问数组中的元素时，需要确保不越界；
• 对数组求 sizeof ，还需要考虑元素所占的字节，比如在 32 位的机器上，每个整数占4字节，那么例子中 data1 就是 5*4=20；
• 在 32 位系统上，对任意类型的指针求 sizeof 得到的结果都是 4；
• 当数组作为函数的参数进行传递时，自动退化为指针，因此求 sizeof 结果同上条。

题目描述(数组中重复的数字)

题目一(找出数组中重复的数字)

在一个长度 n 的数组里的所有数字都在 0-n-1 的范围内。数组中的某些数字是重复的，但不知道有几个数字重复了，也不知道每个数组重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组｛2，3，1，0，2，5，3｝，那么对应的输出是重复的数字 2 或者 3。

解题思路

1. 排序。对数组排序后，依次比较前后元素是否重复即可。但时间复杂度为O(nlogn),空间复杂度为 O(1)。
2. 利用哈希表。利用键值对映射，可以将数组中的元素依次插入插入哈希表中，但是插入之前需要判断是否已存在该值，如果存在则说明该位置的元素重复了，算法的缺点是空间复杂度为 O(n)。
3. 下标定位法。

接下来详细介绍下下标定位法。
注意到题目中数字的范围都在 0-n-1 范围内，假如不存在重复的元素，那么对数组进行重新排序后，数组的索引 i 一定可以对应到单个数字i,否则数字i存在多个。

我们先依次遍历数组中的每个元素，当扫描到索引为 i 的数字 m 时，先比较数字 m 是否等于 i，如果等于则接着扫描下一个数组元素；如果不等，则将数字 m 和数组中索引为 m 的数字 n 进行比较，如果重复(m=n)，则找到了一个重复的数字；如果不重复(m!=n)，那么交换 m 与 n。交换后，此时索引 i 上的数字 m 再和索引 i 进行下一轮的比较，重复上面的步骤，直至数字 m 与索引 i 相同。那么我们就在这个比较交换的过程中寻找重复的元素。

算法实现

复杂度分析

代码中虽有两次循环，但每个数字最多只要交换两次就能找到属于它子集的位置，因此总的时间复杂度为 O(n)。另外，所有操作都在原数组上进行，所以空间复杂度为 O(1)。

题目二 (不修改数组找出重复的元素)

在一个长度为 n+1 的数组里的所有数字都在 1-n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 {2,3,5,4,3,2,6,7},
那么对应的输出是重复的数字 2 或者 3。

解题思路

1. 辅助数组法。依然是按一个下标对应一个数字的思路，先构建一个长度为 n+1 的数组，然后将原数组中的元素依次插入到辅助数组中相应的下标位置上。这样就能发现那个数字重复了。方法的缺点就是空间复杂度为 O(n)。
2. 二分查找法。若 1-n 的范围里只有 n 个数字则一定不会重复，否则必定存在重复的元素。那现在我们把 1-n 的数字从中间的数字 m 分为两部分，那么前一半为 1-m，后一半为 m+1-n，假如前半部分中介于 1-m 中的数字个数超过了 m，那么这一半的区间必定存在重复的元素。接下来可以继续在这一半空间的二分查找，直至找到重复的元素。

算法实现

复杂度分析

算法中使用二分查找的思想，复杂度 O(logn),在计数的时候使用了一个循环复杂度为 O(n),因此，总的时间复杂度为 O(nlogn),操作在原数组上进行，时间复杂度为 O(1)。

参考

<<剑指offer第二版>>

前言

k-近邻学习(kNN)是一种监督学习的方法。它采用测量不同特征值之间的距离方法(如欧式距离)来进行分类。它也是懒惰学习(lazy learning)的著名代表，即它不在训练阶段学习，而是在测试阶段计算后连同给出分类结果。

算法原理

我们都知道，kNN 的训练样本都是有分类标签的。那么，当给定一个测试样本时，我们可以根据某种衡量距离的计算方法来比较测试样本对应的特征向量与每个训练样本对应的特征向量之间的距离。但是，一般我们只取 k 个 与测试样本距离最近的训练样本来比较(一般 k 是不大于20的整数)。

在分类问题中，测试样本的分类结果取决于这 k个训练样本中出现最多的那个标签。而在回归问题中，测试的分类结果可取决于这 k 个训练样本的标签值的平均值。另外，还可以根据距离的远近进行加权平均或加权投票。

算法名称中 k 表示我们只选取与测试样本最相似的 k 个训练样本。

接下来，我以 kNN 分类器为例，利用 python 实现其算法思想。

python实现

首先，若选择欧式距离衡量两个向量点xA和xB之间的距离,则其公式如下:

$$\cdot \\ d=\sqrt {\left( xA_{0}-xB_{0}\right) ^{2}+\left( xA_{1}-xB_{1}\right) ^{2}}$$

接下来，定义函数 classify0()传入相应参数即可完成 kNN 分类。

参考

• <<机器学习>>周志华
• <<机器学习实战>>

题目描述(赋值运算符函数)

如下为类型 CMyString 的声明，请为该类型添加赋值运算符函数。

考察的关注点

• 返回值的类型。是否把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用(*this)。只有返回一个引用，才可以允许连续赋值。否则，如果函数返回的类型是 Void,则该赋值运算符将不能连续赋值。比如 str1=str2=str3 ,这样的形式将不被允许。
• 传入的参数类型。是否把传入的参数声明为常量引用。如果传入的参数不是引用而是实例，那么从形参到实参会调用一次复制构造函数。把参数声明为引用可以避免这样的无谓消耗，提高代码的效率。同时，在赋值运算符函数内不会改变传入的实例的状态，因此还应该为传入的引用参数加上 const 关键字。
• 内存泄漏问题 。是否释放实例自身已有的内存。如果忘记在分配新内存之前释放掉自身已有的空间，则程序将会出现内存泄漏。
• 多情况考虑 。 判断传入的参数和当前的实例是不是同一个实例。如果是同一个，则不进行赋值操作,直接返回。如果事先不判断就进行赋值，那么在释放实例自身的时候就会导致严重的问题：当 *this 和传入的参数是同一个实例时，一旦释放了自身的内存，传入的参数的内存也同时被释放了，因此再也找不到需要赋值的内容了。

  经典解法

  

  考虑异常安全性的解法

  要想在赋值运算符函数中实现异常安全性，我们有两种方法。一种简单的办法是我们先用 new 分配新内容，再用 delete 释放已有的内容(考虑到可能内存不足，无法分配问题)。另一种方法是先创建已给临时实例，再交换临时实例和原来的实例。
  

程序主要利用了 C++ 的特性以及交换临时实例的方法来实现。关键的是 strTemp 是一个局部的变量，那么在方法执行完毕后，它是会自动调用析构函数而释放内存的，那么就不需要手动释放，而通过交换我们也能拿到要赋值的值。

考点

• 基础语法的理解，如运算符函数、常量引用等；
• 内存泄漏的理解；
• 代码异常安全性的考虑。

参考

<<剑指offer2>>

前言

在开启本文的内容介绍时，我们先来了解下什么是函数式编程。所谓的函数式编程其实是一种编程范式，用人话就是写代码所遵循的一种方法或模式。简单地说，当某个函数(可称高阶函数)可以接受函数对象当做输入参数和返回值，这样一种写法即函数式编程。那么本文的闭包则应用了函数式编程的思想，而装饰器可以说是闭包的应用之一。

闭包

作用域

作用域是程序运行时变量可被访问的范围，故有全局变量和局部变量之说。一般我们把定义在函数之外的变量称之为全局变量，其作用域为当前文件或者当前类下。而定义在函数体内的局部变量称之为局部变量。而在python中函数可以嵌套，因而作用域的范围也有了明显的层级关系。即作用域最外层>第一层函数>第二层函数>…第n层函数,有相对的访问限制。我们来看个例子。

什么是闭包

我们先从一个例子来看看。

这段代码最终的输出结果是python。按照一般的生命周期，变量name会随着function()的调用而移出内存。然而当你利用function()的返回函数wrapper再次调用时，仍旧返回了变量name的值，那也就说它并没有离开内存。这其实就是闭包的作用，它使得局部变量在函数外被访问成为可能。
而在Wiki)上，闭包的定义如下:在计算机科学中，闭包（英语：Closure），又称词法闭包（Lexical Closure）或函数闭包（function closures），是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在，即使已经离开了创造它的环境也不例外。所以，有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。

在定义中的关键信息就是自由变量和函数(具体所指见上图),简单地说，该自由变量和函数一同存在于一个封闭的环境即函数所在的作用域内，同生共死。

总之，闭包本质上是一个函数，它包括了自由变量和函数两大部分，闭包使得这些变量的值保存在内存中。

闭包中的难点

首先可以自己先想一下如果是你，你会给出什么样的答案?? 如果是 0,2,4,6 那么请往下看。

首先我们定义了一个函数 fun() 并且是以列表生成式的方式返回结果，并且列表中的元素是由匿名函数lambda定义的。
为什么答案都是 6 呢？其实这是由于闭包的后期绑定导致的late binding,意思就是说在闭包中的自由变量是在内部函数被调用时被查找的，而随着 for 循环的执行，i 的值已经被更新到了3，即在闭包的封闭环境中自由变量 i 每次被查找都是拿到3的结果,再乘以 2，自然每次结果只能都是 6 。
那如果不想得到这样的结果，如何改写？ 下面提供两种优雅的写法。

装饰器

简单的装饰器

decorator 就代表了一个装饰器，它用于给 log 函数增加额外的功能。实际的装饰过程定义在嵌套函数内部，在函数内部，log函数对象 以 func 参数来表示。那么这样一看就好像log被decorator 装饰了一样。

语法糖

在python,能在代码运行期间动态增加功能的方式即借助@符号。而这和Java 中的注解差不多一个意思。那么我们就可以用它来简化装饰器的调用过程。

如上所示，@语法自动帮我们调用了decorator(log),省去了一次手动调用的过程，现在只需要调用一次log(),即可得到装饰效果，可谓是便民操作。而且如果还有其他函数也想被该装饰器装饰，同样加上个@decorator即可。这样其实也有一种封装代码的思想在里面。

带参数的装饰器

装饰器本质上亦是函数，那么就会有传入参数的需求。比如根据level 级别做不同的装饰操作,如此依赖也提高了装饰器的扩展性。

如上所示，我们给装饰器函数user_logging设置了一个参数，这样当你指定不同的level 时，log 就会输出不同的结果。在此程序中调用log("hrx") 等价于调用wrapper=user_logging(decorator(log)) ,然后再调用wrapper("hrx")，这样其实比前述例子多了一层函数调用(因为多嵌套了一个函数)。

注：我们使用*arg,**kw作为 wrapper 函数的参数，这样设置之后表示此函数可以接受任意位置参数和关键字参数，这样一来 log 函数就可以指定各种各样的参数。

类装饰器

函数有装饰器，其实类也有装饰器，思想一样，但写法不太一样。其中实现装饰的步骤主要在类中的__call__ () 方法中进行。

装饰器的缺点

在以上例子中，装饰器的实质都是log=wrapper (表面调用的是log ，但实际上调用了wrapper 执行),所以如果此时输入log.__name__得到的将会是wrapper的名字。可以使用wrapper__name__=log__name__,或利用python 内置装饰器functiontools.wrap实现。wrap操作可以将原函数的元信息拷贝到装饰器函数中的func内。所以完整的装饰器函数还应该加上functiontools.wrap(func)。

总结

记住,python 中一切皆为对象,而函数算个特殊的对象吧。在闭包中，主要由函数对象与自由变量，加上其所处的封闭环境组成。再来，利用闭包，又得到了装饰器的用法，最后既扩展的函数的功能，又方便了代码的编写。

参考

Python装饰器和符号@
理解 Python 装饰器看这一篇就够了
闭包

前言

在面试编程的时候，代码的规范性和完整性非常重要，可能成为能否拿到 offer 的关键因素。那么代码的规范性如何体现呢？比如清晰的书写、代码布局清晰(如缩进，括号对齐)、变量和函数的命名易懂。而代码的完整性体现在代码基本功能实现的正确性以及在边界值、错误处理等方面的全面考虑。

那么完整的代码需要从功能测试、边界测试以及负面测试来提高鲁棒性。例如，在功能测试中，除了完成基本功能，还需要考虑数值的表示范围；在边界测试中，需要考虑循环条件和递归终止条件的正确性；在负面测试中，需要考虑边界值和特殊值的输入，以解决一些不合法的情况。

那么对于错误处理的方式主要有三种，分别是函数用返回值来告知API调用者是否出错，如返回 0 表示出错；当错误发生时设置一个全局变量来记录；对错误情况，采用抛异常的处理方式。

题目(数值的整数次方)

题目：实现函数 double Power(double base,int exponent)，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数范围。

算法思路

首先我们应该对输入参数的各种情况进行讨论。

1. 如果基 base 是 0 而且 指数 exponent 是负数，那么情况判为不合法输入；
2. 注意基 base 是 0 而且 指数 exponent 也是 0 ，这种情况在数学上是无意义的。
3. 无论指数 exponent 是正还是负都统一先转成无符号的整形类型，方便统一计算整数次方。然后，对于 exponent 为负的情况，只需将结果变为倒数即可。

优化多次乘方的思路：
如果输入的指数 exponent 为 32，那么需要进行 31 次乘法操作。那么，如果我们能先算出数字的 16 次方，然后再平方一次即可；那么假如知道了数字的 16 次方，那么只需要在数字的 16 次方的基础上平方一次即可得到结果，那如果知道了数字的 8 次方，那么就可以在数字的 8 次方基础上平方一次得到数字的 16 次方的结果；那么如果知道数字的 4 次方，就可以在数字 4 此方的基础上平方一次得到数字的 8 次方；一次类推，直到知道了数字的 1 次方。

那么可用如下公式表示 a 的 n 次方:

$$a^{n}=\begin{cases}a^{n/2}\cdot a^{n/2}\qquad n为偶数 \\ a^{\left( n-1\right) /2}\cdot a^{\left( n-1\right) /2}\qquad n为奇数\end{cases}$$

算法实现

剑指offer版

个人写法

复杂度分析

时间主要消耗在求解乘法运算结果上面，而使用递归方法(二分原问题)进行乘法求解的时间复杂度为 O(logn)，空间复杂度为 O(1)。

参考

<<剑指offer2>>