?前言?

今天是九日集訓第二天，我會記錄一下學習內容和題解，爭當課代表0.0.
注意！！！！題解的解法一是今天要掌握的解法，解法2是學有余力再研究，涉及到后面知識點0.0
鏈接：《LeetCode零基礎指南》(第二講) 函式
另外：昨天講過的知識點我今天不會再放有需要請查看：
【解題報告】《LeetCode零基礎指南》(第二講) 函式

🧑🏻作者簡介：一個從工業設計改行學嵌入式的年輕人
?聯系方式：2201891280(QQ)
?全文大約閱讀時間： 15min

🎁主要知識點梳理

📝回圈的使用

在C/C++語言中有兩種結構：while和for，但是在很多情況下，兩者沒有太多本質差別，所以我們學習相對應用更方便的for陳述句，

🥨1.語法規則

	for陳述句的表現形式是：

for(回圈初始化運算式;回圈條件運算式;回圈執行運算式){
	回圈體;
}

它的運行程序為

1. 首先，執行回圈初始化運算式，這個只會執行一次！！
2. 然后，執行回圈條件運算式，若值為真，則執行回圈體，否則結束，
3. 接著執行回圈體后執行之回圈執行運算式，
4. 重復執行2、3直到2為假跳出回圈，
   

🥞2.簡單應用

下面的程式演示了一個簡單的1+2+…+n的值求解

int sumNums(int n){             // 入口函式傳參為n
   int i;                      // 宣告一個變數
   int sum = 0;                // 作為回傳的值初始化為0
   for(i = 1; i <= n; ++i) {   // 回圈
       sum += i;               // 回圈體
   }
   return sum;                 // 回傳結果
}

🍔3.初始化運算式

3.1 初始化運算式外置

這里就是講初始化運算式提到for回圈外面

int sumNums(int n){             // 入口函式傳參為n
   int i = 1;                      // 宣告一個變數
   int sum = 0;                // 作為回傳的值初始化為0
   for(; i <= n; ++i) {   // 回圈
       sum += i;               // 回圈體
   }
   return sum;                 // 回傳結果
}

3.2 初始化運算式內置

這里就是可以直接進行初始化和賦值，但是這樣使用for回圈執行完之后會直接進行銷毀變數，所以這個程式是錯的！！！

int sumNums(int n){             // 入口函式傳參為n
   for(int i = 1, sum = 0; i <= n; ++i) {   // 回圈
       sum += i;               // 回圈體
   }
   return sum;                 // 回傳結果
}

3.3 初始化運算式的正確用法

為了之后還能使用變數，就需要在外面宣告，

int sumNums(int n){             // 入口函式傳參為n
   int i,sum;
   for(i = 1, sum = 0; i <= n; ++i) {   // 回圈
       sum += i;               // 回圈體
   }
   return sum;                 // 回傳結果
}

🥙4.條件運算式

條件運算式可以省略，但是會是個死回圈，下面的程式必超時，

int sumNums(int n){             // 入口函式傳參為n
   int i = 1;                      // 宣告一個變數
   int sum = 0;                // 作為回傳的值初始化為0
   for(;; ++i) {   // 回圈
       sum += i;               // 回圈體
   }
   return sum;                 // 回傳結果
}

🌮5.執行運算式

它是結構體執行完之后加的一部分內容，本身可以放在回圈體內，

int sumNums(int n){             // 入口函式傳參為n
   int i = 1;                      // 宣告一個變數
   int sum = 0;                // 作為回傳的值初始化為0
   for(;i<= n; ) {   // 回圈
       sum += i;               // 回圈體
       i++;
   }
   return sum;                 // 回傳結果
}

🍗課后習題

劍指 Offer 64. 求1+2+…+n

劍指 Offer 64. 求1+2+…+n
題目描述

求1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷陳述句（A?B:C），

思路1

管那么多，回圈沖！不解釋，知識點有，

int sumNums(int n){           
    int i;                      
    int sum = 0;               
    for(i = 1; i <= n; ++i) {   
        sum += i;              
    }
    return sum;                
}

思路2

沒限制遞回呀，遞回沖！

