宁波咨询网站设计,淄博哪里有做网站的,佛山哪里做网站,大连网站制作网页牛客网【面试必刷TOP101】~ 06 递归/回溯 文章目录 牛客网【面试必刷TOP101】~ 06 递归/回溯[toc]BM55 没有重复项数字的全排列(★★)BM56 有重复项数字的全排列(★★)BM57 岛屿数量(★★)BM58 字符串的排列(★★)BM59 N皇后问题(★★★)BM60 括号生成(★★)BM61 矩阵最长递增路…牛客网【面试必刷TOP101】~ 06 递归/回溯 文章目录 牛客网【面试必刷TOP101】~ 06 递归/回溯[toc]BM55 没有重复项数字的全排列(★★)BM56 有重复项数字的全排列(★★)BM57 岛屿数量(★★)BM58 字符串的排列(★★)BM59 N皇后问题(★★★)BM60 括号生成(★★)BM61 矩阵最长递增路径(★★)
BM55 没有重复项数字的全排列(★★)
回溯移动元素至前
public class Solution {ArrayListArrayListInteger res;public ArrayListArrayListInteger permute (int[] nums) {res new ArrayList();if (nums null || nums.length 0) return res;ArrayListInteger lists new ArrayList();// Arrays.sort(nums);for (int num : nums) lists.add(num);backtrack(lists, 0, lists.size());return res;} private void backtrack(ArrayListInteger lists, int begin, int end) {if (begin end) {res.add(new ArrayList(lists));return;}for (int i begin; i end; i) {int val lists.remove(i);lists.add(begin, val);backtrack(lists, begin 1, end);val lists.remove(begin);lists.add(i, val);}}
}BM56 有重复项数字的全排列(★★)
排序 回溯set去重
public class Solution {ArrayListArrayListInteger res;public ArrayListArrayListInteger permuteUnique (int[] nums) {res new ArrayList();if (nums null || nums.length 0) return res;ArrayListInteger lists new ArrayList();Arrays.sort(nums);for (int num : nums) lists.add(num);backtrack(lists, 0, lists.size());return res;}private void backtrack(ArrayListInteger lists, int begin, int end) {if (begin end) {res.add(new ArrayList(lists));return;}SetInteger set new HashSet();for (int i begin; i end; i) {if (set.contains(lists.get(i))) continue;set.add(lists.get(i));int val lists.remove(i);lists.add(begin, val);backtrack(lists, begin 1, end);lists.remove(begin);lists.add(i, val);}}}BM57 岛屿数量(★★)
方法一回溯120ms
public class Solution {private static int[] dirs {-1, 0, 1, 0, -1}; public int solve (char[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) return 0;int count 0;int r grid.length, c grid[0].length;for (int i 0; i r; i) {for (int j 0; j c; j) {if (grid[i][j] 0) continue;dfs(grid, i, j, r, c);count;}}return count;}private void dfs(char[][] grid, int i, int j, int r, int c) {if (i 0 || j 0 || i r || j c || grid[i][j] 0) {return;}grid[i][j] 0;for (int d 0; d 4; d) {int x i dirs[d], y j dirs[d 1];dfs(grid, x, y, r, c);}}}更直观的定义
public class Solution {public int solve (char[][] grid) {int count 0;for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 0) continue;sinkLand(grid, i, j);count;}}return count;}private void sinkLand(char[][] grid, int i, int j) {if (i 0 || j 0 || i grid.length || j grid[0].length || grid[i][j] 0) {return;}grid[i][j] 0;sinkLand(grid, i - 1, j);sinkLand(grid, i 1, j);sinkLand(grid, i, j - 1);sinkLand(grid, i, j 1);}}BM58 字符串的排列(★★)
同BM56有重复字符的全排列
public class Solution {ArrayListString res;public ArrayListString Permutation (String str) {res new ArrayList();if (str null || str.equals()) return res;char[] cs str.toCharArray();Arrays.sort(cs);backtrack(cs, 0, cs.length);return res;}private void backtrack(char[] cs, int begin, int end) {if (begin end) {res.add(new String(cs));return;}SetCharacter set new HashSet();for (int i begin; i end; i) {if (set.contains(cs[i])) continue;set.add(cs[i]);swap(cs, begin, i);backtrack(cs, begin 1, end);swap(cs, begin, i);}}private void swap(char[] cs, int i, int j) {char c cs[i];cs[i] cs[j];cs[j] c;}
}BM59 N皇后问题(★★★)
public class Solution {private int count;private int[] x;public int Nqueen (int n) {count 0;x new int[n];Arrays.fill(x, -1);backtrack(n);return count;}private void backtrack(int n) {int k 0;while (k 0) {x[k];while (x[k] n isClash(k)) x[k];if (x[k] n k n - 1) count;if (x[k] n k n - 1) {k;} else {x[k--] -1;}}}private boolean isClash(int k) {for (int i 0; i k; i) {if (x[i] x[k] || Math.abs(i - k) Math.abs(x[i] - x[k])) {return true;}}return false;}}BM60 括号生成(★★)
递归
public class Solution {public ArrayListString res;public ArrayListString generateParenthesis (int n) {res new ArrayList();dfs(new String(), n, n);return res;}private void dfs(String s, int le, int ri) {if (le ri || le 0 || ri 0) return;if (le 0 ri 0) {res.add(s);return;}dfs(s (, le - 1, ri);dfs(s ), le, ri - 1);}
}BM61 矩阵最长递增路径(★★)
dfs记忆化搜索
public class Solution {private static final int[] dirs {-1, 0, 1, 0, -1};private int[][] ms;private int R, C;public int solve (int[][] matrix) {if (matrix null || matrix.length 0 || matrix[0].length 0) {return 0;}R matrix.length;C matrix[0].length;ms new int[R][C];int res 0;for (int i 0; i R; i) {for (int j 0; j C; j) {res Math.max(res, dfs(matrix, i, j));} }return res;}private int dfs(int[][] matrix, int i, int j) {if (ms[i][j] ! 0) return ms[i][j];ms[i][j];for (int k 0; k 4; k) {int x i dirs[k], y j dirs[k 1];if (x 0 || y 0 || x R || y C || matrix[i][j] matrix[x][y]) {continue;}ms[i][j] Math.max(ms[i][j], dfs(matrix, x, y) 1);}return ms[i][j];}}
