?前言?

今天是九日集訓第八天，我會記錄一下學習內容和題解，爭當課代表0.0.
鏈接：《LeetCode零基礎指南》(第九講) 簡單遞回

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

🎁主要知識點梳理

📝1.遞回含義

套娃生萬物，而遞回就是函式自己呼叫自己，
遞回需要記住三點內容：

1. 要實作一個函式，這個函式會自己呼叫自己，并且每次呼叫，函式傳參是不一樣的，
2. 遞回一定要有出口，即滿足一定條件后需要return，否則就可能出現死遞回(引起堆疊溢位)，
3. 根據遞回式來補充你的遞回呼叫內容，

🍿2.遞回呼叫階乘

我們知道，階乘即：
n ! = n ? ( n ? 1 ) ? ( n ? 2 ) ? . . . ? 3 ? 2 ? 1 n! = n *(n-1)*(n-2)*...*3*2*1 n!=n?(n?1)?(n?2)?...?3?2?1
我們如果想用遞回進行計算，就需要轉換為遞推式，如下：
n ! = n ? ( n ? 1 ) ! n! = n*(n-1)! n!=n?(n?1)!
我們可以得出一下的遞回式：
f ( n ) = n f ( n ? 1 ) f(n) = n f(n-1) f(n)=nf(n?1)

---

1. 實作一個函式

int JieCheng(int n){
}

---

2. 遞回出口

int JieCheng(int n) {
  if(n <= 1) {
      return 1;
  }
}

---

3. 遞推關系

int JieCheng(int n) {
  if(n <= 1) {
          return 1;
  }
  return n * JieCheng(n-1);
}

🍔3. 為什么叫遞回

