算法练习（6）：牛客在线编程06 递归/回溯

package jz.bm;import java.io.PushbackInputStream;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;public class bm6 {/*** BM55 没有重复项数字的全排列*/ArrayList<ArrayList<Integer>> res = new ArrayList<>();public ArrayList<ArrayList<Integer>> permute(int[] num) {if (num.length == 0) {return res;}Arrays.sort(num);boolean[] used = new boolean[num.length];Arrays.fill(used, false);dfs(num, used, new ArrayList<>());return res;}private void dfs(int[] num, boolean[] used, ArrayList<Integer> list) {if (list.size() == num.length) {res.add(new ArrayList<>(list));} else {for (int i = 0; i < num.length; i++) {if (used[i]) {continue;}used[i] = true;list.add(num[i]);dfs(num, used, list);used[i] = false;list.remove(list.size() - 1);}}}/*** BM56 有重复项数字的全排列*/public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {if (num.length == 0) {return res;}Arrays.sort(num);boolean[] used = new boolean[num.length];Arrays.fill(used, false);dfs56(num, used, new ArrayList<>());return res;}private void dfs56(int[] num, boolean[] used, ArrayList<Integer> list) {if (list.size() == num.length) {res.add(new ArrayList<>(list));} else {for (int i = 0; i < num.length; i++) {if (used[i]) {continue;}if (i > 0 && num[i] == num[i - 1] && used[i - 1]) {continue;}used[i]  = true;list.add(num[i]);dfs56(num, used, list);used[i] = false;list.remove(list.size() - 1);}}}/*** BM57 岛屿数量*/public int solve (char[][] grid) {int m = grid.length;if (m == 0) {return 0;}int n = grid[0].length;if (n == 0) {return 0;}int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {res++;dfs57(grid, m, n, i, j);}}}return res;}private void dfs57(char[][] grid, int m, int n, int i, int j) {grid[i][j] = '0';if (i - 1 >= 0 && grid[i - 1][j] == '1') {dfs57(grid, m, n, i - 1, j);}if (i + 1 < m && grid[i + 1][j] == '1') {dfs57(grid, m, n, i + 1, j);}if (j - 1 >= 0 && grid[i][j - 1] == '1') {dfs57(grid, m, n, i, j - 1);}if (j + 1 < n && grid[i][j + 1] == '1') {dfs57(grid, m, n, i, j + 1);}}/*** BM58 字符串的排列*/ArrayList<String> strings = new ArrayList<>();public ArrayList<String> Permutation(String str) {if (str == null || "".equals(str)) {return strings;}char[] chars = str.toCharArray();Arrays.sort(chars);boolean[] used = new boolean[chars.length];Arrays.fill(used, false);dfs58(chars, used, new StringBuilder());return strings;}private void dfs58(char[] chars, boolean[] used, StringBuilder stringBuilder) {if (stringBuilder.length() == chars.length) {strings.add(new String(stringBuilder));} else {for (int i = 0; i < chars.length; i++) {if (used[i]) {continue;}if (i > 0 && chars[i] == chars[i - 1] && used[i - 1]) {continue;}stringBuilder.append(chars[i]);used[i] = true;dfs58(chars, used, stringBuilder);used[i] = false;stringBuilder.deleteCharAt(stringBuilder.length() - 1);}}}/*** BM60 括号生成*/ArrayList<String> arrayList = new ArrayList<>();public ArrayList<String> generateParenthesis (int n) {if (n == 0) {return arrayList;}dfs60(n, 0, 0, new StringBuilder());return arrayList;}private void dfs60(int n, int left, int right, StringBuilder stringBuilder) {if (left == n && right == n) {arrayList.add(new String(stringBuilder));return;}if (left < n) {stringBuilder.append("(");dfs60(n, left + 1, right, stringBuilder);stringBuilder.deleteCharAt(left + right);}if (right < left && right < n) {stringBuilder.append(")");dfs60(n, left, right + 1, stringBuilder);stringBuilder.deleteCharAt(left + right);}}/*** BM61 矩阵最长递增路径*/int max = 0;public int solve (int[][] matrix) {int m = matrix.length;int n = matrix[0].length;//这题dfs不需要记录visited, 因为能走的路径是单向的for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs61(matrix, m, n, i, j, 1);}}return max;}private void dfs61(int[][] matrix, int m, int n, int i, int j, int count) {if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i - 1, j, count + 1);}if (i + 1 < m &&  matrix[i + 1][j] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i + 1, j, count + 1);}if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i, j - 1, count + 1);}if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i, j + 1, count + 1);}}
}