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

素颜马尾好姑娘i 2023-10-14 18:41 54阅读 0赞

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);
            }
        }
    }