自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

開(kāi)發(fā) 前端 算法
對(duì)于回溯算法的定義,百度百科上是這樣描述的:回溯算法實(shí)際上一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程,主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解,當(dāng)發(fā)現(xiàn)已不滿(mǎn)足求解條件時(shí),就“回溯”返回,嘗試別的路徑。

什么叫回溯算法

對(duì)于回溯算法的定義,百度百科上是這樣描述的:回溯算法實(shí)際上一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程,主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解,當(dāng)發(fā)現(xiàn)已不滿(mǎn)足求解條件時(shí),就“回溯”返回,嘗試別的路徑?;厮莘ㄊ且环N選優(yōu)搜索法,按選優(yōu)條件向前搜索,以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí),發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo),就退回一步重新選擇,這種走不通就退回再走的技術(shù)為回溯法,而滿(mǎn)足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為“回溯點(diǎn)”。許多復(fù)雜的,規(guī)模較大的問(wèn)題都可以使用回溯法,有“通用解題方法”的美稱(chēng)。

看明白沒(méi),回溯算法其實(shí)就是一個(gè)不斷探索嘗試的過(guò)程,探索成功了也就成功了,探索失敗了就在退一步,繼續(xù)嘗試……,

組合總和

組合總和算是一道比較經(jīng)典的回溯算法題,其中有一道題是這樣的。

找出所有相加之和為 n 的 k 個(gè)數(shù)的組合。組合中只允許含有 1 - 9 的正整數(shù),并且每種組合中不存在重復(fù)的數(shù)字。

說(shuō)明:

  • 所有數(shù)字都是正整數(shù)。
  • 解集不能包含重復(fù)的組合。

示例 1:

  • 輸入: k = 3, n = 7
  • 輸出: [[1,2,4]]

示例 2:

  • 輸入: k = 3, n = 9
  • 輸出: [[1,2,6], [1,3,5], [2,3,4]]

