回溯---java---黑马

回溯

概念

程序在运行过程中分成了多个阶段

通过某些手段，将数据恢复到某一阶段，称之为回溯

手段包括：方法栈、自定义栈

使用基本数据类型n

java">public class Backtracking{public static void main(String[] args) {rec(1);}public void rec(int n) {if (n == 3) {return ;}System.out.println(n);rec(n + 1);System.out.println(n);}
}

使用引用数据类型

java">public class Backtracking{public static void main(String[] args) {rec(1, new LinkedList<>());}public void rec(int n, LinkedList<String> list) {if (n == 3) {return ;}System.out.println("before" + list);list.add('a');rec(n + 1, list);// list.pop();System.out.println("after" + list);}
}

全排列

leetcode46

java">public class Leetcode46{public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>(); boolean[] visited = new boolean[nums.length];dfs(nums, visited, new LinkedList<>(), res)}public void dfs(int[] nums, boolean[] visited, LinkedList<String> stack, List<List<Integer>> res) {if (stack.size() == nums.length) {res.add(new ArrayList<>(stack));return;}for(int i = 0; i < nums.length; i++) {if (!visited[i]) {stack.push(nums[i]);visited[i] = true;dfs(nums, visited, stack, res);visited[i] = false;stack.pop();}}}
}

当数组中存在重复元素时，需要去掉重复元素的排列,前提是要排序数组

java">public class Leetcode46{public List<List<Integer>> permute(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>(); boolean[] visited = new boolean[nums.length];dfs(nums, visited, new LinkedList<>(), res)}public void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> res) {if (stack.size() == nums.length) {res.add(new ArrayList<>(stack));return;}for(int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {continue;}if (!visited[i]) {stack.push(nums[i]);visited[i] = true;dfs(nums, visited, stack, res);visited[i] = false;stack.pop();}}}
}

组合

Leetcode77

java">public class Leetcode77{public List<List<Integer>> combine(int n) {List<List<Integer>> res = new ArrayList<>(); dfs(1, n, k, new LinkedList<>(), res);}public void dfs(int start, int n, int k, LinkedList<Integer> stack, List<List<Integer>> res) {if (stack.size() == k) {res.add(new ArrayList<>(stack));return;}for(int i = start, i <= n; i++) {if (k - stack.size() > n - i + 1) {continue;}    stack.push(i);dfs(i + 1, n, k, stack, res);stack.pop(i);}}
}

Leetcode39

java">public class Leetcode39{public List<List<Integer>> combinationSum(int[] nums, int k) {List<List<Integer>> res = new ArrayList<>();dfs(nums, 0, k, new LinkedList<>(), res);return res;}public void dfs(int[] nums, int start, int target, LinkedList<Integer> stack, List<List<Integer>> res) {if (target == 0) {res.add(new ArrayList<>(stack));}for(int i = start; i < nums.length; i++) {if (target < nums[i]) {continue;}stack.push(nums[i]);dfs(nums, i, target - nums[i], stack, res);stack.pop();}}
}

Leetcode40

java">public class Leetcode40{public List<List<Integer>> combinationSum(int[] nums, int k) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);dfs(nums, 0, k, new boolean[], new LinkedList<>(), res);return res;}public void dfs(int[] nums, int start, int target, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> res) {if (target == 0) {res.add(new ArrayList<>(stack));}for(int i = start; i < nums.length; i++) {if (target < nums[i]) {continue;}if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {continue;}stack.push(nums[i]);visited[i] = true;dfs(nums, i + 1, target - nums[i], stack, res);visited[i] = false;stack.pop();}}
}

Leetcode216

java">public class Leetcode216{public List<List<Integer>> combinationSum(int k, int target) {List<List<Integer>> res = new ArrayList<>();dfs(1, k, target, new LinkedList<>(), res);return res;}public void dfs(int start, int k, int target, new LinkedList<Integer> stack, List<List<Integer>> res) {if (stack.size() == k && target == 0) {res.add(new ArrayList<>(stack));}for(int i = start, int i <= 9; i++) {if (target < i) {continue;}if (stack.size() == k) {continue;}stack.push(i);dfs(i + 1, k, target - i, stack, res);stack.pop();}}
}

Leetcode51-N皇后

java">public class Leetcode51{public static void main(String[] args) {int n = 4;boolean[] ca = new boolean[n];boolean[] cb = new boolean[2 * n - 1];boolean[] cc = new boolean[2 * n - 1];char[][] board = new char[n][n];List<List<String>> res = new ArrayList<>();for(char[] b : board) {Arrays.fill(b, '.');}dfs(0, n, board, ca, cb, cc, res);return res;}public void dfs(int i, int n, char[][] board, boolean[] ca, boolean[] cb, boolean[] cc, List<List<String>> res) {if (i == n) {List<String> list = new ArrayList<>();for(char[] b : board) {list.add(new String(b));}res.add(list);return;}for(int j = 0; j < n; j++) {if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {continue;}board[i][j] = 'Q';ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true;dfs(i + 1, n, board, ca, cb, cc, res);ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;board[i][j] = '.';}}
}

