一文了解分而治之和動態規則算法

• 一、分而治之
• • 1、分而治之是什么？
  • 2、應用場景
  • 3、場景剖析：歸并排序和快速排序
• 二、動態規則
• • 1、動態規則是什么？
  • 2、應用場景
  • 3、場景剖析：斐波那契數列
  • 4、動態規則VS分而治之
• 三、分而治之算法常見應用
• • 1、leetcode 374：猜數字大小
  • 2、leetcode 226：翻轉二叉樹
  • 3、leetcode 100：相同的樹
  • 4、leetcode 101：對稱二叉樹
• 四、動態規則算法常見應用
• • 1、leetcode 70：爬樓梯
  • 2、leetcode 198：打家劫舍
  • 3、leetcode 62：不同路徑
• 五、結束語

眾多周知，分而治之算法和動態規則算法是前端面試中的“寵兒”。而在我們的日常生活中，這兩個場景的應用也相對比較廣泛。比如，分而治之算法常用于翻轉二叉樹、快速搜索等場景中，而動態規則算法，則常用于最少硬幣找零問題、背包問題等場景中。

在下面的這篇文章中，將講解分而治之和動態規則的常用場景以及對 leetcode 的一些經典例題進行解析。

一、分而治之

1、分而治之是什么？

• 分而治之是算法設計中的一種方法。
• 它將一個問題分成多個和原問題相似的小問題，遞歸解決小問題再將結果合并以解決原來的問題。

2、應用場景

• 歸并排序
• 快速搜索
• 二分搜索
• 翻轉二叉樹
• ……

3、場景剖析：歸并排序和快速排序

（1）場景一：歸并排序

• 分：把數組從中間一分為二。
• 解：遞歸地遞歸的對兩個子數組進行歸并排序。
• 合：合并有序子數組。

（2）場景二：快速排序

• 分：選基準，按照基準把數組分成兩個子數組。
• 解：遞歸地對兩個子數組進行快速排序。
• 合：對兩個子數組進行合并。

二、動態規則

1、動態規則是什么？

• 動態規則是算法設計中的一種方法；
• 它將一個問題分解為相互重疊的子問題，通過反復求解子問題，來解決原來的問題。

看到這里，很多小伙伴會想著，動態規則和分而治之不是解決同樣的問題嗎？其實不是的。

注意：

• 動態規則解決相互重疊的子問題。

• 分而治之解決的是相互獨立的子問題。

這樣說可能還有點抽象，稍后將在第3點的時候做詳細解析。

2、應用場景

• 最少硬幣找零問題
• 背包問題
• 最長公共子序列
• 矩陣鏈相乘
• ……

3、場景剖析：斐波那契數列

斐波那契數列是一個很典型的數學問題。斐波那契數列指的是這樣一個數列：

這個數列從第3項開始，每一項都等于前兩項之和。即：

$$Fibonacci[n]=?\begin{array}{l}0,n=0\\ 1,n=1\\ Fibonacci[n?1]+Fibonacci[n?2],n>1\end{array}$$

那么我們來梳理一下，斐波那契數列是怎么運用動態規則算法的。主要有以下兩點：

• 定義子問題：F(n)=F(n - 1) + F(n - 2)；
• 反復執行：從2循環到n，執行上述公式。

4、動態規則VS分而治之

看完上面的內容，我們來梳理下動態規則和分而治之的區別。先用一張圖展示兩者的區別。

大家可以看到，左邊的斐波那契數列是將所有問題分解為若干個相互重疊的問題，每個問題的解法都一樣。

而右邊的翻轉二叉樹，左右子樹是相互獨立的，需先翻轉左右子樹，且在翻轉過程中，它們各自翻轉，互不干擾，左子樹干左子樹的活，右子樹干右子樹的活。

不像斐波那契數列那樣，每一層都是相互依賴的，一層嵌套一層，相互重疊。

這就是動態規則和分而治之的區別。

三、分而治之算法常見應用

引用leetcode的幾道經典題目來強化分而治之算法。

1、leetcode 374：猜數字大小

（1）題意

這里附上原題鏈接

猜數字游戲的規則如下：

• 每輪游戲，我都會從 1 到 n 隨機選擇一個數字。 請你猜選出我選的是哪個數字。
• 如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了。

你可以通過調用一個預先定義好的接口 int guess(int num) 來獲取猜測結果，返回值一共有 3 種可能的情況（-1，1 或 0）：

• -1 ：我選出的數字比你猜的數字小 pick < num 。
• 1 ：我選出的數字比你猜的數字大 pick > num 。
• 0 ：我選出的數字和你猜的數字一樣。恭喜！你猜對了！pick == num 。

返回我選出的數字。

（2）解題思路

