leetcode——backtracking -ag凯发k8国际
ag凯发k8国际
收集整理的这篇文章主要介绍了
leetcode——backtracking
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
目录
1. backtracking
backtracking（回溯）属于 dfs。
普通 dfs 主要用在可达性问题，这种问题只需要执行到特点的位置然后返回即可。
而 backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。
因为 backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。
2. 数字键盘组合
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
3. ip 地址划分
https://leetcode-cn.com/problems/restore-ip-addresses
public list<string> restoreipaddresses(string s) {list<string> addresses = new arraylist<>();stringbuilder tempaddress = new stringbuilder();dorestore(0, tempaddress, addresses, s);return addresses;}private void dorestore(int k, stringbuilder tempaddress, list<string> addresses, string s) {//整体分成4个段if (k == 4 || s.length() == 0) {if (k == 4 && s.length() == 0) {addresses.add(tempaddress.tostring());}return;}//每个段的判断for (int i = 0; i < s.length() && i <= 2; i) {if (i != 0 && s.charat(0) == '0') {break;}string part = s.substring(0, i 1);if (integer.valueof(part) <= 255) {if (tempaddress.length() != 0) {part = "." part;}tempaddress.append(part);dorestore(k 1, tempaddress, addresses, s.substring(i 1));tempaddress.delete(tempaddress.length() - part.length(), tempaddress.length());}}}4. 在矩阵中寻找字符串
https://leetcode-cn.com/problems/word-search
题目描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private int m, n;public boolean exist(char[][] board, string word) {if (word == null || word.length() == 0) {return true;}if (board == null || board.length == 0 || board[0].length == 0) {return false;}m = board.length;n = board[0].length;boolean[][] visited = new boolean[m][n];for (int r = 0; r < m; r) {for (int c = 0; c < n; c) {if (backtracking(0, r, c, visited, board, word)) {return true;}}}return false;}private boolean backtracking(int curlen, int r, int c, boolean[][] visited, final char[][] board, final string word) {if (curlen == word.length()) {return true;}if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charat(curlen) || visited[r][c]) {return false;}visited[r][c] = true;for (int[] d : direction) {if (backtracking(curlen 1, r d[0], c d[1], visited, board, word)) {return true;}}visited[r][c] = false;return false;}5. 输出二叉树中所有从根到叶子的路径
https://leetcode.com/problems/binary-tree-paths
6. 排列
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
7. 含有相同元素求排列
题目描述：数组元素可能含有相同的元素，进行排列时就有可能出现重复的排列，要求重复的排列只返回一个。
在实现上，和 permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。
public list<list<integer>> permuteunique(int[] nums) {list<list<integer>> permutes = new arraylist<>();list<integer> permutelist = new arraylist<>();arrays.sort(nums);boolean[] hasvisited = new boolean[nums.length];backtracking(permutelist, permutes, hasvisited, nums);return permutes;}private void backtracking(list<integer> permutelist, list<list<integer>> permutes, boolean[] visited, int[] nums) {if (permutelist.size() == nums.length) {permutes.add(new arraylist<>(permutelist));return;}for (int i = 0; i < visited.length; i) {if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {continue; //防止重复}if (visited[i]) {continue;}visited[i] = true;permutelist.add(nums[i]);backtracking(permutelist, permutes, visited, nums);permutelist.remove(permutelist.size() - 1);visited[i] = false;}}8. 组合
https://leetcode-cn.com/problems/combinations
9. 组合求和
https://leetcode.com/problems/combination-sum/description/
题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
10. 含有相同元素的组合求和
https://leetcode.com/problems/combination-sum-ii/description/
题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
11. 1-9 数字的组合求和
https://leetcode.com/problems/combination-sum-iii/description/
题目描述：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
12. 子集
https://leetcode.com/problems/subsets-ii/description/
题目描述：找出集合的所有子集，子集不能重复，[1, 2] 和 [2, 1] 这种子集算重复
13. 含有相同元素求子集
题目描述：给定一个可能包含重复数的整数集合，返回所有可能的子集(幂集)。
注意:ag凯发k8国际的解决方案集不能包含重复的子集。
public list<list<integer>> subsets(int[] nums) {list<list<integer>> subsets = new arraylist<>();list<integer> tempsubset = new arraylist<>();for (int size = 0; size <= nums.length; size) {backtracking(subsets, tempsubset, size, 0, nums);}return subsets;}private void backtracking(list<list<integer>> subsets, list<integer> tempsubset, int size, int start, int[] nums) {if (size == 0) {subsets.add(new arraylist<>(tempsubset));}for (int i = start; i < nums.length; i) {tempsubset.add(nums[i]);backtracking(subsets, tempsubset, size - 1, i 1, nums);tempsubset.remove(tempsubset.size() - 1);}}14. 分割字符串使得每个部分都是回文数
https://leetcode-cn.com/problems/palindrome-partitioning
题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
public list<list<string>> partition(string s) {list<list<string>> partitions = new arraylist<>();list<string> temppartition = new arraylist<>();dopartition(s, partitions, temppartition);return partitions;}private void dopartition(string s, list<list<string>> partitions, list<string> temppartition) {if (s.length() == 0) {partitions.add(new arraylist<>(temppartition));return;}for (int i = 0; i < s.length(); i) {if (ispalindrome(s, 0, i)) {temppartition.add(s.substring(0, i 1));dopartition(s.substring(i 1), partitions, temppartition);temppartition.remove(temppartition.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;}15. 数独
https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/
题目描述：编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
- 空白格用 ‘.’ 表示。
16. n皇后
https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode/
题目描述：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的ag凯发k8国际的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘q’ 和 ‘.’ 分别代表了皇后和空位。
private list<list<string>> solutions;private char[][] nqueues;private boolean[] colused;private boolean[] diagonals45used;private boolean[] diagonals135used;private int n;public list<list<string>> solvenqueues(int n) {solutions = new arraylist<>();nqueues = new char[n][n];for (int i = 0; i < n; i) {arrays.fill(nqueues[i], '.');}colused = new boolean[n];diagonals45used = new boolean[2 * n - 1];diagonals135used = new boolean[2 * n - 1];this.n = n;backtracking(0);return solutions;}private void backtracking(int row) {if (row == n) {list<string> list = new arraylist<>();for (char[] chars : nqueues) {list.add(new string(chars));}solutions.add(list);return;}for (int col = 0; col < n; col) {int diagonals45idx = row col;int diagonals135idx = n - 1 - (row - col);if (colused[col] || diagonals45used[diagonals45idx] || diagonals135used[diagonals135idx]) {continue;}nqueues[row][col] = 'q';colused[col] = diagonals45used[diagonals45idx] = diagonals135used[diagonals135idx] = true;backtracking(row 1);colused[col] = diagonals45used[diagonals45idx] = diagonals135used[diagonals135idx] = false;nqueues[row][col] = '.';}}总结
以上是ag凯发k8国际为你收集整理的leetcode——backtracking的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇：
- 下一篇：