找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
-
indexOf 和 lastIndexOf。时间复杂度应该是 O(n^2)。
-
先排序再遍历。时间复杂度是 O(n * logN)。
-
哈希。时间复杂度和空间复杂度都是 O(n)。
-
因为所有数字都在 0～n-1 的范围内，也就意味着如果没有重复数的话， 0～n-1 这 n 个数在数组内都会存在一个。所以可以排序后遍历数组去看当前的元素值是否等于数组下标，有一个不等于的话说明它是重复数字。但如果要将时间复杂度和空间复杂度都降到 O(n) 的话，就不能直接使用排序。所以可以遍历数组，每次都去比较当前的数组元素（姑且称作 val）和数组下标是否相等，不相等的话再去看下标为 val 的数组元素 nums[val]。如果 nums[val] 和 val 相等，说明 val 重复了，可以直接退出循环。否则交换 nums[val] 和 val。这个方法的重点就在于，通过不断的交换使当前的数组元素值等于它的下标，相当于排序了一次， 从而达到唯一的效果。
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
- 从二维数组的右上角开始查找，如果当前数组元素大于 target，则列-1向左查找；小于的话，则行+1，向下查找；等于的话就直接返回；如果查找到边界还没找到的话，说明不存在 target。有点像排序二叉树，利用右上角左边的都小于它，下边的都大于它，一次性排除掉一行或一列。时间复杂度 O(n+m)
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：0 <= s 的长度 <= 10000
-
replace + 正则表达式。
-
使用一个新的字符串，遇到空格就拼接 %20，否则就拼接原来的字符。
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
-
先构造双向链表再从后向前遍历链表打印。
-
通过 unshift 直接插入到数组头，或者使用 reverse 翻转数组。
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
- 把 arr1 和 arr2 当做是两个栈，后进先出，所以只能使用 push 和 pop 方法。入队的时候，都将数据放到 arr1 里面。出队的时候，如果 arr2 为空，就将 arr1 的所有元素 pop 到 arr2 中，这样 arr2 中的数据顺序就符合先进先出了；如果 arr2 不为空，就直接从 arr2 里取数据，这样就不用每次出队都将 arr1 里的数据放到 arr2 里。
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
-
单纯递归，会超时。时间复杂度 O(n^2)，空间复杂度 O(1)。
-
递归 + 记忆数组，防止对已经计算出来的值重复递归计算。时间复杂度 O(n)，空间复杂度 O(n)。
-
DP，使用两个变量来保存上一个和上上一个值。时间复杂度 O(n)，空间复杂度 O(1)。
-
斐波那契数列还可以用矩阵来求解，印象中用矩阵是最快的（时间复杂度是 O(logN)），但已经忘了怎么写了 Orz。
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
-
直接循环判断
numbers[i]是否会小于numbers[i-1]，是的话就是旋转点。时间复杂度为 O(n)。 -
二分，时间复杂度为 O(logN)。
通过数组旋转，可以将原数组切分为两个升序排序的子数组，左子数组较大，右子数组较小，如 [3,4,5,1,2]。通过二分取中间的数组元素 numbers[mid]，将其和数组右边界元素 numbers[r] 比较。
大于的话说明 numbers[mid] 在右子数组中，那么旋转点在 numbers[mid] 右边，所以将寻找范围缩小到 [mid+1, r]。
小于的话说明 numbers[mid] 在左子数组中，那么旋转点可能是 numbers[mid] 或者在其左边，所以将寻找范围缩小到 [l, mid]。
等于的话只需 r-- 舍弃掉 numbers[r]，因为 r-- 后旋转点还是在 [l, r] 上。
需要注意的是（采坑了 Orz），不能将 numbers[mid] 和 numbers[l] 比较，因为两者比较无法得出 numbers[mid] 是在左子数组还是在右子数组。例如 [3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5]，numbers[mid] 都大于 numbers[l]，但最小值一个在后面，一个在前面。