這題說(shuō)的很明白,就是從1-9中選出k個(gè)數(shù)字,他們的和等于n,并且這k個(gè)數(shù)字不能有重復(fù)的。所以第一次選擇的時(shí)候可以從這9個(gè)數(shù)字中任選一個(gè),沿著這個(gè)分支走下去,第二次選擇的時(shí)候還可以從這9個(gè)數(shù)字中任選一個(gè),但因?yàn)椴荒苡兄貜?fù)的,所以要排除第一次選擇的,第二次選擇的時(shí)候只能從剩下的8個(gè)數(shù)字中選一個(gè)……。這個(gè)選擇的過(guò)程就比較明朗了,我們可以把它看做一棵9叉樹(shù),除葉子結(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都有9個(gè)子節(jié)點(diǎn),也就是下面這樣

 

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

從9個(gè)數(shù)字中任選一個(gè),就是沿著他的任一個(gè)分支一直走下去,其實(shí)就是DFS(如果不懂DFS的可以看下373,數(shù)據(jù)結(jié)構(gòu)-6,樹(shù)),二叉樹(shù)的DFS代碼是下面這樣的

  1. public static void treeDFS(TreeNode root) { 
  2.     if (root == null
  3.         return
  4.     System.out.println(root.val); 
  5.     treeDFS(root.left);    treeDFS(root.right);} 

這里可以仿照二叉樹(shù)的DFS來(lái)寫(xiě)一下9叉樹(shù),9叉樹(shù)的DFS就是通過(guò)遞歸遍歷他的9個(gè)子節(jié)點(diǎn),代碼如下

  1. public static void treeDFS(TreeNode root) { 
  2.     //遞歸必須要有終止條件 
  3.     if (root == null
  4.         return
  5.     System.out.println(root.val);    //通過(guò)循環(huán),分別遍歷9個(gè)子樹(shù) 
  6.     for (int i = 1; i <= 9; i++) { 
  7.         //2,一些操作,可有可無(wú),視情況而定 
  8.         treeDFS("第i個(gè)子節(jié)點(diǎn)"); 
  9.         //3,一些操作,可有可無(wú),視情況而定 
  10.     }} 

DFS其實(shí)就相當(dāng)于遍歷他的所有分支,就是列出他所有的可能結(jié)果,只要判斷結(jié)果等于n就是我們要找的,那么這棵9叉樹(shù)最多有多少層呢,因?yàn)橛衚個(gè)數(shù)字,所以最多只能有k層。來(lái)看下代碼

  1. public List<List<Integer>> combinationSum3(int k, int n) { 
  2.     List<List<Integer>> res = new ArrayList<>(); 
  3.     dfs(res, new ArrayList<>(), k, 1, n); 
  4.     return res; 
  5. }private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { 
  6.     //終止條件,如果滿(mǎn)足這個(gè)條件,再往下找也沒(méi)什么意義了 
  7.     if (list.size() == k || n <= 0) { 
  8.         //如果找到一組合適的就把他加入到集合list中 
  9.         if (list.size() == k && n == 0) 
  10.             res.add(new ArrayList<>(list)); 
  11.         return
  12.     } 
  13.     //通過(guò)循環(huán),分別遍歷9個(gè)子樹(shù) 
  14.     for (int i = start; i <= 9; i++) { 
  15.         //選擇當(dāng)前值 
  16.         list.add(i); 
  17.         //遞歸 
  18.         dfs(res, list, k, i + 1, n - i); 
  19.         //撤銷(xiāo)選擇 
  20.         list.remove(list.size() - 1); 
  21.     } 

代碼相對(duì)來(lái)說(shuō)還是比較簡(jiǎn)單的,我們來(lái)分析下(如果看懂了可以直接跳過(guò))。

  1. 代碼dfs中最開(kāi)始的地方是終止條件的判斷,之前在426,什么是遞歸,通過(guò)這篇文章,讓你徹底搞懂遞歸中講過(guò),遞歸必須要有終止條件。
  2. 下面的for循環(huán)分別遍歷他的9個(gè)子節(jié)點(diǎn),注意這里的i是從start開(kāi)始的,所以有可能還沒(méi)有9個(gè)子樹(shù),前面說(shuō)過(guò),如果從9個(gè)數(shù)字中選擇一個(gè)之后,第2次就只能從剩下的8個(gè)選擇了,第3次就只能從剩下的7個(gè)中選擇了……
  3. 在第20行dsf中的start是i+1,這里要說(shuō)一下為什么是i+1。比如我選擇了3,下次就應(yīng)該從4開(kāi)始選擇,如果不加1,下次還從3開(kāi)始就出現(xiàn)了數(shù)字重復(fù),明顯與題中的要求不符
  4. for循環(huán)的i為什么不能每次都從1開(kāi)始,如果每次都從1開(kāi)始就會(huì)出現(xiàn)結(jié)果重復(fù),比如選擇了[1,2],下次可能就會(huì)選擇[2,1]。
  5. 如果對(duì)回溯算法不懂的,可能最不容易理解的就是最后一行,為什么要撤銷(xiāo)選擇。如果經(jīng)??次夜娞?hào)的同學(xué)可能知道,也就是我經(jīng)常提到的分支污染問(wèn)題,因?yàn)閘ist是引用傳遞,當(dāng)從一個(gè)分支跳到另一個(gè)分支的時(shí)候,如果不把前一個(gè)分支的數(shù)據(jù)給移除掉,那么list就會(huì)把前一個(gè)分支的數(shù)據(jù)帶到下一個(gè)分支去,造成結(jié)果錯(cuò)誤(下面會(huì)講)。那么除了把前一個(gè)分支的數(shù)據(jù)給移除以外還有一種方式就是每個(gè)分支都創(chuàng)建一個(gè)list,這樣每個(gè)分支都是一個(gè)新的list,都不互相干擾,也就是下面圖中這樣

 

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

代碼如下

  1. public List<List<Integer>> combinationSum3(int k, int n) { 
  2.     List<List<Integer>> res = new ArrayList<>(); 
  3.     dfs(res, new ArrayList<>(), k, 1, n); 
  4.     return res; 
  5. }private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { 
  6.     //終止條件,如果滿(mǎn)足這個(gè)條件,再往下找也沒(méi)什么意義了 
  7.     if (list.size() == k || n <= 0) { 
  8.         //如果找到一組合適的就把他加入到集合list中 
  9.         if (list.size() == k && n == 0) 
  10.             res.add(new ArrayList<>(list)); 
  11.         return
  12.     } 
  13.     //通過(guò)循環(huán),分別遍歷9個(gè)子樹(shù) 
  14.     for (int i = start; i <= 9; i++) { 
  15.         //創(chuàng)建一個(gè)新的list,和原來(lái)的list撇清關(guān)系,對(duì)當(dāng)前l(fā)ist的修改并不會(huì)影響到之前的list 
  16.         List<Integer> subList = new LinkedList<>(list); 
  17.         subList.add(i); 
  18.         //遞歸 
  19.         dfs(res, subList, k, i + 1, n - i); 
  20.         //注意這里沒(méi)有撤銷(xiāo)的操作,因?yàn)槭窃谝粋€(gè)新的list中的修改,原來(lái)的list并沒(méi)有修改, 
  21.         //所以不需要撤銷(xiāo)操作 
  22.     } 

我們看到最后并沒(méi)有撤銷(xiāo)的操作,這是因?yàn)槊總€(gè)分支都是一個(gè)新的list,你對(duì)當(dāng)前分支的修改并不會(huì)影響到其他分支,所以并不需要撤銷(xiāo)操作。

注意:大家盡量不要寫(xiě)這樣的代碼,這種方式雖然也能解決,但每個(gè)分支都會(huì)重新創(chuàng)建list,效率很差。

要搞懂最后一行代碼首先要明白什么是遞歸,遞歸分為遞和歸兩部分,遞就是往下傳遞,歸就是往回走。遞歸你從什么地方調(diào)用最終還會(huì)回到什么地方去,我們來(lái)畫(huà)個(gè)簡(jiǎn)單的圖看一下

 

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

這是一棵非常簡(jiǎn)單的3叉樹(shù),假如要對(duì)他進(jìn)行DFS遍歷,當(dāng)沿著1→2這條路徑走下去的時(shí)候,list中應(yīng)該是[1,2]。因?yàn)槭沁f歸調(diào)用最終還會(huì)回到節(jié)點(diǎn)1,如果不把2給移除掉,當(dāng)沿著1→4這個(gè)分支走下去的時(shí)候就變成[1,2,4],但實(shí)際上1→4這個(gè)分支的結(jié)果應(yīng)該是[1,4],這是因?yàn)槲覀儼亚耙粋€(gè)分支的值給帶過(guò)來(lái)了。當(dāng)1,2這兩個(gè)節(jié)點(diǎn)遍歷完之后最終還是返回節(jié)點(diǎn)1,在回到節(jié)點(diǎn)1的時(shí)候就應(yīng)該把結(jié)點(diǎn)2的值給移除掉,讓list變?yōu)閇1],然后再沿著1→4這個(gè)分支走下去,結(jié)果就是[1,4]。

