企业网站模板大全,长春定制建站企业网站,软件开发工具包括,wordpress宽屏回溯算法 简介[中等] 77. 组合[中等] 216. 组合总和 III[中等] 17. 电话号码的字母组合[中等] 39. 组合总和[中等] 40. 组合总和 II[中等] 131. 分割回文串[中等] 93. 复原 IP 地址[中等] 78. 子集[中等] 90. 子集 II[中等] 491. 非递减子序列[中等] 46. 全排列[中等] 47. 全排… 回溯算法 简介[中等] 77. 组合[中等] 216. 组合总和 III[中等] 17. 电话号码的字母组合[中等] 39. 组合总和[中等] 40. 组合总和 II[中等] 131. 分割回文串[中等] 93. 复原 IP 地址[中等] 78. 子集[中等] 90. 子集 II[中等] 491. 非递减子序列[中等] 46. 全排列[中等] 47. 全排列 II[困难] 51. N 皇后[困难] 37. 解数独 简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路如果有错误可以在评论区提醒一下。
回溯题模板
class Solution {public 主方法(参数) {//把递归参数传入递归函数recursion(0);return ans;}public void recursion(int n){if(达到终止条件) {//存放结果ans.add(answer);return;}for(循环调用后续的递归){//递归前处理比如把当前数加入答案集合recursion(n 1);//递归后处理回溯撤销递归前处理的内容}}
}[中等] 77. 组合
原题链接
注意每次ans.add时需要添加nums的深拷贝而不是单纯把当前nums放入否则放入的其实是nums数组的引用最后ans的所有元素实际都指向了同一个数组。
class Solution {public ListListInteger combine(int n, int k) {ListListInteger ans new ArrayList();ListInteger nums new ArrayList();recursion(ans, nums, 1, n, k);return ans;}public void recursion(ListListInteger ans, ListInteger nums, int p, int n, int k){//终止条件if(nums.size() k){ans.add(new ArrayList(nums));return;}for(; p n; p){nums.add(p);recursion(ans, nums, p1, n, k);nums.remove(nums.size() - 1);}return;}
}剪枝操作: k - nums.size()是还需要多少个元素构成一组答案
for(; p n - (k - nums.size()) 1; p){nums.add(p);recursion(ans, nums, p1, n, k);nums.remove(nums.size() - 1);}[中等] 216. 组合总和 III
原题链接
sum函数直接用参数替代也可以
class Solution {public ListListInteger combinationSum3(int k, int n) {ListInteger nums new ArrayList();ListListInteger ans new ArrayList();recursion (ans, nums, k, n, 1);return ans;}public void recursion(ListListInteger ans, ListInteger nums, int k, int n, int p){if(nums.size() k){if(sum(nums) n)ans.add(new ArrayList(nums));return;}if(sum(nums) n) {for (; p 9; p) {nums.add(p);recursion(ans, nums, k, n, p 1);nums.remove(nums.size() - 1);}}}public int sum(ListInteger nums){int sum 0;for(Integer i: nums){sum i;}return sum;}
}[中等] 17. 电话号码的字母组合
原题链接
使用StringBuilder做字符串操作
class Solution {public ListString letterCombinations(String digits) {StringBuilder sb new StringBuilder();ListString ans new ArrayList();String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};if(digits.length() 0) return ans;recursion(digits, sb, ans, numString, 0);return ans;}public void recursion(String digits, StringBuilder sb, ListString ans, String[] numString, int p){if(p digits.length()){ans.add(sb.toString());return;}for(int i 0; i numString[digits.charAt(p) - 0].length(); i) {sb.append(numString[digits.charAt(p) - 0].charAt(i));recursion(digits, sb, ans, numString, p 1);sb.deleteCharAt(p);}}
}[中等] 39. 组合总和
原题链接
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger ans new ArrayList();ListInteger nums new ArrayList();recursion(ans, nums, candidates, target, 0, 0);return ans;}public void recursion(ListListInteger ans, ListInteger nums, int[] candidates, int target, int sum, int p){if(sum target) return;//终止条件if(sum target){ans.add(new ArrayList(nums));return;}for(int i p; i candidates.length; i){nums.add(candidates[i]);recursion(ans, nums, candidates, target, sumcandidates[i], i);nums.remove(nums.size() - 1);}return;}
}[中等] 40. 组合总和 II
原题链接
对原数组进行排序相同的数字顺序存放对相同数字的使用保证从左到右。比如选择[1,1,6] 中的 [1,6] 作为答案只会选到第一个1
class Solution {public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);ListListInteger ans new ArrayList();ListInteger nums new ArrayList();int[] flag new int[110];recursion(ans, nums, candidates, flag, target, 0, 0);return ans;}public void recursion(ListListInteger ans, ListInteger nums, int[] candidates, int[] flag, int target, int sum, int p){if(sum target) return;//终止条件if(sum target){ans.add(new ArrayList(nums));return;}for(int i p; i candidates.length; i){//存在与之相同的前一个数且前一个数还没被取过则不会取当前数if(i0 flag[i-1] 0 candidates[i-1] candidates[i]) continue;nums.add(candidates[i]);flag[i] 1;recursion(ans, nums, candidates, flag, target, sumcandidates[i], i1);flag[i] 0;nums.remove(nums.size() - 1);}return;}
}[中等] 131. 分割回文串
原题链接
这个递归自己想还想了挺久的就是从左往右切割终止条件就是判断有没有切到最右端
class Solution {public ListListString partition(String s) {ListListString ans new ArrayList();ListString group new ArrayList();if(s null || s.length() 0) return ans;recursion(ans, group, s, 0);return ans;}private void recursion(ListListString ans, ListString group, String s, int start) {if(start s.length()) {ans.add(new ArrayList(group));return;}for(int i start; i s.length(); i) {if(isPalindrome(s, start, i)) {group.add(s.substring(start, i 1));recursion(ans, group, s, i 1);group.remove(group.size() - 1);}}}private boolean isPalindrome(String s, int begin, int end) {while(begin end) {if(s.charAt(begin) ! s.charAt(end--)) return false;}return true;}
}[中等] 93. 复原 IP 地址
原题链接
注意分割段到4时也需要return往后的递归都是无意义的
class Solution {public ListString restoreIpAddresses(String s) {ListString ans new ArrayList();ListString answer new ArrayList();if(s null || s.length() 0) return ans;//p表示目前划分到第几段ip地址总共四段 index表示s下标recursion(ans, s, 0, answer);return ans;}public void recursion(ListString ans, String s, int index, ListString answer){if(answer.size() 4 index s.length()){ans.add(createAnswer(answer));}if(index s.length() || answer.size() 4) return;if(s.charAt(index) 0){answer.add(0);recursion(ans, s, index 1, answer);answer.remove(answer.size() - 1);}else {for (int i index; i s.length() i - index 3; i) {String string s.substring(index, i 1);int num Integer.parseInt(string);if (num 0 num 255){answer.add(string);recursion(ans, s, i 1, answer);answer.remove(answer.size() - 1);}}}}public String createAnswer(ListString answer){StringBuilder sb new StringBuilder();for(int i 0; i answer.size(); i){if(i ! 0){sb.append(.);}sb.append(answer.get(i));}return sb.toString();}
}[中等] 78. 子集
原题链接
一道标准的子集问题模板题子集是收集树形结构中树的所有节点的结果。 而组合问题、分割问题是收集树形结构中叶子节点的结果。子集问题不需要在找到一组答案之后就进行回退。
class Solution {public ListListInteger subsets(int[] nums) {ListListInteger ans new ArrayList();ListInteger answer new ArrayList();recursion(ans, answer, nums, 0);return ans;}public void recursion(ListListInteger ans, ListInteger answer, int[] nums, int index){ans.add(new ArrayList(answer));for(int i index; i nums.length; i){answer.add(nums[i]);recursion(ans, answer, nums, i 1);answer.remove(answer.size() - 1);}}
}[中等] 90. 子集 II
原题链接
class Solution {public ListListInteger subsetsWithDup(int[] nums) {ListListInteger ans new ArrayList();ListInteger answer new ArrayList();boolean[] used new boolean[nums.length];Arrays.sort(nums);recursion(ans, answer, used, nums, 0);return ans;}public void recursion(ListListInteger ans, ListInteger answer, boolean[] used, int[] nums, int index){ans.add(new ArrayList(answer));for(int i index; i nums.length; i){if(i 0 nums[i] nums[i - 1] !used[i - 1]){continue;}used[i] true;answer.add(nums[i]);recursion(ans, answer, used, nums, i 1);answer.remove(answer.size() - 1);used[i] false;}}
}[中等] 491. 非递减子序列
原题链接
不能简单的强制类似[1,1,1,1,1]序列从左到右选这道题不能排序有可能会有[1,1,2,1,1]这样2之前的1没取的时候2后面的1也可以取需要用集合set来做去重
class Solution {public ListListInteger findSubsequences(int[] nums) {ListListInteger ans new ArrayList();ListInteger answer new ArrayList();recursion(ans, answer, nums, 0);return ans;}public void recursion(ListListInteger ans, ListInteger answer, int[] nums, int index){if(answer.size() 1)ans.add(new ArrayList(answer));HashSetInteger hs new HashSet();for(int i index; i nums.length; i){if(hs.contains(nums[i]) || (answer.size() 0 nums[i] answer.get(answer.size() - 1)))continue;hs.add(nums[i]);answer.add(nums[i]);recursion(ans, answer, nums, i 1);answer.remove(answer.size() - 1);}}
}[中等] 46. 全排列
原题链接
开一个数组标记不重复取数每次循环都从头开始即可
class Solution {public ListListInteger permute(int[] nums) {ListListInteger ans new ArrayList();ListInteger answer new ArrayList();boolean[] used new boolean[nums.length];recursion(ans, answer, used, nums);return ans;}public void recursion(ListListInteger ans, ListInteger answer, boolean[] used, int[] nums){if(answer.size() nums.length) {ans.add(new ArrayList(answer));return;}for(int i 0; i nums.length; i){if(used[i]) continue;used[i] true;answer.add(nums[i]);recursion(ans, answer, used, nums);answer.remove(answer.size() - 1);used[i] false;}}
}[中等] 47. 全排列 II
原题链接
对数组排序并对相同数字保证从左到右取数同时不重复取数
class Solution {public ListListInteger permuteUnique(int[] nums) {ListListInteger ans new ArrayList();ListInteger answer new ArrayList();boolean[] used new boolean[nums.length];Arrays.sort(nums);recursion(ans, answer, used, nums);return ans;}public void recursion(ListListInteger ans, ListInteger answer, boolean[] used, int[] nums){if(answer.size() nums.length) {ans.add(new ArrayList(answer));return;}for(int i 0; i nums.length; i){if(used[i]) continue;if(i 0 nums[i] nums[i - 1] !used[i - 1]) continue;used[i] true;answer.add(nums[i]);recursion(ans, answer, used, nums);answer.remove(answer.size() - 1);used[i] false;}}
}[困难] 51. N 皇后
原题链接
class Solution {public ListListString solveNQueens(int n) {ListListString ans new ArrayList();//初始化棋盘声明一个flag数组标记每一行填充的元素在哪一列初始化为-1int[] flag new int[n];for(int i 0; i n; i){flag[i] -1;}recursion(ans, flag, 0);return ans;}public void recursion(ListListString ans, int[] flag, int row){if(row flag.length){ans.add(createAnswer(flag));return;}for(int i 0; i flag.length; i){if(isFree( flag, row, i)){flag[row] i;recursion(ans, flag, row 1);flag[row] -1;}}}//可否放置皇后棋子的判定public boolean isFree(int[] flag, int row, int p){//对角线判定 以及 列未判定for(int i 0; i row; i ) {if(flag[i] p) return false;if (flag[i] - i p - row || flag[i] i row p) {return false;}}return true;}//创建答案public ListString createAnswer(int[] flag) {ListString answer new ArrayList();for (int i 0; i flag.length; i) {StringBuilder sb new StringBuilder();for (int j 0; j flag.length; j) {if (flag[i] j) {sb.append(Q);} else {sb.append(.);}}answer.add(sb.toString());}return answer;}
}[困难] 37. 解数独
原题链接
代码随想录给到的是一种暴力二维搜索是比较容易想到的每次递归都去判断行、列、九宫格里是否重复这样效率会比较低可以牺牲空间来简化这部分的判断分别开设三个二维数组记录每一行每一列每一个九宫格1-9的数字是否被使用过后续比较直接从数组里去读取信息就可以。
class Solution {public void solveSudoku(char[][] board) {//行、列、九宫格是否被占用boolean[][] rowOccupy new boolean[9][9];boolean[][] colOccupy new boolean[9][9];boolean[][] nineOccupy new boolean[9][9];char a board[1][2];for(int i 0; i 9; i){for(int j 0; j 9; j){char ch board[i][j];if(ch ! .) {rowOccupy[i][ch - 1] true;colOccupy[j][ch - 1] true;nineOccupy[i / 3 * 3 j / 3][ch - 1] true;}}}recursion(rowOccupy, colOccupy, nineOccupy, board, 0, 0);}public boolean recursion(boolean[][] rowOccupy, boolean[][] colOccupy, boolean[][] nineOccupy, char[][]board, int i, int j){if(i 8 || j 8) return true;if(board[i][j] ! .){if(j 8) {if (recursion(rowOccupy, colOccupy, nineOccupy, board, i 1, 0)) {return true;}}else if (recursion(rowOccupy, colOccupy, nineOccupy, board, i, j 1)) {return true;}}else {for (int k 1; k 9; k) {if (!rowOccupy[i][k - 1] !colOccupy[j][k - 1] !nineOccupy[i / 3 * 3 j / 3][k - 1]) {board[i][j] String.valueOf(k).charAt(0);rowOccupy[i][k - 1] true;colOccupy[j][k - 1] true;nineOccupy[i / 3 * 3 j / 3][k - 1] true;if (j 8) {if (recursion(rowOccupy, colOccupy, nineOccupy, board, i 1, 0)) {return true;}}else if (recursion(rowOccupy, colOccupy, nineOccupy, board, i, j 1)) {return true;}board[i][j] .;rowOccupy[i][k - 1] false;colOccupy[j][k - 1] false;nineOccupy[i / 3 * 3 j / 3][k - 1] false;}}}return false;}
}
