（1）排序和查找是面试考察算法的重点，如二分查找、归并排序、快速排序等；
（2）查找：顺序查找、二分查找、哈希表查找、二叉排序树查找等；
（3）排序：插入排序、冒泡排序、归并排序、快速排序等算法的额外消耗空间、平均时间复杂度、最差时间复杂度等比较。
（4）一般递归比循环代码实现简单，但递归可能造成计算重复、影响性能；递归调用层级太多，还有可能引起调用栈溢出。
6. 旋转数组的最小数字
- 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
// Solution:二分查找，根据中间值与两端值的大小缩小范围；
// Tips: (1)特殊旋转：仅调整0个元素到前方；（2）三个数字相同时，无法判断如何移动指针，∴顺序查找
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.empty()) {
printf("Invalid input.");
return 0;
}
int left = 0;
int right = rotateArray.size()-1;
int mid = left; // 仅调整0个元素时返回第一个值
while (rotateArray[left] >= rotateArray[right]) {
if (right - left == 1) {
mid = right;
break;
}
mid = (left+right)/2;
// left,right,mid指向的三个数字相同时，顺序查找
if (rotateArray[left] == rotateArray[right] &&
rotateArray[left] == rotateArray[mid]) {
return minInOrder(rotateArray);
}
if (rotateArray[mid] >= rotateArray[left]) {
left = mid;
} else if (rotateArray[mid] <= rotateArray[right]) {
right = mid;
}
}
return rotateArray[mid];
}
int minInOrder(vector<int> rotateArray) {
int min = rotateArray[0];
int size = rotateArray.size();
for (int i = 1; i < size; i ++) {
if (min > rotateArray[i])
min = rotateArray[i];
}
return min;
}
};
7. 斐波那契数列（循环实现，避免重复计算）
// 斐波那契数列（n<=39）
// f(n) = f(n-1)+f(n-2), n>1; f(0)=0, f(1)=1
// Solution: 循环求解，避免递归大量重复计算
class Solution {
public:
int Fibonacci(int n) {
if (n == 1) {
return 1;
} else if (n == 0) {
return 0;
}
int fibNMinusTwo = 0;
int fibNMinusOne = 1;
int fibN = 0;
for (int i = 2; i <= n; i ++) {
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
};
8. 跳台阶（斐波那契数列应用）
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
// Solution:斐波那契数列应用
// f(1) = 1, f(2) = 2; f(n) = f(n-1) + f(n-2), n > 2.
class Solution {
public:
int jumpFloor(int number) {
if (number == 1) {
return 1;
} else if (number == 2) {
return 2;
}
int fNMinusTwo = 1;
int fNMinusOne = 2;
int fN = 0;
for (int i = 3; i <= number; i ++) {
fN = fNMinusOne + fNMinusTwo;
fNMinusTwo = fNMinusOne;
fNMinusOne = fN;
}
return fN;
}
};
9. 变态跳台阶
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
// Solution: 可用数学归纳法证明 f(n) = 2^(n-1)
/*
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
*/
class Solution {
public:
int jumpFloorII(int number) {
if (number == 0) {
return 0;
}
int res = 1;
for (int i = 2; i <= number; i ++) {
res = 2*res;
}
return res;
}
};
10. 矩形覆盖（斐波那契数列应用）
- 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
// Solution:斐波那契数列应用
// f(n) = f(n-1) 竖放 +f(n-2) 横放； f(1) = 1, f(2) = 2.
class Solution {
public:
int rectCover(int number) {
if (number == 1) {
return 1;
} else if (number == 2) {
return 2;
}
int fNMinusTwo = 1;
int fNMinusOne = 2;
int fN = 0;
for (int i = 3; i <= number; i ++) {
fN = fNMinusOne + fNMinusTwo;
fNMinusTwo = fNMinusOne;
fNMinusOne = fN;
}
return fN;
}
};
