Morning, Noon, Night.

面试题：二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

思路1：举个例子进行说明。对于任何一个数字，和1进行与运算，判断得到的结果。设置一个count进行技术，如果结果与运算得到的结果为1，那么count就加1，每计算此意，１就向向左移动一位，直到完成所有的计算，最后得到的count值就是输出。

虽然存在丰富的精细和抽象的NLP技术，但集群和分类应始终作为处理这类数据时使用的第一种技术。 除了在生产中最容易扩展之外，它们的易用性可以迅速帮助企业解决一系列应用问题：

• 如何自动区分不同类别的句子？
• 如何找到一个数据集中最相似的句子？
• 如何提取一个丰富而简洁的表示，然后可以用于一系列其他任务？
• 如何快速找到这些任务是否可以在你的数据集上？

这篇文章的作用是提供一个简单方式的寻找句子表示，以便将它们分类或组合在一起。

动态规划

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

能采用动态规划求解的问题的特点：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
• 从上往下分析问题，从下往上求解问题。

回溯法

回溯法可以看成蛮力法的升级版，主要是在搜索过程中寻找问题的解，当发现已经不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步进行选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法过程：

• 针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
• 确定结点的扩展搜索规则。
• 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

面试题：旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

思路：我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中没我们可以用二分法实现O(logn)的查找。我们用两个指针分别指向数组的第一个元素和最后一个元素，按照旋转规则，第一个元素大于或者等于最后一个元素。

接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素位于该之间元素的后面。我们可以把第一个指针指向该之间元素，这样就可以缩小寻找范围，移动之后的第一个指针仍然位于前面的递增数组。

同样，如果该中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时数组中最小的元素位于该之间元素的前面。我们可以把第二个指针指向该之间元素，这样就可以缩小寻找范围，移动之后的第二个指针仍然位于前面的递增数组。

对于特殊情况，如下面的情况，就需要利用顺序查找。对于数组{0,1,1,1,1}的旋转。

面试题：斐波那契数列

题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

1
2
3
4
5
6
7
8
9
10
11

// ====================方法1：递归====================
long long Fibonacci_soultion1(unsigned int n)
{
    if(n<= 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci_soultion1(n-1)+Fibonacci_soultion1(n-2);
}

替换空格

题目：请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

思路: 首先准备两个指针：p1和p2。p1指向原始字符串的末尾，p2指向替换之后的字符串的末尾。接下来我们向前移动p1，逐个把它指向的字符串复制到p2指向的位置，知道遇到第一个空格为止。此时p1向前移动一格，在p2之前插入字符串”%20”，同时p2向前移动三格。

深度学习在计算机视觉领域取得了十分重大的突破，许多研究也是如雨后春笋般。而模型的训练离不开数据集的支持，因此有必要对常用的数据集进行了解。接下来主要对计算机视觉和自然语言处理这两个领域的常用数据集进行介绍。

计算机视觉

MNIST

MNIST数据集被称为深度学习领域的“Hello World!”，入门必备！它有60000个训练样本集和10000个测试样本集，每个样本图像的宽高为28*28。此数据集是以二进制存储的，不能直接以图像格式查看，不过很容易找到将其转换成图像格式的工具。

该数据集可在http://yann.lecun.com/exdb/mnist/ 获取，主要包含以下四部分：

train-images-idx3-ubyte.gz: training set images (9912422 bytes)
train-labels-idx1-ubyte.gz: training set labels (28881 bytes)
t10k-images-idx3-ubyte.gz: test set images (1648877 bytes)
t10k-labels-idx1-ubyte.gz: test set labels (4542 bytes)

二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路:首先选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。

1
2
3
4

1   2   8   9       1   2   8      1  2
2   4   9   12      2   4   9      2  4     2  4
4   7   10  13      4   7   10     4  7     4  7     4  7
6   8   11  15      6   8   11     7  8     7  8     7  8

面试题：找出数组中重复的数字

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

思路：排序一个长度为n的数组需要O(nlogn)的时间，我们选择利用哈希表来解决这个问题。从头到尾顺序扫描数组的每个数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否包含了该数字。如果哈希表没有这个数字，就把它加入哈希表。如果哈希表已经存在该数字，就找到一个重复数字。这个算法的时间复杂度是O(n),他是以创建一个大小O(n)的哈希表为代价。现在我们重排这个数组，从头到尾依次扫描这个数组。当扫描到下标为i的数组时，首先比较这个数字（用m表示）是不是等于i。如果是，则扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果他和地ｍ个数字相等，就找到一个重复的数字；如果他和第m个数字不相等，就把第i个数字和地ｍ个数字作交换，把Ｍ放到属于他的位置。重复比较交换这个过程，知道发现一个重复数字。