我們來(lái)總結(jié)一下回溯算法的代碼模板吧

  1. private void backtrack("原始參數(shù)") { 
  2.     //終止條件(遞歸必須要有終止條件) 
  3.     if ("終止條件") { 
  4.         //一些邏輯操作(可有可無(wú),視情況而定) 
  5.         return
  6.     }    for (int i = "for循環(huán)開(kāi)始的參數(shù)"; i < "for循環(huán)結(jié)束的參數(shù)"; i++) { 
  7.         //一些邏輯操作(可有可無(wú),視情況而定) 
  8.         //做出選擇 
  9.         //遞歸 
  10.         backtrack("新的參數(shù)"); 
  11.         //一些邏輯操作(可有可無(wú),視情況而定) 
  12.         //撤銷(xiāo)選擇 
  13.     } 

有了模板,回溯算法的代碼就非常容易寫(xiě)了,下面就根據(jù)模板來(lái)寫(xiě)幾個(gè)經(jīng)典回溯案例的答案。

八皇后問(wèn)題

八皇后問(wèn)題也是一道非常經(jīng)典的回溯算法題,前面也有對(duì)八皇后問(wèn)題的專(zhuān)門(mén)介紹,有不明白的可以先看下394,經(jīng)典的八皇后問(wèn)題和N皇后問(wèn)題。他就是不斷的嘗試,如果當(dāng)前位置能放皇后就放,一直到最后一行如果也能放就表示成功了,如果某一個(gè)位置不能放,就回到上一步重新嘗試。比如我們先在第1行第1列放一個(gè)皇后,如下圖所示

 

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

然后第2行從第1列開(kāi)始在不沖突的位置再放一個(gè)皇后,然后第3行……一直這樣放下去,如果能放到第8行還不沖突說(shuō)明成功了,如果沒(méi)到第8行的時(shí)候出現(xiàn)了沖突就回到上一步繼續(xù)查找合適的位置……來(lái)看下代碼

  1. //row表示的是第幾行 
  2. public void solve(char[][] chess, int row) { 
  3.     //終止條件,row是從0開(kāi)始的,最后一行都可以放,說(shuō)明成功了    if (row == chess.length) {        //自己寫(xiě)的一個(gè)公共方法,打印二維數(shù)組的,        //主要用于測(cè)試數(shù)據(jù)用的        Util.printTwoCharArrays(chess);        System.out.println();        return;    }    for (int col = 0; col < chess.length; col++) { 
  4.         //驗(yàn)證當(dāng)前位置是否可以放皇后 
  5.         if (valid(chess, row, col)) { 
  6.             //如果在當(dāng)前位置放一個(gè)皇后不沖突, 
  7.             //就在當(dāng)前位置放一個(gè)皇后 
  8.             chess[row][col] = 'Q'
  9.             //遞歸,在下一行繼續(xù)…… 
  10.             solve(chess, row + 1); 
  11.             //撤銷(xiāo)當(dāng)前位置的皇后 
  12.             chess[row][col] = '.'
  13.         } 
  14.     } 

全排列問(wèn)題

給定一個(gè)沒(méi)有重復(fù)數(shù)字的序列,返回其所有可能的全排列。

  • 示例:
  • 輸入: [1,2,3]
  • 輸出:

 

  1.  
  2. [1,2,3],  
  3. [1,3,2],  
  4. [2,1,3],  
  5. [2,3,1],  
  6. [3,1,2],  
  7. [3,2,1]  

這道題我們可以把它當(dāng)做一棵3叉樹(shù),所以每一步都會(huì)有3種選擇,具體過(guò)程就不在分析了,直接根據(jù)上面的模板來(lái)寫(xiě)下代碼

  1. public List<List<Integer>> permute(int[] nums) { 
  2.     List<List<Integer>> list = new ArrayList<>(); 
  3.     backtrack(list, new ArrayList<>(), nums); 
  4.     return list; 
  5. }private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) { 
  6.     //終止條件 
  7.     if (tempList.size() == nums.length) { 
  8.         //說(shuō)明找到一一組組合 
  9.         list.add(new ArrayList<>(tempList)); 
  10.         return
  11.     } 
  12.     for (int i = 0; i < nums.length; i++) { 
  13.         //因?yàn)椴荒苡兄貜?fù)的,所以有重復(fù)的就不能選 
  14.         if (tempList.contains(nums[i])) 
  15.             continue
  16.         //選擇當(dāng)前值 
  17.         tempList.add(nums[i]); 
  18.         //遞歸 
  19.         backtrack(list, tempList, nums); 
  20.         //撤銷(xiāo)選擇 
  21.         tempList.remove(tempList.size() - 1); 
  22.     } 

是不是感覺(jué)很簡(jiǎn)單。

子集問(wèn)題

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums,返回該數(shù)組所有可能的子集(冪集)。

  • 說(shuō)明:解集不能包含重復(fù)的子集。
  • 示例:
  • 輸入: nums = [1,2,3]
  • 輸出:

 

  1. 輸入: nums = [1,2,3] 
  2. 輸出: 
  3. [3], 
  4. [1], 
  5. [2], 
  6. [1,2,3], 
  7. [1,3], 
  8. [2,3], 
  9. [1,2], 
  10. [] 

我們還是根據(jù)模板來(lái)修改吧

  1. public List<List<Integer>> subsets(int[] nums) { 
  2.     List<List<Integer>> list = new ArrayList<>(); 
  3.     //先排序 
  4.     Arrays.sort(nums); 
  5.     backtrack(list, new ArrayList<>(), nums, 0); 
  6.     return list; 
  7. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) { 
  8.     //注意這里沒(méi)有寫(xiě)終止條件,不是說(shuō)遞歸一定要有終止條件的嗎,這里怎么沒(méi)寫(xiě),其實(shí)這里的終止條件 
  9.     //隱含在for循環(huán)中了,當(dāng)然我們也可以寫(xiě)if(start>nums.length) rerurn;只不過(guò)這里省略了。 
  10.     list.add(new ArrayList<>(tempList)); 
  11.     for (int i = start; i < nums.length; i++) { 
  12.         //做出選擇 
  13.         tempList.add(nums[i]); 
  14.         //遞歸 
  15.         backtrack(list, tempList, nums, i + 1); 
  16.         //撤銷(xiāo)選擇 
  17.         tempList.remove(tempList.size() - 1); 
  18.     } 

所以類(lèi)似這種題基本上也就是這個(gè)套路,就是先做出選擇,然后遞歸,最后再撤銷(xiāo)選擇。在講第一道示例的時(shí)候提到過(guò)撤銷(xiāo)的原因是防止把前一個(gè)分支的結(jié)果帶到下一個(gè)分支造成結(jié)果錯(cuò)誤。不過(guò)他們不同的是,一個(gè)是終止條件的判斷,還一個(gè)就是for循環(huán)的起始值,這些都要具體問(wèn)題具體分析。下面再來(lái)看最后一到題解數(shù)獨(dú)。

解數(shù)獨(dú)

數(shù)獨(dú)大家都玩過(guò)吧,他的規(guī)則是這樣的

一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則:

  • 數(shù)字 1-9 在每一行只能出現(xiàn)一次。
  • 數(shù)字 1-9 在每一列只能出現(xiàn)一次。
  • 數(shù)字 1-9 在每一個(gè)以粗實(shí)線(xiàn)分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

過(guò)程就不在分析了,直接看代碼,代碼中也有詳細(xì)的注釋?zhuān)@篇講的是回溯算法,這里主要看一下backTrace方法即可,其他的可以先不用看

  1. //回溯算法 
  2. public static boolean solveSudoku(char[][] board) { 
  3.     return backTrace(board, 0, 0); 
  4. }//注意這里的參數(shù),row表示第幾行,col表示第幾列。private static boolean backTrace(char[][] board, int row, int col) { 
  5.     //注意row是從0開(kāi)始的,當(dāng)row等于board.length的時(shí)候表示數(shù)獨(dú)的 
  6.     //最后一行全部讀遍歷完了,說(shuō)明數(shù)獨(dú)中的值是有效的,直接返回true 
  7.     if (row == board.length) 
  8.         return true
  9.     //如果當(dāng)前行的最后一列也遍歷完了,就從下一行的第一列開(kāi)始。這里的遍歷    //順序是從第1行的第1列一直到最后一列,然后第二行的第一列一直到最后 
  10.     //一列,然后第三行的……    if (col == board.length) 
  11.         return backTrace(board, row + 1, 0); 
  12.     //如果當(dāng)前位置已經(jīng)有數(shù)字了,就不能再填了,直接到這一行的下一列    if (board[row][col] != '.'
  13.         return backTrace(board, row, col + 1); 
  14.     //如果上面條件都不滿(mǎn)足,我們就從1到9中選擇一個(gè)合適的數(shù)字填入到數(shù)獨(dú)中 
  15.     for (char i = '1'; i <= '9'; i++) { 
  16.         //判斷當(dāng)前位置[row,col]是否可以放數(shù)字i,如果不能放再判斷下        //一個(gè)能不能放,直到找到能放的為止,如果從1-9都不能放,就會(huì)下面 
  17.         //直接return false 
  18.         if (!isValid(board, row, col, i)) 
  19.             continue;        //如果能放數(shù)字i,就把數(shù)字i放進(jìn)去        board[row][col] = i;        //如果成功就直接返回,不需要再?lài)L試了        if (backTrace(board, row, col)) 
  20.             return true
  21.         //否則就撤銷(xiāo)重新選擇        board[row][col] = '.'
  22.     }    //如果當(dāng)前位置[row,col]不能放任何數(shù)字,直接返回false 
  23.     return false
  24. }//驗(yàn)證當(dāng)前位置[row,col]是否可以存放字符cprivate static boolean isValid(char[][] board, int row, int col, char c) { 
  25.     for (int i = 0; i < 9; i++) { 
  26.         if (board[i][col] != '.' && board[i][col] == c) 
  27.             return false
  28.         if (board[row][i] != '.' && board[row][i] == c) 
  29.             return false
  30.         if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && 
  31.                 board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) 
  32.             return false
  33.     }    return true