• 二分搜索，同樣具備“分、解、合”的特性。
• 考慮選擇分而治之。

（3）解題步驟

• 分：計算中間元素，分割數組。
• 解：遞歸地在較大或者較小的數組進行二分搜索。
• 合：不需要此步，因為在子數組中搜到就返回了。

（4）代碼實現

/** * Forward declaration of guess API.* @param {number} num your guess* @return -1 if num is lower than the guess number* 1 if num is higher than the guess number* otherwise return 0* var guess = function(num) {}*//*** @param {number} n* @return {number}*/ let guessNumber = function(n) {const rec = (low, high) => {if(low > high){return;}// 1.計算中間元素，分割數組const mid = Math.floor((low + high) / 2);// 2.與猜測的數字進行比較const res = guess(mid);// 3.遞歸地在較大或者較小子數組進行二分搜索if(res === 0){return mid;}else if(res === 1){return rec(mid + 1, high);}else{return rec(low, mid - 1);}}return rec(1, n); };

2、leetcode 226：翻轉二叉樹

（1）題意

這里附上原題鏈接

翻轉一棵二叉樹。

（2）解題思路

• 先翻轉左右子樹，再將子樹換個位置。
• 符合“分、解、合”特性。
• 考慮選擇分而治之。

（3）解題步驟

• 分：獲取左右子樹。
• 解：遞歸地翻轉左右子樹。
• 合：將翻轉后的左右子樹換個位置放到根節點上。

（4）代碼實現

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/ /*** @param {TreeNode} root* @return {TreeNode}*/var invertTree = function(root) {if(!root){return null;}return{//1.根節點值不變val:root.val,//2.遞歸地將左子樹與右子樹結點變換left:invertTree(root.right),//3.遞歸地將右子樹與左子樹結點變換right:invertTree(root.left)} };

3、leetcode 100：相同的樹

（1）題意

這里附上原題鏈接

給你兩棵二叉樹的根節點 p 和 q ，編寫一個函數來檢驗這兩棵樹是否相同。

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

（2）解題思路

• 兩棵樹：根節點的值相同，左子樹相同，右子樹相同。
• 符合“分、解、合”特性。
• 考慮選擇分而治之。

（3）解題步驟

• 分：獲取兩棵樹的左子樹和右子樹。
• 解：遞歸地判斷兩棵樹的左子樹是否相同，右子樹是否相同。
• 合：將上述結果合并，如果根節點的值也相同，兩棵樹就相同。

（4）代碼實現

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/ /*** @param {TreeNode} p* @param {TreeNode} q* @return {boolean}*/ let isSameTree = function(p, q) {if(!p && !q){return true;}/*** 判斷條件：* 1.p樹和q樹同時存在；* 2.每遍歷一個節點，兩棵樹的節點值都存在；* 3.遞歸左子樹，比較每個節點值；* 4.遞歸右子樹，比較每個節點值。*/if(p && q && p.val === q.val &&isSameTree(p.left, q.left) &&isSameTree(p.right, q.right)){return true;}return false; };

4、leetcode 101：對稱二叉樹

（1）題意

這里附上原題鏈接

給定一個二叉樹，檢查它是否是鏡像對稱的。

（2）解題思路

• 轉化為：左右子樹是否鏡像。
• 分解為：樹1的左子樹和樹2的右子樹是否鏡像，樹1的右子樹和樹2的左子樹是否鏡像。
• 符合“分、解、合”特性，考慮選擇分而治之。

（3）解題步驟

• 分：獲取兩棵樹的左子樹和右子樹。
• 解：遞歸地判斷樹1的左子樹和樹2的右子樹是否鏡像，樹1的右子樹和樹2的左子樹是否鏡像。
• 合：如果上述成立，且根節點值也相同，兩棵樹就鏡像。

（4）代碼實現

let isSymmetric = function(root){if(!root){return true;}const isMirror = (l, r) => {if(!l && !r){return true;}/*** 判斷條件：* 1.左子樹和右子樹同時存在；* 2.左子樹和右子樹的根節點相同；* 3.左子樹的左節點和右子樹的右節點鏡像相同；* 4.左子樹的右結點和右子樹的左結點鏡像相同*/if(l && r && l.val === r.val &&isMirror(l.left, r.right) &&isMirror(l.right, r.left)){return true;}return false;}return isMirror(root.left, root.right); }

四、動態規則算法常見應用

引用leetcode的幾道經典題目來強化動態規則算法。

1、leetcode 70：爬樓梯

（1）題意

這里附上原題鏈接

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

**注意：**給定 n 是一個正整數。

（2）解題思路

• 爬到第n階可以在第n - 1階爬1個臺階，或者在第n - 2階爬2個臺階。
• F(n) = F(n - 1) + F(n - 2)。
• 使用動態規則。

（3）解題步驟

• 定義子問題：F(n) = F(n - 1) + F(n - 2)。
• 反復執行：從2循環到n，執行上述公式。

（4）代碼實現

/** @param {number} n* @return {number}*/ // 數組方法 var climbStairs = function(n) {if(n < 2){return 1;}// 記錄第0階和第1階可以走多少步const dp = [1, 1];// 從第2階開始遍歷，直至第5階for(let i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n]; };

如果dp用一維數組來記錄的話，時間復雜度和空間復雜度都為O(n)，這樣子的話效率還是偏低的。

那么有什么方法可以來降低它的復雜度呢？

可以采用變量的方法。從上面的代碼中我們可以看出，dp的值用一個數組存著，一直在線性增長。那么這個時候我們可以考慮把這個一維數組變換成單變量的形式，不斷進行替換，來降低空間復雜度。

下面用代碼實現一遍。

let climbStairs2 = function(n){if(n < 2){return 1;}//定義一個變量，記錄 n - 2 時的臺階數let dp0 = 1;//定義一個變量，記錄 n - 1 時的臺階數let dp1 = 1;for(let i = 2; i <= n; i++){const temp = dp0;//每遍歷一次，就讓dp0指向下一個數的值，即dp1dp0 = dp1;//每遍歷一次，就讓dp1指向dp1下一個數的值，即前兩個數的和，也就是dp1和原來dp0的值dp1 = dp1 + temp;}return dp1; }

從上面的代碼中可以看出，沒有了數組或者像矩陣一樣線性增長的數組，空間復雜度就變為了O(1)。

2、leetcode 198：打家劫舍

（1）題意

這里附上原題鏈接

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。

（2）解題思路

• f(k) = 從前k個房屋中能偷竊到的最大數額。
• Ak = 第k個房屋的錢數。
• f(k) = max(f(k - 2) + Ak, f(k - 1))。
• 考慮使用動態規則。

（3）解題步驟

• 定義子問題：f(k) = max(f(k - 2) + Ak, f(k - 1))。
• 反復執行：從2循環到n，執行上述公式。

（4）代碼實現

/*** @param {number[]} nums* @return {number}*/let rob1 = function(nums) {if(nums.length === 0){return 0;}// 前0個房屋和前1個房屋能劫持到的金錢數const dp = [0,nums[0]];for(let i = 2; i <= nums.length; i++){dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);}return dp[nums.length]; };

與爬樓梯同樣，如果dp用一維數組來記錄的話，時間復雜度和空間復雜度都為O(n)，這樣子的話效率還是偏低的。

那這個時候就可以采用單變量的方法，來降低空間復雜度。

下面用代碼實現一遍。

let rob2 = function(nums) {if(nums.length === 0){return 0;}let dp0 = 0;let dp1 = nums[0];for(let i = 2; i <= nums.length; i++){const dp2 = Math.max(dp0 + nums[i - 1], dp1);dp0 = dp1;dp1 = dp2;}return dp1; };

此時空間復雜度自然也就變為O(1)了。

3、leetcode 62：不同路徑

（1）題意

這里附上原題鏈接

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。

問總共有多少條不同的路徑？

（2）解題思路

• 每一步只能向下或者向右移動一步，因此想要走到(i,j)，如果向下走一步，那么從(i-1,j)走過來；如果向右走一步，那么從(i,j-1)走過來。
• f(i, j) = f(i-1, j) + f(i, j-1)。
• 使用動態規則。

（3）解題步驟

• 定義子問題：f(i, j) = f(i-1, j) + f(i, j-1)。
• 反復執行：從2循環到n，執行上述公式。

（4）代碼實現

let uniquePaths = function(m, n){const f = new Array(m).fill(0).map(() => new Array(n).fill(0));for(let i = 0; i < m; i++){// 將第一列全部補上1f[i][0] = 1;}for(let j = 0; j < n; j++){// 將第一行全部補上1f[0][j] = 1;}for(let i = 1; i < m; i++){for(let j = 1; j < n; j++){f[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[m - 1][n - 1]; }

五、結束語

分而治之和動態規則算法在前端中的應用還是挺多的，特別是在面試或筆試的時候會經常出現這類題目，大家可以在此之外再繼續多刷刷此類 leetcode 的題，做多了慢慢就能舉一反三了~

• 關注公眾號 星期一研究室 ，第一時間關注學習干貨，更多有趣的專欄待你解鎖~
• 如果這篇文章對你有用，記得點個贊加個關注再走哦~
• 我們下期見！🥂🥂🥂

總結

以上是生活随笔為你收集整理的一文了解分而治之和动态规则算法在前端中的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。