一)電話號(hào)碼的字母組合
17. 電話號(hào)碼的字母組合 - 力扣（LeetCode）
1)畫出決策樹:只是需要對(duì)最終的決策樹做一個(gè)深度優(yōu)先遍歷，在葉子節(jié)點(diǎn)收集結(jié)果即可
把圖畫出來(lái)，知道每一層在干什么，代碼就能寫出來(lái)了
?2)定義全局變量:
1)定義一個(gè)哈希表來(lái)處理數(shù)字和字符串的映射關(guān)系
2)使用ret來(lái)保存最終結(jié)果
class Solution { HashMap<Character,String> result=new HashMap<>(); List<String> ret; StringBuilder path; public List<String> letterCombinations(String digits) { this.path=new StringBuilder(); result.put('2',"abc"); result.put('3', "def"); result.put('4', "ghi"); result.put('5', "jkl"); result.put('6', "mno"); result.put('7', "pqrs"); result.put('8', "tuv"); result.put('9', "wxyz"); this.ret=new ArrayList<>(); if(digits.length()==0){ return ret; } dfs(result,digits,0); return ret; } public void dfs(HashMap<Character,String> result,String digits,int index){ if(index==digits.length()){ //這個(gè)最終條件,第一次就寫錯(cuò)了,index遍歷到數(shù)組的最后一個(gè)位置以后,說(shuō)明當(dāng)前已經(jīng)把所有的字母枚舉完成了 ret.add(path.toString()); return; } Character number=digits.charAt(index); String string=result.get(number); char[] chars=string.toCharArray(); for(int i=0;i<chars.length;i++){ path.append(chars[i]); //繼續(xù)遍歷到下一層 dfs(result,digits,index+1); //恢復(fù)現(xiàn)場(chǎng),回退到上一層 path.deleteCharAt(path.length()-1); } } }
二)括號(hào)生成:
22. 括號(hào)生成 - 力扣（LeetCode）
先進(jìn)行想一下，什么是有效的括號(hào)組合？
1)左括號(hào)的數(shù)量==右括號(hào)的數(shù)量
2)從頭開(kāi)始的任意一個(gè)子串中，左括號(hào)的數(shù)量都是大于等于右括號(hào)的數(shù)量，如果發(fā)現(xiàn)右括號(hào)的數(shù)量是大于左括號(hào)的，那么必然會(huì)出現(xiàn)一個(gè)右括號(hào)沒(méi)有做括號(hào)匹配，所以就不是一個(gè)有效的括號(hào)組合
假設(shè)如果n==3，那么我們只是需要枚舉6個(gè)位置即可，因?yàn)閚==3表示的是三對(duì)括號(hào)，一共有6個(gè)位置，那么我們只是需要進(jìn)行暴力枚舉6個(gè)位置可能出現(xiàn)的情況就可以了
一)畫出決策樹:
?二)定義一個(gè)全局變量:?
1)left表示左括號(hào)的數(shù)量，right表示右括號(hào)的數(shù)量，N表示一共有多少對(duì)括號(hào)
2)當(dāng)進(jìn)行深度優(yōu)先遍歷的時(shí)候，使用這個(gè)path變量來(lái)進(jìn)行記錄這個(gè)路徑中曾經(jīng)出現(xiàn)選擇過(guò)的括號(hào)
三)dfs所干的事:
當(dāng)左括號(hào)合法的時(shí)候，把左括號(hào)添加到path中當(dāng)右括號(hào)合法的時(shí)候，把右括號(hào)添加到path中
四)遞歸:遇到葉子節(jié)點(diǎn)的時(shí)候，將這個(gè)path添加到ret中，遇到葉子節(jié)點(diǎn)的情況就是當(dāng)right==N的時(shí)候，說(shuō)明此時(shí)右括號(hào)已經(jīng)滿了
剪枝:
1)在進(jìn)行遍歷的過(guò)程中發(fā)現(xiàn)右括號(hào)的數(shù)量已經(jīng)大于等于左括號(hào)了，此時(shí)能不能進(jìn)行添加右括號(hào)了，應(yīng)該進(jìn)行剪枝操作
2)在進(jìn)行遍歷的過(guò)程中發(fā)現(xiàn)左括號(hào)的數(shù)量已經(jīng)大于等于n了，此時(shí)不能再進(jìn)行添加左括號(hào)了，進(jìn)行剪枝操作
class Solution { int N; StringBuilder path; List<String> ret;//存放最終的結(jié)果字符串 int right=0;//記錄在深度優(yōu)先遍歷的過(guò)程中右括號(hào)的數(shù)量 int left=0;//記錄在深度優(yōu)先遍歷的過(guò)程中左括號(hào)的數(shù)量 public List<String> generateParenthesis(int n) { N=n; path=new StringBuilder(); ret=new ArrayList<>(); dfs(); return ret; } public void dfs(){ if(right==N){ ret.add(path.toString()); return; } //選擇左括號(hào) if(left<N){ path.append('('); left++; dfs(); //回溯恢復(fù)現(xiàn)場(chǎng) left--; path.deleteCharAt(path.length()-1); } //選擇右括號(hào) if(right<left){ path.append(')'); right++; dfs(); //回溯恢復(fù)現(xiàn)場(chǎng) right--; path.deleteCharAt(path.length()-1); } } }其實(shí)本質(zhì)上來(lái)說(shuō)把剛才的那些全局變量放到參數(shù)里面，只是回溯時(shí)候的操作是不一樣的
三)組合:
力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
1)實(shí)現(xiàn)剪枝的操作:當(dāng)我們進(jìn)行枚舉當(dāng)前數(shù)的時(shí)候，只需要從當(dāng)前數(shù)的下一個(gè)數(shù)字開(kāi)始進(jìn)行枚舉就可以了，只需要控制dfs的參數(shù)即可
2)dfs做的事:從pos位置開(kāi)始進(jìn)行枚舉，將枚舉的情況添加到path中即可
3)回溯:當(dāng)枚舉完成當(dāng)前位置向上歸的過(guò)程中，先把path中添加的數(shù)進(jìn)行剔除，然后再返回到上一層即可
4)遞歸出口:k==path.size()
class Solution { List<List<Integer>> ret; List<Integer> path; int N; int k; public List<List<Integer>> combine(int n, int k) { N=n; this.k=k; path=new ArrayList<>(); ret=new ArrayList<>(); dfs(1); return ret; } public void dfs(int index){ if(path.size()==k) { ret.add(new ArrayList<>(path)); return; } for(int i=index;i<=N;i++){ path.add(i); dfs(i+1); path.remove(path.size()-1); } } }
四)目標(biāo)和
494. 目標(biāo)和 - 力扣（LeetCode）
中心思想:
1)就是在第一個(gè)數(shù)前面+1或者是進(jìn)行-1操作，變量作為全局變量還是函數(shù)中的參數(shù)來(lái)說(shuō)，作為全局變量是需要考慮一下回溯，作為參數(shù)的話是不需要進(jìn)行考慮回溯操作的，因?yàn)榇a本身已經(jīng)幫助我們遞歸向下進(jìn)行向上返回的過(guò)程中已經(jīng)幫助我們完成回溯操作了
2)當(dāng)作為參數(shù)的時(shí)候，遞歸函數(shù)本身歸的過(guò)程中已經(jīng)在幫助我們進(jìn)行回溯操作了，當(dāng)int結(jié)果作為參數(shù)，數(shù)組類型或者是list類型作為全局的時(shí)候?qū)懛ㄊ潜容^方便的
此時(shí)index==5，正好最終的所有情況的和都是已經(jīng)計(jì)算完成了，所以此時(shí)應(yīng)該向上返回結(jié)果
class Solution { int count=0; int target=0; int path=0; public int findTargetSumWays(int[] nums, int target) { this.target=target; dfs(nums,0); return count; } public void dfs(int[] nums,int pos){ if(pos==nums.length){ //path是標(biāo)識(shí)這個(gè)路徑中所選擇的結(jié)果 if(path==target) count++; return; } //當(dāng)前這個(gè)數(shù)取正數(shù)的情況 path+=nums[pos];//pos的作用是記錄數(shù)組下標(biāo) dfs(nums,pos+1); //回溯 path-=nums[pos]; //當(dāng)前這個(gè)數(shù)取負(fù)數(shù)的情況 path-=nums[pos]; dfs(nums,pos+1); //回溯 path+=nums[pos]; } }class Solution { int count=0; int target=0; public int findTargetSumWays(int[] nums, int target) { this.target=target; dfs(nums,0,0); return count; } public void dfs(int[] nums,int path,int pos){ if(pos==nums.length){ if(path==target){ count++; } return; } dfs(nums,path+nums[pos],pos+1);//回來(lái)的就是原來(lái)的現(xiàn)場(chǎng) dfs(nums,path-nums[pos],pos+1); } }
五)組合總和(1):
39. 組合總和 - 力扣（LeetCode）
1)沒(méi)有一成不變的模板，只需要將決策樹畫出來(lái)，將最終的決策樹轉(zhuǎn)化成代碼即可
2)反正這個(gè)題就是你從目標(biāo)的元素里面找到幾個(gè)數(shù)這幾個(gè)數(shù)進(jìn)行相加的結(jié)果等于target即可
3)所以這個(gè)題的中心思想就是一個(gè)數(shù)一個(gè)數(shù)，兩個(gè)數(shù)，兩個(gè)數(shù)的進(jìn)行考慮
4)第一個(gè)位置可以存放2，可以存放3，可以存放5
解法1:?
class Solution { List<List<Integer>> ret; int sum=0; List<Integer> path; int target=0; public List<List<Integer>> combinationSum(int[] nums, int target) { ret=new ArrayList<>(); path=new ArrayList<>(); this.target=target; Arrays.sort(nums); dfs(nums,0); return ret; } public void dfs(int[] nums,int index){ if(sum==target){ ret.add(new ArrayList<>(path)); return; } //index這個(gè)參數(shù)表示的是這一層循環(huán)從數(shù)組中的哪一個(gè)位置開(kāi)始進(jìn)行枚舉 for(int i=index;i<nums.length;i++){ path.add(nums[i]); sum+=nums[i]; if(sum>target){ sum-=nums[i]; path.remove(path.size()-1); //如果說(shuō)當(dāng)前的數(shù)加起來(lái)的和已經(jīng)都大于target了,那么后續(xù)都無(wú)需進(jìn)行遍歷了,因?yàn)榇藭r(shí)數(shù)組是有序的,直接回退到上一層即可 return; } dfs(nums,i);//下一次遍歷的位置還是可以從當(dāng)前位置開(kāi)始進(jìn)行遍歷,這里面是可以選擇重復(fù)元素 sum-=nums[i]; path.remove(path.size()-1); } } }class Solution { List<List<Integer>> ret; int sum=0; List<Integer> path; int target=0; public List<List<Integer>> combinationSum(int[] nums, int target) { ret=new ArrayList<>(); path=new ArrayList<>(); this.target=target; Arrays.sort(nums); dfs(nums,0); return ret; } public void dfs(int[] nums,int index){ if(sum>target) return; if(sum==target){ ret.add(new ArrayList<>(path)); return; } for(int i=index;i<nums.length;i++){ path.add(nums[i]); sum+=nums[i]; dfs(nums,i); //枚舉到下一層的時(shí)候回溯到當(dāng)前結(jié)點(diǎn)的時(shí)候進(jìn)行恢復(fù)現(xiàn)場(chǎng)的操作 sum-=nums[i]; path.remove(path.size()-1); } } }下面是當(dāng)sum是局部變量的時(shí)候，所進(jìn)行傳遞的值:
?解法2:根據(jù)選取對(duì)應(yīng)的數(shù)的個(gè)數(shù)來(lái)畫出決策樹:
每一個(gè)數(shù)我可以選擇0個(gè)，1個(gè)，可以選擇2個(gè)，可以選擇3個(gè)，可以選擇4個(gè)
我們告訴dfs一個(gè)位置，枚舉1個(gè)，兩個(gè)，三個(gè)，只要小于8即可，只要枚舉的個(gè)數(shù)*這個(gè)數(shù)<8即可，添加到path路徑中，接下來(lái)去下一層開(kāi)始走
當(dāng)我們枚舉完9的時(shí)候才會(huì)向上恢復(fù)現(xiàn)場(chǎng)的，因?yàn)榧僭O(shè)如果枚舉到3的時(shí)候才向上恢復(fù)現(xiàn)場(chǎng)，那么6的情況必定會(huì)被丟棄掉，因?yàn)楹竺娴臄?shù)是在前面的數(shù)的基礎(chǔ)上+3的，后面的數(shù)要依賴于前面的數(shù)，所以當(dāng)我們將這一層的所有的數(shù)處理完成之后才會(huì)恢復(fù)現(xiàn)場(chǎng)
class Solution { List<Integer> path=new ArrayList<>(); List<List<Integer>> ret=new ArrayList<>(); public int target; int sum=0; public void dfs(int[] nums,int index){ if(sum==target){ ret.add(new ArrayList<>(path)); return; } if(index==nums.length||sum>target) return; //進(jìn)行枚舉nums[index]使用多少個(gè) for(int k=0;k*nums[index]+sum<=target;k++){ if(k!=0) path.add(nums[index]); sum+=k*nums[index]; dfs(nums,index+1); sum-=k*nums[index];//向上回溯的時(shí)候恢復(fù)現(xiàn)場(chǎng) } for(int k=1;k*nums[index]+sum<=target;k++){ path.remove(path.size()-1); } } public List<List<Integer>> combinationSum(int[] nums, int target) { this.target=target; dfs(nums,0); return ret; } }
六)組合總和(2)?
39. 組合總和 - 力扣（LeetCode）
class Solution { int sum=0; int target=0; List<List<Integer>> ret; List<Integer> path; boolean[] used; public List<List<Integer>> combinationSum2(int[] nums, int target) { this.ret=new ArrayList<>(); this.path=new ArrayList<>(); this.target=target; this.used=new boolean[nums.length]; Arrays.sort(nums); dfs(nums,0); return ret; } public void dfs(int[] nums,int index){ if(sum>target) return; if(sum==target){ ret.add(new ArrayList<>(path)); return; } for(int i=index;i<nums.length;i++){ if(i!=index&&used[i-1]!=true&&nums[i]==nums[i-1]){ continue; } path.add(nums[i]); sum+=nums[i]; used[i]=true; dfs(nums,i+1); used[i]=false; sum-=nums[i]; path.remove(path.size()-1); } } }
其實(shí)本質(zhì)上不使用check數(shù)組也是一樣的，我們每一次從下一個(gè)位置開(kāi)始進(jìn)行枚舉，就已經(jīng)可以自動(dòng)排除上一次曾經(jīng)使用過(guò)的元素，自己一定要好好畫決策樹
class Solution { List<List<Integer>> ret=new ArrayList<>(); List<Integer> path=new ArrayList<>(); int sum=0; public void dfs(int[] nums,int target,int index){ if(sum>target) return; if(sum==target){ ret.add(new ArrayList<>(path)); return; } if(path.size()==nums.length) return; for(int i=index;i<nums.length;i++){ if(i!=index&&nums[i]==nums[i-1]){ continue; } path.add(nums[i]); sum+=nums[i]; dfs(nums,target,i+1); path.remove(path.size()-1); sum-=nums[i]; } } public List<List<Integer>> combinationSum2(int[] nums, int target) { Arrays.sort(nums); dfs(nums,target,0); return ret; } }如果我們最終發(fā)現(xiàn)時(shí)間超時(shí)，那么可能出現(xiàn)的bug就是沒(méi)有正確的進(jìn)行剪枝，導(dǎo)致一些冗余的情況進(jìn)行計(jì)算了進(jìn)來(lái)
七)路經(jīng)總和
112. 路徑總和 - 力扣（LeetCode）
解法1:找到二叉樹的所有路徑和，把他存放到一個(gè)list里面
相同子問(wèn)題:跟定一個(gè)根節(jié)點(diǎn)，求以根節(jié)點(diǎn)為樹的所有路徑和
遞歸出口:當(dāng)進(jìn)行遍歷到葉子結(jié)點(diǎn)的時(shí)候
dfs:向下一直找到葉子節(jié)點(diǎn)，如果遇到葉子節(jié)點(diǎn)，就把sum+root.val存放到最終結(jié)果中
class Solution { public int sum=0; List<Integer> list=new ArrayList<>(); public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; dfs(root,0); return list.contains(targetSum); } public void dfs(TreeNode root,int sum){ if(root.left==null&&root.right==null){ //與到葉子節(jié)點(diǎn)的時(shí)候才會(huì)進(jìn)行計(jì)數(shù),找到遞歸的出口 list.add(sum+root.val); return; } if(root.left!=null) dfs(root.left,sum+root.val); if(root.right!=null) dfs(root.right,sum+root.val); } }解法2:使用回溯的方式，也是找到重復(fù)子問(wèn)題:
1)觀察我們要找的所有函數(shù)，我們可以查詢出它的功能:詢問(wèn)是否從當(dāng)前節(jié)點(diǎn)root到達(dá)葉子節(jié)點(diǎn)的路徑，找到滿足于路徑和等于sum，假設(shè)從根節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的和是temp，那么我們只是需要找到是否從當(dāng)前節(jié)點(diǎn)到達(dá)葉子節(jié)點(diǎn)，找到和等于sum-temp的葉子的路徑，滿足路徑之和等于sum-temp
2)遞歸出口:當(dāng)遍歷到葉子結(jié)點(diǎn)的時(shí)候，判斷sum-temp==true
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; if(root.left==null&&root.right==null){ return root.val==targetSum; } return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val); } }
八)路經(jīng)總和(2)
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-627608.html
class Solution { List<Integer> path; List<List<Integer>> ret; int targetSum; int sum; public List<List<Integer>> pathSum(TreeNode root, int targetSum) { this.path=new ArrayList<>(); this.ret=new ArrayList<>(); this.targetSum=targetSum; dfs(root); return ret; } public void dfs(TreeNode root){ if(root==null) return; if(root.left==null&&root.right==null){ path.add(root.val); sum+=root.val; if(sum==targetSum){ ret.add(new ArrayList<>(path)); } sum-=root.val; path.remove(path.size()-1); //此時(shí)遍歷到葉子結(jié)點(diǎn)的時(shí)候還是需要向上進(jìn)行回溯操作 return; } path.add(root.val); sum+=root.val; dfs(root.left); //向上回溯,恢復(fù)現(xiàn)場(chǎng) sum-=root.val; path.remove(path.size()-1); path.add(root.val); sum+=root.val; dfs(root.right); //向上回溯,恢復(fù)現(xiàn)場(chǎng) sum-=root.val; path.remove(path.size()-1); } }
九)組合總和(3)
216. 組合總和 III - 力扣（LeetCode）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-627608.html
class Solution { List<Integer> path; List<List<Integer>> ret; int sum=0; int n=0; int target; public List<List<Integer>> combinationSum3(int n, int target) { this.path=new ArrayList<>(); this.target=target; this.n=n; this.ret=new ArrayList<>(); dfs(1); return ret; } public void dfs(int index){ if(path.size()>n) return; if(sum==target&&path.size()==n){ ret.add(new ArrayList<>(path)); return; } for(int i=index;i<=9;i++){ path.add(i); sum+=i; dfs(i+1); sum-=i; path.remove(path.size()-1); } } }
到了這里，關(guān)于窮舉&&深搜&&暴搜&&回溯&&剪枝(2)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
