LeetCode算法题8：递归和回溯1
文章目錄
- 前言
- 回溯算法：
- 一、合并兩個有序鏈表(簡單，可略過)
- 迭代遍歷
- 一開始沒有想到的遞歸解法
- 二、反轉(zhuǎn)鏈表
- 迭代遍歷（頭插法）：
- 遞歸：
- 三、組合
- 回溯：
- 四、全排列
- 回溯（交換）：
- 回溯：
- 五、字母大小寫全排列
- 回溯：
- 總結(jié)
前言
??????Leetcode算法系列：https://leetcode-cn.com/study-plan/algorithms/?progress=njjhkd2
??????簡單總結(jié)一下遞歸回溯相關(guān)的算法題：
回溯算法：
??????回溯思想個人覺得還是挺好理解，但目前理解的還是不夠深|><|。以下摘自百度百科：
??????回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。八皇后問題就是回溯算法的典型，第一步按照順序放一個皇后，然后第二步符合要求放第2個皇后，如果沒有位置符合要求，那么就要改變第一個皇后的位置，重新放第2個皇后的位置，直到找到符合條件的位置就可以了。回溯在迷宮搜索中使用很常見，就是這條路走不通，然后返回前一個路口，繼續(xù)下一條路。回溯算法說白了就是窮舉法。不過回溯算法使用剪枝函數(shù)，剪去一些不可能到達(dá) 最終狀態(tài)（即答案狀態(tài)）的節(jié)點，從而減少狀態(tài)空間樹節(jié)點的生成。
??????回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。
一、合并兩個有序鏈表(簡單，可略過)
??????題目鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
??????題目描述：將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
迭代遍歷
??????直接采用歸并思想既可。參考算法如下：
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode realh=new ListNode(0);//自定義一個頭節(jié)點。ListNode tmp=realh;while(list1!=null&&list2!=null){if(list1.val<list2.val){tmp.next=list1;list1=list1.next;}else{tmp.next=list2;list2=list2.next;}tmp=tmp.next;}tmp.next=list1==null?list2:list1;return realh.next;}一開始沒有想到的遞歸解法
??????當(dāng)發(fā)現(xiàn)也可以采用遞歸來做的時候，試了一下，先做終止條件判斷，遞歸主體判斷當(dāng)前兩個結(jié)點值之間的大小，值小的結(jié)點需要返回，注意要在返回之前完成下一輪的遞歸合并。參考算法如下：
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null)return list2;if(list2==null)return list1;if(list1.val<list2.val){list1.next=merge(list1.next,list2);return list1;}else{list2.next=merge(list1,list2.next);return list2;}}二、反轉(zhuǎn)鏈表
??????題目鏈接：https://leetcode-cn.com/problems/reverse-linked-list/
??????題目描述：給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
迭代遍歷（頭插法）：
??????參考算法如下：
public ListNode reverseList(ListNode head) {if(head==null)return head;ListNode realh=new ListNode(0),tmp;//仍建立一個頭節(jié)點來保存最終的鏈表while(head!=null){tmp=head;//tmp 為待插入的結(jié)點，插入位置為 realh 的next處head=head.next; //插入之前需要保證下一次迭代元素訪問的正確性tmp.next=realh.next;realh.next=tmp;}return realh.next;}遞歸：
??????遞歸稍微有點難理解，可參考題解。下面算法的大體思路為：遞歸終止條件有兩個，當(dāng)前結(jié)點為 null 或當(dāng)前結(jié)點的 next 為 null。1，當(dāng)前結(jié)點為 null 僅針對 head 為一個空鏈表的情況，應(yīng)返回 null；2，當(dāng)前結(jié)點的 next 為 null 才是遞歸的終止條件。在對鏈表的遞歸遍歷中，每一層遞歸中，我們都可以順序的得到鏈表的每一個結(jié)點。
??????下面代碼做的是從從后往前將鏈表逆序，由于我們的終止條件，第一次調(diào)整指針是在倒數(shù)第二個結(jié)點 a處（假設(shè) a->next = b; b->next = null），此時可采用操作： a->next->next=a; a->next =null; 來將當(dāng)前僅有兩個元素的鏈表逆序。在原鏈表中依次往前，對倒數(shù)第三個結(jié)點、第四個…也是如此，最后返回結(jié)點 b 為新鏈表的第一個結(jié)點。
public ListNode reverseList(ListNode head) {if(head==null||head.next==null)return head;ListNode tmp=reverseList(head.next); //tmp 為原鏈表最后一個結(jié)點，新鏈表的第一個結(jié)點。head.next.next=head; //這兩行代碼從倒數(shù)第二個結(jié)點處開始調(diào)整結(jié)點的指向關(guān)系，一步步進(jìn)行逆序。head.next=null;return tmp;}??????目前僅有的粗淺印象為：從后往前對鏈表結(jié)點進(jìn)行操作需要將遞歸語句放在操作語句的前面；從前往后按照前后順序操作，需要將操作語句放在遞歸語句的前面。
三、組合
??????題目鏈接：https://leetcode-cn.com/problems/combinations/
??????題目描述：給定兩個整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合。
你可以按 任何順序 返回答案。
回溯：
??????可參考對應(yīng)的官方題解，初始的算法如下：
??????1：算法的退出條件代碼塊b放在保存合適的組合情況代碼塊a后面的原因在于代碼塊a在代碼塊c的前面，即先進(jìn)行訪問、判定操作，后進(jìn)行遞歸遍歷。對于 n,k = 4,2 的情況，在 start 為 5 的遞歸遍歷中，代碼塊 a 先判斷的是包含 4 的情況，然后再準(zhǔn)備添加 5。 若將代碼塊 b 放在 a 的前面，需要更改 b 中的 if 語句為 if(start>end+1)。
//對 n 個數(shù)的組合，假設(shè)每個數(shù)均有兩種狀態(tài)，選取和不選取，每一種成功的情況發(fā)生在選取的數(shù)有 k 個的情況，保存每一個可能的情況。List<List<Integer>> ans=new LinkedList<>();List<Integer> tmp=new LinkedList<>();public List<List<Integer>> combine(int n, int k) {solve(1,n,k);return ans;}public void solve(int start,int end,int k){if(tmp.size()==k){ //碰到每一種成功的情況時應(yīng)該保存 aans.add(new LinkedList<>(tmp));return;}//start == end，此時表示到達(dá)最后一個元素處 bif(start>end)return; //設(shè)置算法的退出條件tmp.add(start); //選取當(dāng)前值 start 的情況 c solve(start+1,end,k);tmp.remove(tmp.size()-1); //不選取的情況solve(start+1,end,k);}??????當(dāng) n=4，k=2 時的執(zhí)行結(jié)果如下（在 solve 方法的第一行添加 System.out.println(tmp);）：
????????????????????????????????????????????????[]
????????????????????????????????????????????????[1]
????????????????????????????????????????????????[1, 2]
????????????????????????????????????????????????[1]
????????????????????????????????????????????????[1, 3]
????????????????????????????????????????????????[1]
????????????????????????????????????????????????[1, 4]
????????????????????????????????????????????????[1]
????????????????????????????????????????????????[]
????????????????????????????????????????????????[2]
????????????????????????????????????????????????[2, 3]
????????????????????????????????????????????????[2]
????????????????????????????????????????????????[2, 4]
????????????????????????????????????????????????[2]
????????????????????????????????????????????????[]
????????????????????????????????????????????????[3]
????????????????????????????????????????????????[3, 4]
????????????????????????????????????????????????[3]
????????????????????????????????????????????????[]
????????????????????????????????????????????????[4]
????????????????????????????????????????????????[]
??????2：進(jìn)一步修改，添加剪枝條件并在此時可以刪除代碼塊 b 的算法參考如下：
??????現(xiàn)在我們知道，代碼塊 a 中判斷的元素范圍不包括當(dāng)前的 start ，而 end-start+1 表示還未添加進(jìn) tmp 集合的的剩余元素，如果 tmp 中元素數(shù)量加上剩余元素數(shù)量之和小于 k 的話，絕對不可能出現(xiàn)成功的情況，所以程序可直接返回，不需要進(jìn)行冗余的判斷。
??????并且在此時，代碼塊 b 可以刪除，它不會再被執(zhí)行。原因在于 b 針對的是當(dāng)前 tmp 元素數(shù)量達(dá)不到 k ，且即將要擴(kuò)大區(qū)間到 n+1 的時候，作為此時的邊界條件，程序應(yīng)該返回。
??????而新加的代碼塊 d，目的是為了避免沒必要的遞歸運算，即剪枝。那么 b 表示的返回條件是否被 d 囊括呢？答案是肯定的。假設(shè)對于 n=4，k=2 的情況，當(dāng)前 tmp 中的元素為 1，start 為 5 時，此時在 d 中程序直接就返回了（即代碼塊 b 的作用）。
??????b 針對的邊界條件：如果當(dāng)前 tmp 元素數(shù)量達(dá)不到 k ，且即將要擴(kuò)大區(qū)間到 n+1 的時候，此時 end-start+1 的值為 0，而 tmp.size() 又是小于 k 的，在 d 中程序也就直接返回了。 所以代碼塊 b 可刪除掉。
List<List<Integer>> ans=new LinkedList<>();List<Integer> tmp=new LinkedList<>();public List<List<Integer>> combine(int n, int k) {solve(1,n,k);return ans;}public void solve(int start,int end,int k){if(tmp.size()+(end-start+1)<k) dreturn;if(tmp.size()==k){ //碰到每一種成功的情況時應(yīng)該保存 aans.add(new LinkedList<>(tmp));return;} /*//start == end，此時表示到達(dá)最后一個元素處 bif(start>end)return; //設(shè)置算法的退出條件 */tmp.add(start); //選取當(dāng)前值 start 的情況 c solve(start+1,end,k);tmp.remove(tmp.size()-1); //不選取的情況solve(start+1,end,k);}四、全排列
??????題目鏈接：https://leetcode-cn.com/problems/permutations/
??????題目描述：給定一個不含重復(fù)數(shù)字的數(shù)組 nums ，返回其所有可能的全排列 。你可以 按任意順序 返回答案。
回溯（交換）：
??????先將初始數(shù)組保存到 tmp 列表中，方便直接采用 swap 方法來交換。大體思想是：假設(shè)數(shù)組元素為{1，2，3，4}，全排列的順序為：先得到以 1 開頭的所有排列，然后是 2，3，4；假如在以 1 開頭的排列中，先得到其余的 2，3，4開頭的排列；假如在以1 ，2 開頭的排列，分別得到 3，4 開頭的排列；假如在以 1，2，3開頭的排列中，最后一個數(shù)只能是 4。
ArrayList<Integer> tmp=new ArrayList<>();List<List<Integer>> ans=new LinkedList<List<Integer>>();//用交換的方法做！public List<List<Integer>> permute(int[] nums) {for (int num : nums)tmp.add(num);solve(0,nums.length-1);return ans;}public void solve(int cur,int end) {if (cur == end) {// cur 表示當(dāng)前的元素下標(biāo)ans.add(new ArrayList<>(tmp));return;}else{for(int i=cur;i<=end;i++){Collections.swap(tmp,cur,i);//交換solve(cur+1,end);Collections.swap(tmp,cur,i);//復(fù)位}}}回溯：
??????原文鏈接為對應(yīng)題解：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/ 不同于交換，這里為依次選擇每一個元素。見下圖：
??????對應(yīng)的代碼為（稍加修改后）：
五、字母大小寫全排列
??????題目鏈接：https://leetcode-cn.com/problems/letter-case-permutation/
??????題目描述：給定一個字符串 s ，通過將字符串 s 中的每個字母轉(zhuǎn)變大小寫，我們可以獲得一個新的字符串。
返回 所有可能得到的字符串集合 。以 任意順序 返回輸出。
回溯：
??????這道題和求組合的思路有些類似，組合是一個元素選或不選，本體是一個字母是否發(fā)生的大小寫轉(zhuǎn)換，然后給出所有的字符串集合。參考算法如下：
List<String> ans=new LinkedList<>();public List<String> letterCasePermutation(String s) {char[] ss=s.toCharArray();int start=0,end=ss.length-1;solve(ss,start,end);return ans;}public void solve(char[] ss,int start,int end){if(start>end){ans.add(new String(ss));return;}if(ss[start]>='0'&&ss[start]<='9')solve(ss,start+1,end); //數(shù)字跳過else{change(ss,start);solve(ss,start+1,end);change(ss,start);solve(ss,start+1,end);} }public void change(char[] ss, int i){//char tmp='a'-'A';if(ss[i]<='z'&&ss[i]>='a')ss[i]-=('a'-'A');else if(ss[i]<='Z'&&ss[i]>='A')ss[i]+=('a'-'A');}總結(jié)
??????完
總結(jié)
以上是生活随笔為你收集整理的LeetCode算法题8：递归和回溯1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LeetCode算法题7：DFS和BFS
- 下一篇： LeetCode算法题9：递归和回溯-N