一文了解貪心算法和回溯算法在前端中的應用

• 一、貪心算法
• • 1、貪心算法是什么？
  • 2、應用場景
  • 3、場景剖析：零錢兌換
• 二、回溯算法
• • 1、回溯算法是什么？
  • 2、什么問題適合選用回溯算法解決？
  • 2、應用場景
  • 3、場景剖析：全排列
• 三、貪心算法常見應用
• • 1、leetcode 455：分發餅干
  • 2、leetcode 122：買賣股票的最佳時機
• 四、回溯算法常見應用
• • 1、leetcode 46：全排列
  • 2、leetcode 78：子集
• 五、寫在最后

在我們日常的生活中，經常會碰到貪心算法和回溯算法的應用場景。比如，貪心算法常應用于最少硬幣找零問題，分數背包等問題。而回溯算法常用于迷宮求解、N皇后等問題。這兩種各有各的優點，也各有各的不足。

在下面的這篇文章中，將講解貪心算法和回溯算法的常見應用場景，以及分析高頻 leetcode 算法題。

一起來學習⑧📖

一、貪心算法

1、貪心算法是什么？

• 貪心算法是算法設計中的一種方法。
• 期盼通過每個階段的局部最優選擇，從而達到全局的最優。
• 結果不一定最優。

2、應用場景

• 最少硬幣找零問題
• 分數背包問題
• ……

3、場景剖析：零錢兌換

先用一張圖來描述輸入輸出結果。

從上圖中可以看到，如果用貪心算法解決零錢兌換問題的話，它會先從最大面額的硬幣開始，拿盡可能多的這種硬幣找零。當無法再拿更多這種價值的硬幣時，開始拿第二大價值的硬幣，依次繼續。

大家可以發現，如果是第一種情況，確實可以達到理論最優。但是如果是第二種情況的話，還有一種更優的解法，那就是6 = 3 + 3。所以說，貪心算法并不總是能得到最優答案。

但是呢，雖說不能總是能得到最優答案，那我們為什么還有用它呢？

比起動態規則算法而言，貪心算法更簡單、更快。雖然它并不總是能得到最優的答案，但是綜合來看，它相對執行時間來說，輸出了一個可以接受的解。

二、回溯算法

1、回溯算法是什么？

• 回溯算法是算法設計中的一種方法。
• 回溯算法是一種漸進式尋找并構建問題解決方式的策略。
• 回溯算法會先從一個可能的動作開始解決問題，如果不行，就回溯選擇另一個動作，直到將問題解決。

2、什么問題適合選用回溯算法解決？

• 有很多路。
• 這些路里面，有死路，有活路。
• 通常需要遞歸來模擬所有的路。

2、應用場景

• 迷宮老鼠問題
• 數獨解題器
• 騎士巡邏問題
• N皇后問題
• ……

3、場景剖析：全排列

先用一張圖來戰術輸入輸出的過程。

從上圖中可以看到，全排列 [1, 2, 3] 三個元素，在遞歸的過程中會有很多種結果，比如說[1, 1, 2]，[1, 2, 1], [1, 2, 2]之類的結果。那么，當出現重復元素的時候，就會出現死路，這個時候就應該回退回去并去尋找下一條路活路走出去。這就是回溯算法要解決的問題。

三、貪心算法常見應用

引用leetcode的幾道經典題目來強化貪心算法。

1、leetcode 455：分發餅干

（1）題意

這里附上原題鏈接

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。

輸入輸出示例：

• 輸入: g = [1,2,3], s = [1,1]
• 輸出: 1
• 解釋:
  • 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
  • 雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
  • 所以你應該輸出1。

（2）解題思路

• 既能滿足孩子，還消耗最少。
• 先將“較小的餅干”分給“胃口較小”的孩子。

（3）解題步驟

• 對餅干數組和胃口數組升序降序。
• 遍歷餅干數組，找到能滿足第一個孩子的餅干。
• 然后繼續遍歷餅干數組，找到能滿足第二、三、四、……、n個孩子的餅干。

（4）代碼實現

