題目六：旋轉(zhuǎn)數(shù)組的最小數(shù)字

題目描述：
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)猛频。
輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)蚓让，該數(shù)組的最小值為1乾忱。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0历极，請(qǐng)返回0窄瘟。

解題思路：
直接使用二分法查找最小值

  public int minNumberInRotateArray(int [] array) {
        if(array.length == 0)
            return 0;
        int low = 0 ; int high = array.length - 1;
        while (low < high){
            int mid = (low + high) / 2;
            if(array[mid] > array[high]){
                low = mid + 1;
            }else if(array[mid] == array[high]){
                high = high - 1;
            }else{
                high = mid;
            }
        }
        return array[low];
    }

題目七：斐波那契數(shù)列

題目描述：
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n趟卸，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)蹄葱。

解題思路：
可以用遞歸的方式，但是如果n代表的數(shù)字過大會(huì)出現(xiàn)卡頓和內(nèi)存溢出的問題锄列。這里還是使用循環(huán)來解決图云。

  public int Fibonacci(int n) {

        int fn1 = 1;
        int fn2 = 1;

        if (n <= 0) {
            return 0;
        }

        if (n == 1 || n == 2) {
            return 1;
        }

        while (n-- > 2) {
            fn1 += fn2;
            fn2 = fn1 - fn2;
        }
        return fn1;
    }

題目八：跳臺(tái)階

題目描述：
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)右蕊。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法琼稻。

解題思路：
如果能理解到其實(shí)就是求類似斐波那契數(shù)列的一個(gè)數(shù)列，那么就好辦得多了饶囚。根據(jù)第七題修改而來:

   public int JumpFloor(int target) {
        int fn1 = 2;
        int fn2 = 1;

        if (target <= 0) {
            return 0;
        }else if (target == 1 ) {
            return 1;
        }else if (target == 2 ) {
            return 2;
        }

        while (target-- > 2) {
            int fn = fn1;
            fn1 += fn2;
            fn2 = fn;
        }
        return fn1;
    }

題目九：變態(tài)跳臺(tái)階

題目描述：
一只青蛙一次可以跳上1級(jí)臺(tái)階帕翻，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法萝风。

解題思路：
其實(shí)根據(jù)題意可以得到：f(n) = 2 * f(n-1)嘀掸，那么f(n)=2的(n-1)次方。

  public int JumpFloorII(int target) {

        if (target <= 0) {
            return 0;
        }else if (target == 1 ) {
            return 1;
        }

        return (int) Math.pow(2, target -1);
    }

題目十：矩形覆蓋

題目描述：
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形规惰。請(qǐng)問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2*n的大矩形睬塌，總共有多少種方法？

解題思路：
依舊是斐波拉契數(shù)列歇万。

  public int RectCover(int target) {
        int fn1 = 2;
        int fn2 = 1;

        if (target <= 0) {
            return 0;
        }else if (target == 1 ) {
            return 1;
        }else if (target == 2 ) {
            return 2;
        }

        while (target-- > 2) {
            int fn = fn1;
            fn1 += fn2;
            fn2 = fn;
        }
        return fn1;
    }