乐清品牌网站建设,一个主机可以做几个网站域名,抖音电商网站建设,访问紧急升级中通知问升级组合问题#xff1a;N个数里面按一定规则找出k个数的集合
如果题目要求的是组合的具体信息#xff0c;则只能使用回溯算法#xff0c;如果题目只是要求组合的某些最值#xff0c;个数等信息#xff0c;则使用动态规划#xff08;比如求组合中元素最少的组合#xff0c;…组合问题N个数里面按一定规则找出k个数的集合
如果题目要求的是组合的具体信息则只能使用回溯算法如果题目只是要求组合的某些最值个数等信息则使用动态规划比如求组合中元素最少的组合求组合的个数等
77. 组合
ListListInteger res new ArrayList();
LinkedListInteger path new LinkedList();public ListListInteger combine(int n, int k) {dfs(1, n, k);return res;
}private void dfs(int start, int n, int k) {if (path.size() k) {res.add(new ArrayList(path));return;}// for循环的作用固定第一个值比如 1~4分别固定1~4如果start为2则不会遍历到1for (int i start; i n; i) {path.push(i); // 记录dfs(i 1, n, k);path.pop(); // 回溯}
}
39. 组合总和
ListListInteger res new ArrayList();
LinkedListInteger path new LinkedList();public ListListInteger combinationSum(int[] candidates, int target) {dfs(0, candidates, target);return res;
}private void dfs(int start, int[] candidates, int target) {// 如果target为0说明找到解if (0 target) {res.add(new ArrayList(path));return;}for (int i start; i candidates.length; i) {int candidate candidates[i];if (target candidate) {continue; // 剪枝}path.push(candidate);dfs(i, candidates, target - candidate); // // 关键点:不用i1了表示可以重复读取当前的数path.pop();}
}
40. 组合总和 II
ListListInteger result new LinkedList();
LinkedListInteger stack new LinkedList();
boolean[] visited;public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 排序将相同的元素相邻放置visited new boolean[candidates.length];dfs(0, candidates, target);return result;
}public void dfs(int start, int[] candidates, int target) {if (target 0) {result.add(new LinkedList(stack));return;}for (int i start; i candidates.length; i) {int candidate candidates[i];if (target candidate) {continue; // 减枝}// 如果相邻的两个值相等且前一个值还没有被访问则跳过循环// 相邻的值只有一个可以被先访问防止组合结果出现重复比如【521512】if (i 0 candidate candidates[i - 1] !visited[i - 1]) {continue;}visited[i] true;stack.push(candidate);// 不同点从当前遍历到的元素后面开始递归start i1;排除自身使得结果中一个元素只能出现一次dfs(i 1, candidates, target - candidate);stack.pop();visited[i] false;}
}
216. 组合总和 III
ListListInteger res new ArrayList();
LinkedListInteger path new LinkedList();public ListListInteger combinationSum3(int k, int n) {dfs(1, k, n);return res;
}private void dfs(int start, int k, int target) {if (target 0 path.size() k) {res.add(new ArrayList(path));return;}for (int i start; i 9; i) {if (target i) {continue; // 剪枝}if (path.size() k) {continue; // 剪枝}path.push(i);dfs(i 1, k, target - i);path.pop();}
}
17. 电话号码的字母组合
ListString res new ArrayList(); // 存放最终的结果集合
StringBuilder temp new StringBuilder(); // 每个结果public ListString letterCombinations(String digits) {if (digits null || digits.isEmpty()) {return res;}// 数字和字符串的映射关系比如数组下标为2时numString[2] abcString[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};// 递归dfs(digits, numString, 0);return res;
}/**** param digits 题目的参数比如”23”* param numString 数字和字符串的映射关系* param i 当前正在处理的字符串的索引 比如0则表示正在处理 digits的第一个字符串也是就2对应的字符串‘abc’*/
private void dfs(String digits, String[] numString, int i) {if (digits.length() temp.length()) {// 将结果加入集合res.add(temp.toString());return;}// 取当前应该处理的字符串// digits.charAt(i)表示取参数中的数字比如“2” -0操作将其转化为2~9范围内的int类型// numString[digits.charAt(i) - 0]; 则表示在映射关系中取当前数字对应的字符串char charAt digits.charAt(i);String str numString[charAt - 0];for (int j 0; j str.length(); j) {temp.append(str.charAt(j));dfs(digits, numString, i 1); // 取下一个字符串一个一个处理// 比如“digits”为“23”则先取2对应的字符串“abc”然后固定a递归处理3对应的字符串def,固定d则返回adtemp.deleteCharAt(temp.length() - 1);}
}
切割问题一个字符串按一定规则有几种切割方式 在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。 131. 分割回文串
class Solution {//保持前几题一贯的格式ListListString res new ArrayList();ListString cur new ArrayList();public ListListString partition(String s) {backtracking(s, 0, new StringBuilder());return res;}private void backtracking(String s, int start, StringBuilder sb) {//因为是起始位置一个一个加的所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文所以cur是满足条件的if (start s.length()) {//注意创建一个新的copyres.add(new ArrayList(cur));return;}//像前两题一样从前往后搜索如果发现回文进入backtracking,起始位置后移一位循环结束照例移除cur的末位for (int i start; i s.length(); i) {sb.append(s.charAt(i));if (check(sb)) {cur.add(sb.toString());backtracking(s, i 1, new StringBuilder());cur.remove(cur.size() - 1);}}}//helper method, 检查是否是回文前后指针指向的元素不同则不是回文private boolean check(StringBuilder sb) {for (int i 0; i sb.length() / 2; i) {if (sb.charAt(i) ! sb.charAt(sb.length() - 1 - i)) {return false;}}return true;}}
93. 复原 IP 地址❤️
class Solution {LinkedListString res new LinkedList();public ListString restoreIpAddresses(String s) {if (s.length() 12) {return res;}backTrack(s, 0, 0);return res;}private void backTrack(String s, int startIndex, int pointNum) {if (pointNum 3) {if (isValid(s, startIndex, s.length() - 1)) {res.add(s);}return;}for (int i startIndex; i s.length(); i) {if (isValid(s, startIndex, i)) {s s.substring(0, i 1) . s.substring(i 1);pointNum;backTrack(s, i 2, pointNum);pointNum--;s s.substring(0, i 1) s.substring(i 2);} else {break;}}}/*** 验证当前子串是否符合下面三个条件* 1.子串的第一个字符不为0* 2.子串总数不大于255* 3.子串为正整数*/private boolean isValid(String s, int start, int end) {if (start end) {return false;}if (s.charAt(start) 0 start ! end) {return false;}int num 0;for (int i start; i end; i) {num num * 10 s.charAt(i) - 0;if (num 255) {return false;}}return true;}}
子集问题一个N个数的集合里有多少符合条件的子集 求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。 78. 子集❤️
ListListInteger list new ArrayList();
LinkedListInteger path new LinkedList();public ListListInteger subsets(int[] nums) {dfs(0, nums);return list;
}private void dfs(int start, int[] nums) {// 子集是收集树形结构中树的所有节点的结果。list.add(new ArrayList(path));for (int i start; i nums.length; i) {int num nums[i];path.push(num);dfs(i 1, nums);path.pop();}
}
90. 子集 II 子集II问题这种需要回溯解决的题目组合问题子集问题切割问题如果遇到原先给你的集合中有重复元素而输出的结果中不允许有重复结果的需要先将原始数组排序然后使用一个boolean类型的数组标记每个元素是否被访问对于重复的元素如果前一个元素没有被访问则不允许访问第二个元素 ListListInteger result new ArrayList();
LinkedListInteger path new LinkedList();
boolean[] used; // 元素是否被访问public ListListInteger subsetsWithDup(int[] nums) {if (nums.length 0) {result.add(path);return result;}Arrays.sort(nums);used new boolean[nums.length];dfs(nums, 0);return result;
}private void dfs(int[] nums, int startIndex) {result.add(new ArrayList(path));if (startIndex nums.length) { // 终止条件return;}for (int i startIndex; i nums.length; i) {// 去重递归树层去重如果nums中有重复则必须先访问前面的元素才能访问后面的元素if (i 0 nums[i] nums[i - 1] !used[i - 1]) {// 如果出现重复前面一个还没访问则跳出循环continue;}int num nums[i];path.push(num);used[i] true;dfs(nums, i 1);path.pop();used[i] false;}
}
491. 非递减子序列
ListListInteger res new ArrayList();
ListInteger path new ArrayList();public ListListInteger findSubsequences(int[] nums) {dfs(0, nums);return res;
}public void dfs(int start, int[] nums) {if (path.size() 1) {res.add(new ArrayList(path));}// 使用数组去重第一遇到一个值将对应数组下标置位1如果再次遇到1则说明已经访问过跳过int[] used new int[201];for (int i start; i nums.length; i) {int num nums[i];if (!path.isEmpty() path.get(path.size() - 1) num ||used[num 100] 1) {continue;}used[num 100] 1;path.add(num);dfs(i 1, nums);path.remove(path.size() - 1);}
}
排列问题N个数按一定规则全排列有几种排列方式 每层都是从0开始搜索而不是startIndex 需要used数组记录path里都放了哪些元素了 46. 全排列❤️❤️
class Solution {ListListInteger res new LinkedList();ListInteger path new LinkedList();boolean[] used;public ListListInteger permute(int[] nums) {used new boolean[nums.length];dfs( nums);return res;}private void dfs(int[] nums) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if(!used[i]){used[i] true;path.add(nums[i]);dfs(nums);used[i] false;path.remove(path.size()-1);}}}
}
47. 全排列 II❤️
class Solution {ListListInteger res new LinkedList();LinkedListInteger path new LinkedList();boolean[] used; // 判断一个元素是否被访问public ListListInteger permuteUnique(int[] nums) {used new boolean[nums.length];// 定义一个集合存放结果/******************************和46的区别*******************************/Arrays.sort(nums); // 排序/******************************和46的区别*******************************/doPermute(nums);return res;}private void doPermute(int[] nums) {if (path.size() nums.length) {res.add(new LinkedList(path));}for (int i 0; i nums.length; i) {/******************************和46的区别*******************************/if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue; // 相邻元素如果相等且前一个元素还没有被处理则跳过 【两个相邻元素只有一个可以先被处理排除重复】}/******************************和46的区别*******************************/if (!used[i]) {path.push(nums[i]);used[i] true;doPermute(nums); // 递归path.pop(); // 回溯used[i] false; // 回溯}}}
}
棋盘问题N皇后解数独等等
51. N 皇后 使用三个数组分别标记列冲突左斜线冲突右斜线冲突 根据当前位置的横坐标 X 和纵坐标 Y 计算当前位置所处的左斜线公式X Y 右斜线公式为 N - 1 - ( X - Y ) class Solution {boolean[] currCol;boolean[] leftSlash;boolean[] rightSlash;char[][] chessBoard;ListListString res new ArrayList();ListString path new ArrayList();public ListListString solveNQueens(int n) {currCol new boolean[n]; // 当前列数组大小和N皇后的N的大小相同leftSlash new boolean[2 * n - 1]; // 左斜线的大小等于2*N-1因为在N*N大小的棋盘上有2*N-1个对角线rightSlash new boolean[2 * n - 1]; // 右斜线同理chessBoard new char[n][n];for (char[] chars : chessBoard) {Arrays.fill(chars, .);}dfs(0);return res;}private void dfs(int i) {int n currCol.length;if (i n) {for (char[] chars : chessBoard) {StringBuilder stringBuilder new StringBuilder();for (char c : chars) {stringBuilder.append(c);}path.add(stringBuilder.toString());}res.add(new ArrayList(path));path.clear();}for (int j 0; j n; j) {if (currCol[j] || leftSlash[i j] || rightSlash[n - 1 - (i - j)]) {continue;}chessBoard[i][j] Q;currCol[j] true;leftSlash[i j] true;rightSlash[n - 1 - (i - j)] true;dfs(i 1);chessBoard[i][j] .;currCol[j] false;leftSlash[i j] false;rightSlash[n - 1 - (i - j)] false;}}
}
37. 解数独 解数独问题需要使用三个二维数组记录行冲突列冲突九宫格冲突 根据当前位置的横坐标 X 和纵坐标 Y 计算当前位置所处的九宫格公式为X / 3 * 3 Y / 3 class Solution {boolean[][] ca new boolean[9][9]; // 行冲突boolean[][] cb new boolean[9][9];// 列冲突boolean[][] cc new boolean[9][9];// 九宫格冲突public void solveSudoku(char[][] board) {// 记录当前数独中已经存在的数组for (int i 0; i 9; i) {for (int j 0; j 9; j) {char c board[i][j];if (c ! .) { // 如果字符不为.ca[i][c - 1] true; // 将其所在行的数字c设置为冲突(该行不能再添加c数字)cb[j][c - 1] true; // 将其所在列的数字c设置为冲突(该列不能再添加c数字)cc[i / 3 * 3 j / 3][c - 1] true; // 将其所在九宫格的数字c设置为冲突(该九宫格不能再添加c数字)}}}// 参数一正在处理的行参数二正在处理的列参数三整个二维数组dfs(0, 0, board);}private boolean dfs(int i, int j, char[][] board) {// 跳过数独中已经有数字的地方while (board[i][j] ! .) {// 超出列长则列长恢复为0行if (j 9) {j 0;i;}// i9 说明已经遍历完所有数组中的元素if (i 9) {return true;}}// 通过上面的while跳过数独中有数字的地方找到了没有数字的地方开始尝试从1~9放入数字for (int x 1; x 9; x) {// 如果添加的数字x在当前行当前列当前九宫格中有任意一个冲突则跳过尝试下一个数字if (ca[i][x - 1] || cb[j][x - 1] || cc[i / 3 * 3 j / 3][x - 1]) {continue;}// 如果没有冲突向[i,j]节点添加x数字board[i][j] (char) (x 0);// 添加完数字后更新冲突数组把当前行当前列当前九宫格中的x-1设置为trueca[i][x - 1] cb[j][x - 1] cc[i / 3 * 3 j / 3][x - 1] true;boolean dfs dfs(i, j, board); // 递归if (dfs) {return true; // 如果找到解则直接返回true}board[i][j] .; // 如果没找到解回溯ca[i][x - 1] cb[j][x - 1] cc[i / 3 * 3 j / 3][x - 1] false; //回溯}return false;}
}