/*** @param {number[]} g 孩子胃口* @param {number[]} s 餅干尺寸* @return {number}*/ let findContentChildren = function(g, s) {// 實現升序排序const sortFunc = function(a, b){return a-b;}//對g進行升序排序，即從小到大排序g.sort(sortFunc);//對s進行升序排序，即從小到大排序s.sort(sortFunc);//定義初始值，記錄餅干能滿足多少個孩子let i = 0;//對排序后的餅干進行一一遍歷，并逐一與孩子的胃口比對，如果能滿足，則對i進行+1操作s.forEach(n => {if(n >= g[i]){i += 1;}});return i; };console.log(findContentChildren([1, 2], [1, 2, 3]));

2、leetcode 122：買賣股票的最佳時機

（1）題意

這里附上原題鏈接

給定一個數組 prices ，其中 prices[i] 是一支給定股票第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

輸入輸出示例：

• 輸入: prices = [7,1,5,3,6,4]
• 輸出: 7
• 解釋:
  • 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
  • 隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

（2）解題思路

• 前提：上帝視角，知道未來的價格。
• 局部最優：建好就收，見差就不動，不做長遠打算。

（3）解題步驟

• 新建一個變量，用來統計總利潤。
• 遍歷價格數組，如果當前價格比昨天高，就是昨天買，今天賣，否則就不交易。
• 遍歷結束后，返回所有利潤之和。

（4）代碼實現

/*** @param {number[]} prices* @return {number}*/ let maxProfit = function(prices) {//新建一個變量，用來統計總利潤let profit = 0;//遍歷價格數組for(let i = 1; i < prices.length; i++){//如果當前價格prices[i]比昨天prices[i - 1]高，就是昨天買，今天賣；//否則說明當前天數沒買，不進行交易if(prices[i] > prices[i - 1]){//遍歷過程中，不斷對利潤進行相加profit += prices[i] - prices[i-1];}}//遍歷結束后，返回所有利潤之和return profit; };console.log(maxProfit([7, 5, 4, 7]));

四、回溯算法常見應用

引用leetcode的幾道經典題目來強化回溯算法。

1、leetcode 46：全排列

（1）題意

這里附上原題鏈接

給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

輸入輸出示例：

• 輸入: nums = [1,2,3]
• 輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

（2）解題思路

• 要求：①所有排列情況；②沒有重復元素。
• 有出路、有死路。
• 考慮回溯算法。

（3）解題步驟

• 用遞歸模擬出所有情況。
• 遇到包含重復元素的情況，就回溯。
• 收集所有到達遞歸終點的情況，并返回。

（4）代碼實現

/*** @param {number[]} nums* @return {number[][]}*/ let permute = function(nums) {// 1.定義一個變量，收集所有結果的情況const res = [];const backtrack = (path) => {// 4.遞歸的重點收集所有滿足題目要求的數組if(path.length === nums.length){res.push(path);return;}nums.forEach(n => {// 3.在把元素放進去時該數組已有此元素，那么此路為死路if(path.includes(n)){return;}backtrack(path.concat(n));});};// 2.遞歸時傳入一個數組backtrack([]);return res; };console.log(permute([1, 2, 3]));

2、leetcode 78：子集

（1）題意

這里附上原題鏈接

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

輸入輸出示例：

• 輸入: nums = [1,2,3]
• 輸出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

（2）解題思路

• 要求：①所有子集；②沒有重復元素。
• 有出路、有死路。
• 考慮使用回溯算法。

（3）解題步驟

• 用遞歸模擬出所有情況。
• 保證接的數字都是后面的數字。
• 收集所有到達遞歸終點的情況，并返回。

（4）代碼實現

/*** @param {number[]} nums* @return {number[][]}*/var subsets = function(nums) {//1.定義一個變量，存放結果const res = [];const backtrack = (path, l, start) => {// 4.到達路徑終點時，push到結果里面if(path.length === l){res.push(path);return;}//3.不斷遍歷數組，并將其添加到path中for(let i = start; i < nums.length; i++){backtrack(path.concat(nums[i]), l, i + 1);}}//2.子集的長度有可能是0-nums.length不等for(let i = 0; i <= nums.length; i++){// 三個參數分別指：路徑,路徑數組的長度,起始的下標backtrack([], i, 0);}return res; };console.log(subsets([1, 2, 3]));

五、寫在最后

貪心算法和回溯算法在前端的面試和筆試中也是非常經典的常考題。貪心算法相較于其他算法來說比較簡單，而回溯算法涉及到很多溯回問題，邏輯較強，建議大家在做題目時如果看不懂的情況下可以選擇多調試代碼，一步一步跟著它的思路，多調試幾遍，慢慢就能深入理解其邏輯了。

貪心算法和回溯算法在前端中的應用就講到這里啦！如有不理解或文章有誤歡迎評論區留言或私信我交流~

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

總結

以上是生活随笔為你收集整理的一文了解贪心算法和回溯算法在前端中的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

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