int sumNums(int n){
    if(n == 1) return 1;//遞回出口
    return n + sumNums(n - 1); //下一層遞回
}

231. 2 的冪

231. 2 的冪
題目描述

給你一個整數 n，請你判斷該整數是否是 2 的冪次方，如果是，回傳 true ；否則，回傳 false ，
如果存在一個整數 x 使得 n == 2x ，則認為 n 是 2 的冪次方，

思路1

同樣的回圈沖就好了，但是要注意溢位問題，

bool isPowerOfTwo(int n){
    for(int i = 1;i <= 1<<30;){
        if(i == n)  return true;
        if(i == 1<<30) break;	//防止溢位
        else i*=2;
    }
    return false;
}

思路2

其實溢位也是假溢位 把i變成unsigned 就會很省事

bool isPowerOfTwo(int n){
    for(unsigned int i = 1;i <= 1<<30;i*=2){
        if(i == n)  return true;
    }
    return false;
}

思路3

高級用法之位運算，之位與
因為2的冪在二進制表示中就是只有一個1其它都是0 所以用x&(x-1) == 0 判斷是不是就好了
看不懂請跳過0.0

bool isPowerOfTwo(int n){
    return n<=0?0:!(n & (n-1));
}

326. 3 的冪

326. 3 的冪
題目描述

給定一個整數，寫一個函式來判斷它是否是 3 的冪次方，如果是，回傳 true ；否則，回傳 false ，
整數 n 是 3 的冪次方需滿足：存在整數 x 使得 n == 3x

思路

其實和上面差不多 我們這次換個思路，3的冪肯定是除了1只包含3這個質因子，我們不斷的除3看是否最后是1就好了，

bool isPowerOfThree(int n){
    if(n <= 0) return false;
    while(n % 3 == 0) n /= 3;
    if(n == 1) return true;
    return false;
}

342. 4的冪

342. 4的冪
題目描述

給定一個整數，寫一個函式來判斷它是否是 3 的冪次方，如果是，回傳 true ；否則，回傳 false ，
整數 n 是 3 的冪次方需滿足：存在整數 x 使得 n == 3x

思路

和3的冪是一樣的，

bool isPowerOfFour(int n){
    if(n <= 0) return false;
    while(n % 4 == 0)	//判斷能否整除
        n /= 4;		//除4
    return n == 1;
}

1492. n 的第 k 個因子

1492. n 的第 k 個因子
題目描述

給你兩個正整數 n 和 k ，
如果正整數 i 滿足 n % i == 0 ，那么我們就說正整數 i 是整數 n 的因子，
考慮整數 n 的所有因子，將它們 升序排列 ，請你回傳第 k 個因子，如果 n 的因子數少于 k ，請你回傳 -1 ，

思路

直接去統計是否到達第k個因子就好了，

int kthFactor(int n, int k){
        for(int i = 1; i <= n ; i++){
            if(n % i == 0) k--;
            if(!k) return i;
        }
        return -1;	//最后k都還有數字
}

367. 有效的完全平方數

367. 有效的完全平方數
題目描述

給定一個 正整數 num ，撰寫一個函式，如果 num 是一個完全平方數，則回傳 true ，否則回傳 false ，
進階：不要 使用任何內置的庫函式，如 sqrt ，

思路1

直接去遍歷查找就完事了，

int isPerfectSquare(int x){
    int i;
    long long p;
    for(i = 1; ; ++i) {    
        p = (long long)i*i;  
        if(p == x) {
            return true;     
        } 
        if(p > x) {
            return false;
        }
    }
    return false;         
}

思路2

為了加速二分查找，

bool isPerfectSquare(int num){
    unsigned int left = 0, right = 1<<16;//最大也就這么大了
    while(left < right){
        unsigned int mid = left + (right - left)/2;
        if(mid * mid > num) right = mid;
        else if(mid *mid == num) return true;
        else left = mid + 1;
    }
    return false;
}

📑寫在最后
今天完成了第二天的打卡，演算法筆記因為第二章內容很簡單，我想跳過，但是內容還是有億點點多，我晚上肯定能更完-.-希望大家可以跟我一起，0.0