f(5)
= 5 * f(4)
= 5 * (4 * f(3))
= 5 * (4 * (3 * f(2)))
= 5 * (4 * (3 * (2 * f(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

🍗課后習題

172. 階乘后的零

172. 階乘后的零

題目描述

給定一個整數 n ，回傳 n! 結果中尾隨零的數量，
提示n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

思路

因為階乘的0的數量其實取決于這個數中10的因子個數，但是10 = 5 *2，其中2的數量會比5的數量多，所以只需要5因子的數量就好了，其中5的倍數貢獻一個，25貢獻兩個，125貢獻三個，但是25還是5的倍數，所以只需要再算一次就好了， 125也是一樣的道理，125算一個就好了，

int trailingZeroes(int n){
    int ans = 0;
    for(int i = 5;i <= n;i*=5){
        ans += n / i;
    }
    return ans;
}

1342. 將數字變成 0 的操作次數

1342. 將數字變成 0 的操作次數

題目描述

給你一個非負整數 num，請你回傳將它變成 0 所需要的步數， 如果當前數字是偶數，你需要把它除以 2 ；否則，減去 1 ，

思路

按照要求進行除就好了，

int numberOfSteps(int num){
    if(num == 0) return 0;
    else if( num & 1 == 1)  return numberOfSteps(num -1) +1;
    else return numberOfSteps(num / 2) +1;
}

222. 完全二叉樹的節點個數

222. 完全二叉樹的節點個數

題目描述

給你一棵 完全二叉樹 的根節點 root，求出該樹的節點個數，
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置，若最底層為第 h層，則該層包含 1~ 2h個節點，

思路

利用先根遍歷的寫法就行了，

void previsit(struct TreeNode *root,int *ans){
    if(root){
        (*ans) ++;
        previsit(root->left,ans);
        previsit(root->right,ans);
    }
}

int countNodes(struct TreeNode* root){
    int ans = 0;
    previsit(root,&ans);
    return ans;
}

LCP 44. 開幕式焰火

LCP 44. 開幕式焰火

題目描述

「力扣挑戰賽」開幕式開始了，空中綻放了一顆二叉樹形的巨型焰火，
給定一棵二叉樹root代表焰火，節點值表示巨型焰火這一位置的顏色種類，請幫小扣計算巨型焰火有多少種不同的顏色，

思路

利用hash表來做標記，然后進行先根遍歷，然后最后算數量，

int hash[1001];
void get123(struct TreeNode * );

int numColor(struct TreeNode* root){
    int ans = 0;
    memset(hash,0,sizeof(hash));
    get123(root);
    for(int i = 0; i < 1001; ++i){
        if(hash[i]) ans++;
    }
    return ans;
}

void get123(struct TreeNode * root){
    if(root){
        if(root ->left) get123(root->left);
        hash[root->val]++;
        if(root->right) get123(root->right);
    }
}

397. 整數替換

397. 整數替換

題目描述

給定一個正整數 n，你可以做如下操作：

1. 如果n 是偶數，則用n / 2替換n ，
2. 如果n是奇數，則可以用n + 1或n - 1替換n ，

n變為1所需的最小替換次數是多少？

思路

如果是偶數，毫無疑問是直接除以2就好了，
如果是奇數：

1. 如果這個奇數是k = 4*n+1那么(k-1)/2會得到更小的值，
2. 如果這個奇數是k = 4*n+3 那么(k+1)/4會得到最小的值，但是有一個特殊情況就是n=3

int integerReplacement(int n){
    int ans = 0;
    while(n != 1){
        if(n % 2 == 0)  n /= 2;
        else if(n % 4 == 1){
            n /= 2;
            ans++;
        }
        else{
            if(n == 3)  n = 1;
            else n = n/2 + 1;
            ans++;
        }
        ans++;
    }
    return ans;
}

938. 二叉搜索樹的范圍和

938. 二叉搜索樹的范圍和

題目描述

給定二叉搜索樹的根結點 root，回傳值位于范圍[low, high]之間的所有結點的值的和，

思路

先根遍歷的方式來統計和就好了，

void previsit(struct TreeNode *root,int low,int high,int *ans){
    if(root){
        if(root->val >= low && root->val <= high)  (*ans) += root->val;
        previsit(root->left,low,high,ans);
        previsit(root->right,low,high,ans);
    }
}

int rangeSumBST(struct TreeNode* root, int low, int high){
    int ans = 0;
    previsit(root,low,high,&ans);
    return ans;
}

劍指 Offer 55 - I. 二叉樹的深度

劍指 Offer 55 - I. 二叉樹的深度

題目描述

輸入一棵二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度，
例如：
給定二叉樹 [3,9,20,null,null,15,7]，

思路

其實可能需要層序遍歷的，但是也可以用先序遍歷來看層的深度，做個記錄就好了，

void previsit(struct TreeNode *root,int *max,int ceng){
    if(root){
        ceng ++;
        if(ceng > *max) *max = ceng;
        previsit(root->left,max,ceng);
        previsit(root->right,max,ceng);
    }
}

int maxDepth(struct TreeNode* root){
    int max = 0;
    previsit(root,&max,0);
    return max;
}

104. 二叉樹的最大深度

104. 二叉樹的最大深度

題目描述

給定一個二叉樹，找出其最大深度，
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，
說明: 葉子節點是指沒有子節點的節點，
示例：
給定二叉樹[3,9,20,null,null,15,7]，

思路

其實可能需要層序遍歷的，但是也可以用先序遍歷來看層的深度，做個記錄就好了，

void previsit(struct TreeNode *root,int *max,int ceng){
    if(root){
        ceng ++;
        if(ceng > *max) *max = ceng;
        previsit(root->left,max,ceng);
        previsit(root->right,max,ceng);
    }
}

int maxDepth(struct TreeNode* root){
    int max = 0;
    previsit(root,&max,0);
    return max;
}

226. 翻轉二叉樹

226. 翻轉二叉樹

題目描述

翻轉一棵二叉樹，

思路

遍歷每個節點，交換左右節點，

struct TreeNode* invertTree(struct TreeNode* root){
    if(root){
        struct TreeNode *temp;
        temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
    }
    return root;
}

劍指 Offer II 110. 所有路徑

劍指 Offer II 110. 所有路徑

題目描述

給定一個有 n 個節點的有向無環圖，用二維陣列graph表示，請找到所有從 0到n-1的路徑并輸出（不要求按順序），

graph的第i個陣列中的單元都表示有向圖中i號節點所能到達的下一些結點（譯者注：有向圖是有方向的，即規定了 a→b 你就不能從 b→a ），若為空，就是沒有下一個節點了，

思路

根據每個節點進行深度遍歷，如果等于所要求的資料，就將路徑所有的節點插入到最終的結果，因為無環，所以不需要標記資料，

void dfs(int x,int n, int **graph, int *graphColSize,int *returnSize,int **returnColumnSizes,int **ans,int *temp,int tempsize){
    if(x == n){
        int *tmp = malloc(sizeof(int)*tempsize);
        memcpy(tmp,temp,sizeof(int) * tempsize);
        ans[*returnSize] = tmp;
        (*returnColumnSizes)[(*returnSize)++] = tempsize;
        return;
    }
    for(int i = 0; i < graphColSize[x];i++){
        int y = graph[x][i];
        temp[tempsize++] = y;
        dfs(y,n, graph , graphColSize, returnSize,returnColumnSizes,ans,temp,tempsize);
        tempsize--;
    }
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes){
    int **ans;
    int temp[15];
    int tempsize = 0;
    temp[tempsize++] = 0;
    ans = malloc(sizeof(int *) * (1<<13));
    *returnSize = 0;
    (*returnColumnSizes) = malloc(sizeof(int) *(1<<13));
    dfs(0,graphSize - 1, graph , graphColSize, returnSize,returnColumnSizes,ans,temp,tempsize);
    return ans;
}

797. 所有可能的路徑

797. 所有可能的路徑

題目描述

給你一個有 n 個節點的 有向無環圖（DAG），請你找出所有從節點 0 到節點 n-1 的路徑并輸出（不要求按特定順序）
二維陣列的第 i 個陣列中的單元都表示有向圖中 i 號節點所能到達的下一些節點，空就是沒有下一個結點了，
譯者注：有向圖是有方向的，即規定了 a→b 你就不能從 b→a ，

思路

和上面一樣，所以看上面的把，

void dfs(int x,int n, int **graph, int *graphColSize,int *returnSize,int **returnColumnSizes,int **ans,int *temp,int tempsize){
    if(x == n){
        int *tmp = malloc(sizeof(int)*tempsize);
        memcpy(tmp,temp,sizeof(int) * tempsize);
        ans[*returnSize] = tmp;
        (*returnColumnSizes)[(*returnSize)++] = tempsize;
        return;
    }
    for(int i = 0; i < graphColSize[x];i++){
        int y = graph[x][i];
        temp[tempsize++] = y;
        dfs(y,n, graph , graphColSize, returnSize,returnColumnSizes,ans,temp,tempsize);
        tempsize--;
    }
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes){
    int **ans;
    int temp[15];
    int tempsize = 0;
    temp[tempsize++] = 0;
    ans = malloc(sizeof(int *) * (1<<13));
    *returnSize = 0;
    (*returnColumnSizes) = malloc(sizeof(int) *(1<<13));
    dfs(0,graphSize - 1, graph , graphColSize, returnSize,returnColumnSizes,ans,temp,tempsize);
    return ans;
}

🍦寫在最后

今天結束了六級，也結束了數字集成電路的作業，所以最近有億點點時間可以更新，所以要開演算法坑了，有一起的同學們么？首頁見！