斐波那契數列

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。

n<=39

思路：此題用遞歸會超內存，故直接循環。

代碼：

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int ans=0,temp1=0,temp2=1;
        for(int i=2;i<=n;i++){
            ans=temp1+temp2;
            temp1=temp2;
            temp2=ans;
        }
        return ans;
    }
};

　跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法

思路：

對于本題,前提只有 一次 1階或者2階的跳法。

a.如果兩種跳法，1階或者2階，那么假定第一次跳的是一階，那么剩下的是n-1個臺階，跳法是f(n-1);

b.假定第一次跳的是2階，那么剩下的是n-2個臺階，跳法是f(n-2)

c.由a\b假設可以得出總跳法為: f(n) = f(n-1) + f(n-2) 

d.然后通過實際的情況可以得出：只有一階的時候 f(1) = 1 ,只有兩階的時候可以有 f(2) = 2

e.可以發現最終得出的是一個斐波那契數列。

代碼：

class Solution {
public:
    int jumpFloor(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        int ans=0,temp1=1,temp2=2;
        for(int i=3;i<=n;i++){
            ans=temp1+temp2;
            temp1=temp2;
            temp2=ans;
        }
        return ans;
    }
};

　　變態跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

思路：每個臺階都有跳與不跳兩種情況（除了最后一個臺階），最后一個臺階必須跳。所以共用2^(n-1)中情況，這里的一行就是通過位移做乘法得到2^(n-1)的結果（小技巧：2的n次方可以通過對1進行位移求）。

class Solution {
public:
    int jumpFloorII(int number){
        return  1<<--number;
    }
};

　　矩形覆蓋

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？

思路：對于大矩形來說，去掉一塊小矩形，即是n-1的情況，而1塊小矩形的添加只有一種，去掉2塊小矩形，2塊小矩形的添加也只有一種。因而遞推方程為f(n)=f(n-1)+f(n-2).

代碼：

class Solution {
public:
    int rectCover(int number) {
        if(number==0) return 0;
        if(number==1) return 1;
        if(number==2) return 2;
        return rectCover(number-1)+rectCover(number-2);
    }
};

　　二進制中1的個數

輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

思路：JAVA直接使用toBinaryString二進制轉換即可，C++可以考慮：如果一個整數不為0，那么這個整數至少有一位是1。如果我們把這個整數減1，那么原來處在整數最右邊的1就會變為0，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響。

舉個例子：一個二進制數1100，從右邊數起第三位是處于最右邊的一個1。減去1后，第三位變成0，它后面的兩位0變成了1，而前面的1保持不變，因此得到的結果是1011.我們發現減1的結果是把最右邊的一個1開始的所有位都取反了。這個時候如果我們再把原來的整數和減去1之后的結果做與運算，從原來整數最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000.也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0.那么一個整數的二進制有多少個1，就可以進行多少次這樣的操作。
即可得如下代碼：
class Solution {
public:
     int  NumberOf1(int n) {
         int cnt=0;
         while(n!=0){
             cnt++;
            n=n&(n-1);
         }
         return cnt;
     }
};

　　數值的整數次方

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

思路：直接用快速冪求解即可。

代碼：

class Solution {
public:
    double Power(double base, int exponent) {
        double res=1.0;
        long long p=abs(exponent);
        while(p){
            if(p&1) res*=base;
            base*=base;
            p>>=1;
        }
        return (exponent>0)?res:1/res;
    }
};