前言

????????本文用于整理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);}}
}