Leetcode37解数独

java">public class Leetcode37{public void solveSudoku(char[][] board) {int n = board.length;boolean[][] ca = new boolean[n][n];boolean[][] cb = new boolean[n][n];boolean[][] cc = new boolean[n][n];for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {char ch = board[i][j];if (ch != '.') {ca[i][ch - '1'] = true;cb[j][ch - '1'] = true;cc[i / 3 * 3 + j / 3][ch - '1'] = true;}}}dfs(0, 0, board, ca, cb, cc);}public static boolean dfs(int i, int j, char[][] board, boolean[][] ca, boolean[][] cb, boolean[][] cc) {while (board[i][j] != '.') {if (++j >= 9) {j = 0;i++;}if (i >= 9) {return true;}}for(int x = 1; x <= 9; x++) {if (ca[i][x - 1] || cb[j][x - 1] || cc[i / 3 * 3 + j / 3][x - 1]) {continue;}board[i][j] = (char) (x + '0');ca[i][x - 1] = cb[j][x - 1] = cc[i / 3 * 3 + j / 3][x - 1] = true;if (dfs(i, j, board, ca, cb, cc)) {return true;}ca[i][x - 1] = cb[j][x - 1] = cc[i / 3 * 3 + j / 3][x - 1] = false;board[i][j] = '.';}return false;}
}

Leetcode167-两数之和

java">public class Leetcode167{public int[] twoSum(int[] nums, int target) {int i = 0;int j = nums.length - 1;while (i < j) {if (nums[i] + nums[j] < target) {i++;} else if (nums[i] + nums[j] > target) {j--;} else {break;}}return new int[]{i + 1, j + 1};}
}

java">public class Leetcode167{public int[] twoSum(int[] nums, int target) {int n = nums.length;for(int i = 0; i < n; i++) {int left = i + 1;int t = target - nums[i];int right = n - 1;while (left <= right) {int m = (left + right) >>> 1;if (t < nums[m]) {j = m - 1;} else if (t > nums[m]) {i = m + 1;} else {return new int[]{i + 1, m + 1};}}}return null;}
}

Leetcode15-三数之和

java">public class Leetcode15{public List<List<Integer>> threeSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>>res = new ArrayList<>();int n = nums.length;dfs(3, 0, n - 1, target, new LinkedList<>(), res);return res;}public void dfs(int n, int i, int j, int target, int[] nums, LinkedList<Integer> stack, List<List<Integer>> res) {if (n == 2) {// 两数之和twoSum(i, j, target, nums, stack, res);}for(int k = i; k < j; k++) {if (k > i && nums[k] == nums[k - 1]) {continue;}stack.push(nums[k]);dfs(n - 1, k + 1, j, target - nums[k], nums, stack, res);stack.pop();}}public void twoSum(int i, int j, int target, int[] nums, LinkedList<Integer> stack, List<List<Integer>> res) {while (i < j) {if (nums[i] + nums[j] < target) {i++;} else if (nums[i] + nums[j] > target) {j--;} else {List<Integer> list = new ArrayList<>(stack);list.add(nums[i]);list.add(nums[j]);res.add(list);i++;j--;while (i < j && nums[i] == nums[i - 1]) {i++;}while (i < j && nums[j] == nums[j + 1]) {j--;}}}}
}

Leetcode18-四数之和

java">public class Leetcode15{public List<List<Integer>> threeSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>>res = new ArrayList<>();int n = nums.length;dfs(4, 0, n - 1, target, new LinkedList<>(), res);return res;}public void dfs(int n, int i, int j, int target, int[] nums, LinkedList<Integer> stack, List<List<Integer>> res) {if (n == 2) {// 两数之和twoSum(i, j, target, nums, stack, res);}for(int k = i; k < j - (n - 2); k++) {if (k > i && nums[k] == nums[k - 1]) {continue;}stack.push(nums[k]);dfs(n - 1, k + 1, j, target - nums[k], nums, stack, res);stack.pop();}}public void twoSum(int i, int j, int target, int[] nums, LinkedList<Integer> stack, List<List<Integer>> res) {while (i < j) {if (nums[i] + nums[j] < target) {i++;} else if (nums[i] + nums[j] > target) {j--;} else {List<Integer> list = new ArrayList<>(stack);list.add(nums[i]);list.add(nums[j]);res.add(list);i++;j--;while (i < j && nums[i] == nums[i - 1]) {i++;}while (i < j && nums[j] == nums[j + 1]) {j--;}}}}
}

Leetcode11

java">public class Leetcode11{public int MostWaterLeetcode11(int[] height) {int i = 0; int j = height.length - 1;int max = 0;while (i < j) {if (nums[i] <= nums[j]) {i++;} else {j--;}max = Integer.max(max, Integer.min(nums[i], nums[j]) * (j - i + 1))}retu}}