總結(jié)

回溯算法要和遞歸結(jié)合起來(lái)就很好理解了,遞歸分為兩部分,第一部分是先往下傳遞,第二部分到達(dá)終止條件的時(shí)候然后再反彈往回走,我們來(lái)看一下階乘的遞歸

 

450,什么叫回溯算法,一看就會(huì),一寫(xiě)就廢

其實(shí)回溯算法就是在往下傳遞的時(shí)候把某個(gè)值給改變,然后往回反彈的時(shí)候再把原來(lái)的值復(fù)原即可。比如八皇后的時(shí)候我們先假設(shè)一個(gè)位置可以放皇后,如果走不通就把當(dāng)前位置給撤銷(xiāo),放其他的位置。如果是組合之類(lèi)的問(wèn)題,往下傳遞的時(shí)候我們把當(dāng)前值加入到list中,然后往回反彈的時(shí)候在把它從list中給移除掉即可。

責(zé)任編輯:未麗燕 來(lái)源: 今日頭條
相關(guān)推薦

2022-03-21 21:05:40

TypeScript語(yǔ)言API

2021-06-01 06:01:35

SSO單點(diǎn)登錄

2019-08-08 16:30:23

技術(shù)編程SpringBoot

2022-04-27 20:52:48

JSChrome元素

2021-01-21 00:06:26

vue.js語(yǔ)言開(kāi)發(fā)

2010-09-06 10:15:11

DB2打補(bǔ)丁

2020-03-27 09:06:54

選擇排序算法冒泡排序

2021-01-08 17:18:35

前端vuevue.js

2019-08-14 10:20:32

算法數(shù)組鏈表

2021-02-07 11:13:20

Windows 10Windows 10X微軟

2021-07-29 10:26:34

數(shù)據(jù)分析上云CIO

2021-10-20 06:47:50

Elasticsear場(chǎng)景引擎

2019-01-15 09:55:24

RAID磁盤(pán)陣列數(shù)據(jù)存儲(chǔ)

2010-01-27 13:54:52

IT電影

2024-12-12 08:22:03

負(fù)載均衡算法無(wú)狀態(tài)

2023-05-12 09:08:48

TypeScript工具類(lèi)型

2020-04-15 08:33:43

Netty網(wǎng)絡(luò)通信

2015-07-30 14:20:27

面試攻略

2020-09-21 08:33:12

線(xiàn)程池調(diào)度Thread Pool

2021-05-14 07:11:49

方法調(diào)用類(lèi)加載
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)