【LeetCode Hot100】回溯篇
前言
本文用于整理LeetCode Hot100中题目解答，因题目比较简单且更多是为了面试快速写出正确思路，只做简单题意解读和一句话题解方便记忆。但代码会全部给出，方便大家整理代码思路。
46. 全排列
一句话题意
给定一个无重复数字的序列，求序列的全排列。
一句话题解
dfs扔数求全排列。
class Solution {List<List<Integer>> ans;public List<List<Integer>> permute(int[] nums) {ans =new ArrayList<>();dfs(nums,new ArrayList<>(),new HashSet<>());return ans;}void dfs(int[] nums,List<Integer> arr,Set<Integer> u){if(arr.size() == nums.length){ans.add(new ArrayList<>(arr));return ;}for(int i=0;i<nums.length;i++){if(u.contains(nums[i]))continue;arr.add(nums[i]);u.add(nums[i]);dfs(nums,arr,u);arr.remove(arr.size()-1);u.remove(nums[i]);}}
}78. 子集
一句话题意
给定一个数组，求数组中所有的子集。
一句话题解
二进制枚举。
class Solution {public List<List<Integer>> subsets(int[] nums) {int n = nums.length;List<List<Integer>> ans = new ArrayList<>();for(int i=(1<<n)-1;i>=0;i--){List<Integer> arr = new ArrayList<>();int ii=i;for(int j=0;j<n;j++){if(ii%2==1)arr.add(nums[j]);ii/=2;}ans.add(arr);}return ans;}
}17. 电话号码的字母组合
一句话题意
给定一个旧电话上数字和字符的映射，问给定一串数字序列，可能的字母组合有哪些。
一句话题解
先将数字做映射，然后dfs组合即可。
class Solution {Map<Character, String> mp = new HashMap<>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};public List<String> letterCombinations(String digits) {List<String> ans = new ArrayList<String>();if (digits.length() == 0) {return ans;}dfs(ans, digits, 0, new StringBuilder());return ans;}void dfs(List<String> ans,String digits,int i,StringBuilder s){if(i==digits.length()){ans.add(s.toString());return ;}String now=mp.get(digits.charAt(i));for(int j=0;j<now.length();j++){s.append(now.charAt(j));dfs(ans,digits,i+1,s);s.deleteCharAt(i);}}
}
39. 组合总和
一句话题意
给定一个数字序列和一个目标值，数字序列中每个可以取任意个，问组成目标值的所有组合。
一句话题解
DFS，如果没有达到目标值，则尽量往里面扔值。
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();List<Integer> c = new ArrayList<>();dfs(candidates, target, ans, c, 0);return ans;}public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> c, int i) {if (i == candidates.length) {return;}if (target == 0) {ans.add(new ArrayList<Integer>(c));return;}dfs(candidates, target, ans, c, i + 1);if (target - candidates[i] >= 0) {c.add(candidates[i]);dfs(candidates, target - candidates[i], ans, c, i);c.remove(c.size() - 1);}}
}
22. 括号生成
一句话题意
构建所有满足含有n对括号的括号序列。
一句话题解
dfs，优先放左括号，然后再放右括号。
class Solution {public List<String> generateParenthesis(int n) {List<String> ans = new ArrayList<String>();dfs(ans, new StringBuilder(), 0, 0, n);return ans;}public void dfs(List<String> ans, StringBuilder s, int l, int r, int n) {if (s.length() == n * 2) {ans.add(s.toString());return;}if (l < n) {s.append('(');dfs(ans, s, l + 1, r, n);s.deleteCharAt(s.length() - 1);}if (r < l) {s.append(')');dfs(ans, s, l, r + 1, n);s.deleteCharAt(s.length() - 1);}}
}79. 单词搜索
一句话题意
给定一个二维字符数组，规定每个字符只能使用一次，问给定的单词是否出现在二维数组中过。
一句话题解
DFS，额外设定一个访问数组即可。
class Solution {int n;int m;char[][] dt;boolean[][] v;String s;boolean flag=false;public boolean exist(char[][] board, String word) {this.n=board.length;this.m=board[0].length;this.dt=board;this.v=new boolean[n][m];this.s=word;for(int i=0;i<n;i++)for(int j=0;j<m;j++)v[i][j]=false;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]==word.charAt(0)){v[i][j]=true;dfs(i,j,1);v[i][j]=false;if(flag)return true;}}}return false;}int[][] fx={{0,1},{1,0},{-1,0},{0,-1}};void dfs(int i,int j,int idx){if(idx == s.length()){flag=true;return;}for(int k=0;k<4;k++){int ii=i+fx[k][0];int jj=j+fx[k][1];if(ii<0||ii>=n||jj<0||jj>=m||v[ii][jj]||dt[ii][jj]!=s.charAt(idx))continue;v[ii][jj]=true;dfs(ii,jj,idx+1);v[ii][jj]=false;}}
}131. 分割回文串
一句话题意
给定一个字符串，可以任意分割字符串，求当进行分割后所有子串都是回文串的分割方式有哪些。
一句话题解
先DP求出所有回文子串，然后dfs进行分割。
class Solution {int n;boolean[][] dp;String s;List<String> arr;List<List<String>>ans;public List<List<String>> partition(String s) {this.s=s;this.n=s.length();this.dp=new boolean[n][n];this.ans=new ArrayList<>();this.arr=new ArrayList<>();for(int i=0;i<n;i++)for(int j=0;j<n;j++)dp[i][j]=true;for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){dp[i][j]= s.charAt(i) == s.charAt(j) && dp[i+1][j-1];}}dfs(0);return ans;}void dfs(int i){if(i==n){ans.add(new ArrayList(arr));return;}for(int j=i;j<n;j++){if(dp[i][j]){arr.add(s.substring(i,j+1));dfs(j+1);arr.remove(arr.size()-1);}}}
}51. N 皇后
一句话题意
皇后的规则是可以吃相同行列、对角线的棋子，问所有满足可以在棋盘上防止N个互不影响的皇后。
一句话题解
存三个set用于存哪个位置不能存，DFS即可。
class Solution {List<List<String>> ans = new ArrayList<>();List<String> arr = new ArrayList<>();Set<Integer> uy = new HashSet<>();Set<Integer> ul = new HashSet<>();Set<Integer> ur = new HashSet<>();int n;public List<List<String>> solveNQueens(int n) {this.n=n;dfs(0);return ans;}void dfs(int row){if(row==n){ans.add(new ArrayList<>(arr));return;}for(int i=0;i<n;i++){if(uy.contains(i)||ul.contains(row-i)||ur.contains(row+i))continue;StringBuffer s = new StringBuffer();for(int j=0;j<i;j++)s.append('.');s.append('Q');for(int j=i+1;j<n;j++)s.append('.');arr.add(new String(s));uy.add(i);ul.add(row-i);ur.add(row+i);dfs(row+1);uy.remove(i);ul.remove(row-i);ur.remove(row+i);arr.remove(arr.size()-1);}}
}