剑指Offer.C++.code6-10

（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;
    }
};