去除数组重复值

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中唯一个重复的数字。

Input:
0 1 2 4 2 5

思路一：

使用空间换时间，使用hashMap，开辟长度为n的数组空间，对输入的数作为index就行叠加，hashMap[2] = 1,第二次遇到2，hashMap[2]++ = 2， 说明重复的数字为2。
时间复杂度O(n)，空间复杂度O(n)

思路二：

遍历Input，将值与Input[值] 进行swap，如果交换过程中出现两次值相同则说明，当前数字是重复的。
时间复杂度O(n)，空间复杂度O(1)

二维数组中的查找

给定一个（n * m）二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

Input:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

思路一：

采用二分思想，当这个数在左下角，大于这个数的都在右边，小于这个数的都在上边。当这个数在右上角，大于这个数的都在下边，小于这个数的都在左边，所以只要从这两端进行查找速度会比较快。
时间复杂度O(n + m)，空间复杂度O(1)

矩形覆盖

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

Input:
n = 5

思路一：

动态规划思想，当n=1, 覆盖的方法 = 1， 当n=2, 覆盖的方法 = 2，当n=3，可以把这个2 * 3的大局限拆分成 2 *1 与 2 * 2 的两块区域矩形，覆盖方法为 1 + 2 = 3。f(n) = f(n -1) + f(n - 2),所有结果应该是1 2 3 5 8 ，n 为5时有 8种方法，动态规划思想，将分体拆分为一个个小问题。

变态跳台阶

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

Input:
n = 5

思路一

动态规划思想，将问题拆分为登上最后一个楼梯可以采用1 - n级的方法，所以f(n) = f(n-1) + f(n - 2) + ... + f(1) => f(n) = 2 * f(n - 1)。f(1) = 1, f(2) = 2, f(3) = 2^(n - 1), f(5) = 2 ^ 4 = 16。

求100！的结果有多少0

思路一：

首先分析阶层的计算都是通过乘法进行的，所以只要计算出有多少个10进行相乘就知道有多少个0了，而10能够通过2 * 5 得到，2的数量一定是足够的，所以只要计算出5的个数就能知道有多少个0，将每个数字进行质因数分解得出结果 (100/5 + 20/5 + 4/5) = 24。

二进制中1的个数

输入一个整数，输出该数二进制表示中 1 的个数。

思路一

整数转二进制过程中统计1的个数。
时间复杂度O(n),空间复杂度O(1)。

思路二

100010001 与 100010000进行 & 运算的结果每次都消耗一个1，所以只需要判断进行了多少次&运算就能够知道有多少个1了。

寻找重复数个数

输入一组递增数组arr = [1,2,2,2,2,4,5,5,7,7,8]求重复的2出现的次数，复杂度小于O(n)

思路一

使用二分算法。cnt = 0;
第一次： left = 0, right = 10, mid =( left + right)/ 2 = 5
arr[5] > 2 => left = 0, right = mid - 1 = 4
第二次：left = 0, right = 4, mid = 2
arr[2] == 2 => cnt++, 这时候不清楚arr[2] 左右两端与2之间的关系。

如何实现一个高效单项链表逆序输出？

head->1->2->3->4->NULL

思路一

遍历链表入栈，输出栈。

已知sqrt(2) 约等于1.414，不用数学库，求sqrt(2)精确到小数位后10位

思路一

sqrt(2)的结果是在1.4 与 1.5 之间，采用二分法，不断扩大精度，获取结果。

给定一个二叉搜索树（BST）,找到树中第K小的节点

思路一

BST左子树小于根节点，右节点大于根节点，采用中序遍历即可。

设计一个LRU 缓存机制

思路一

新数据插入使用头插法在链表首部插入数据，更新数据将旧节点移动到首部，当链表满了淘汰链表末尾数据，保留头部与尾部指针。

寻找字符串最大不重复子串

思路一

使用滑动窗口，不断的向字符串右侧移动，当出现重复字符，将字符从左侧移除，边移动边记录。

寻找字符串最大回文子串

思路一

暴力枚举每一个字符作为回文串中心向两侧判断。

思路二

动态规划，最大回文串状态转换公式f[i][j] = f[i + 1][j - 1] ^ (s[i] == s[j])

思路三

Manacher 算法，这里不多介绍。

寻找n个柱子，2个柱子之间的最大积水量

思路一

双指针法，分别从左，右两端向内移动，判断当前位置小的节点不断向中间移动，边移动边计算最大积水量。

多个字符串最长公共前缀

思路一

暴力横向遍历或者纵向遍历。

思路二

取第一个字符串，不断二分左边部分的字符串进行前缀匹配。

思路三

分而治之，将两辆个字符串判断的最长公共前缀，不断进行公共最长前缀匹配，计算出最后结果。

删除链表倒数第N个节点

思路一

定义两个指针，先让其中一个向后移动N节点，再同时移动，当其中一个节点到达尾部，另一个节点就是倒数第N个节点。