劍指offer--程式設計題參考代碼(3)

繼續分享，求醜數，菲不拉基數列啊，一些邏輯的以及算法等。

15.整數中1出現的次數（從1到n整數中1出現的次數）

<span style="font-size:14px;">class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
       int sum=0;
        if(n<0)
            return -1;
        if(n== 0)
            return 0;
       for(int i=1 ;i<=n;i++){
           int temp = i;
           while(temp>0)
               {
               if(temp%10 == 1)
                   ++sum;
               temp=temp/10;
           }
       }
        return sum;
    }
};</span>
           

16.用位運算實作加法

定理1：設a，b為兩個二進制數，則a+b = a^b + (a&b)<<1。

證明：a^b是不考慮進位時加法結果。當二進制位同時為1時，才有進位，是以 (a&b)<<1是進位産生的值，稱為進位補償。

将兩者相加便是完整加法結果。

定理2：使用定理1可以實作隻用位運算進行加法運算。

證明：利用定理1中的等式不停對自身進行疊代。每疊代一次，進位補償右邊就多一位0，

是以最多需要加數二進制位長度次疊代，進位補償就變為0，這時運算結束。

<span style="font-size:14px;">class Solution {
public:
    int Add(int num1, int num2)
    {
      int jw=num1&num2;
      int jg=num1^num2;
   while(jw)
  {
   int t_a=jg;
   int t_b=jw<<1;
   jw=t_a&t_b;
   jg=t_a^t_b;
  }
  return jg;
    }
};</span>
           

17.把字元串轉換成整數

<span style="font-size:14px;">class Solution {
public:
    int StrToInt(string str) {
        int i=0,sum=0,len;
        len =str.length();
        if(str[0]=='-'||str[0]=='+')
            i=1;
        for(int j=i;j<len;j++){
            if(str[j]<'0'|| str[j]>'9')
                return 0;
        }
        while(i<len)
            {
            sum=sum*10+(str[i++]-'0');
        }
        if(str[0]=='-')
            sum=-sum;
        return sum;
    }
};
</span>
           

18.醜數

把隻包含因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含因子7。

 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。

1.周遊的方式（代碼簡單，效率低），

<span style="font-size:14px;">int number = 1500; //要求輸出醜數的數
 int index = 1; //數字本身
 while(number > 0){
 int temp = index;
 while(temp%2 == 0)temp = temp/2;
 while(temp%3 == 0)temp = temp/3;
 while(temp%5 == 0)temp = temp/5;
 if(temp == 1)
 {  
 System.out.println(index+"number="+number);
 number--;
 }
 index++;
 } </span>
           

（此段 文字借鑒了别人的原理）

按規律求值，如果p是醜數，那麼p=2^x * 3^y * 5^z

那麼隻要賦予x,y,z不同的值就能得到不同的醜數。

如果要順序找出醜數，要知道下面幾個特（fei）點（hua）。

對于任何醜數p：

（一）那麼2*p,3*p,5*p都是醜數，并且2*p<3*p<5*p

（二）如果p<q, 那麼2*p<2*q,3*p<3*q,5*p<5*q

現在說說算法思想：

    由于1是最小的醜數，那麼從1開始，把2*1，3*1，5*1，進行比較，得出最小的就是1

的下一個醜數，也就是2*1，

    這個時候，多了一個醜數‘2’，也就又多了3個可以比較的醜數，2*2，3*2，5*2，

這個時候就把之前‘1’生成的醜數和‘2’生成的醜數加進來也就是

(3*1,5*1,2*2，3*2，5*2)進行比較，找出最小的。。。。如此循環下去就會發現，

每次選進來一個醜數，該醜數又會生成3個新的醜數進行比較。

   下面說一個O（n）的算法。

    在上面的特（fei）點（hua）中，既然有p<q, 那麼2*p<2*q，那麼

“我”在前面比你小的數都沒被選上，你後面生成新的醜數一定比“我”大吧，那麼你乘2

生成的醜數一定比我乘2的大吧，那麼在我選上之後你才有機會選上。

其實每次我們隻用比較3個數：用于乘2的最小的數、用于乘3的最小的數，用于乘5的最小的

數。也就是比較(2*x , 3*y, 5*z) ，x>=y>=z的，

個人實作：

<span style="font-size:14px;">class Solution {
public:
    int GetUglyNumber_Solution(int index) {     
       int ugly[index];
       for (int i = 0; i < index; i++) {  
         ugly[i] = 0;  
        }  
        ugly[0]=1;
        int i=0;
        int t2=0,t3=0,t5=0;
        while(i<index){
           ++i;
        ugly[i]=min_3(ugly[t2]*2,ugly[t3]*3,ugly[t5]*5);
        if(ugly[t2]*2==ugly[i])
           t2++;
        if(ugly[t3]*3==ugly[i])
           t3++;
        if(ugly[t5]*5==ugly[i])
           t5++;
       }
       return ugly[index-1];
    }
    int min_3(int a,int b,int c){
    return (a=(a<b?a:b))<c?a:c;
   //return a<b?(a<c?a:c):(b<c?b:c);
    }
};</span>
           

19.菲不拉基數列：

遞歸求法：

<span style="font-size:14px;">class Solution {
public:
    int Fibonacci(int n) {
         if(n==1)
             return 1;
         if(n==2)
             return 1;
         return Fibonacci(n-1)+Fibonacci(n-2) ;
    }
};</span>
           

非遞歸：

<span style="font-size:14px;">class Solution {
public:
    int Fibonacci(int n) {
         if(n<=0)
             return 0;
         if(n<=2)
             return 1;
         int a=1,b=1,c=0;
         n=n-2;
         while(n>0)
             {
             c=a+b;
             a=b;
             b=c;
             --n;
         }
        return b;
    }
};</span>