DFS 学习笔记

叁歲伎倆 2024-03-26 09:05 35阅读 0赞

### leetcode面试题 08.07. 无重复字符串的排列组合 ###

#### 方式1：第一步→DFS基本模板 ####

public static String[] permutation(String S) {
        
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(S, sb, res);
        
        return res.toArray(String[]::new);
    }
    
    public static void dfs(String str, StringBuilder sb, List<String> res) {
        
        if (sb.length() == 变量) {
        
            res.add(sb.toString());
            return;
        }
        
        for (int i = 0; i < str.length(); i++) {
        
            sb.append(str.charAt(i));
            dfs(str, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    输入："qwe"
    
    变量=1→3
    ["q","w","e"]
    
    变量=2 → 3*3=9
    ["qq","qw","qe","wq","ww","we","eq","ew","ee"]
    
    变量= 3→ 3*3*3=27
    ["qqq","qqw","qqe","qwq","qww","qwe","qeq","qew","qee","wqq","wqw","wqe","wwq","www","wwe","weq","wew","wee","eqq","eqw","eqe","ewq","eww","ewe","eeq","eew","eee"]
    
    变量=4 → 3*3*3*3=81
    ["qqqq","qqqw","qqqe","qqwq","qqww","qqwe","qqeq","qqew","qqee","qwqq","qwqw","qwqe","qwwq","qwww","qwwe","qweq","qwew","qwee","qeqq","qeqw","qeqe","qewq","qeww","qewe","qeeq","qeew","qeee","wqqq","wqqw","wqqe","wqwq","wqww","wqwe","wqeq","wqew","wqee","wwqq","wwqw","wwqe","wwwq","wwww","wwwe","wweq","wwew","wwee","weqq","weqw","weqe","wewq","weww","wewe","weeq","weew","weee","eqqq","eqqw","eqqe","eqwq","eqww","eqwe","eqeq","eqew","eqee","ewqq","ewqw","ewqe","ewwq","ewww","ewwe","eweq","ewew","ewee","eeqq","eeqw","eeqe","eewq","eeww","eewe","eeeq","eeew","eeee"]

#### 方式1：第二步→DFS排除自己 ####

public static String[] permutation(String S) {
        
        List<String> res = new ArrayList<>();
        boolean[] visited = new boolean[S.length()];
        StringBuilder sb = new StringBuilder();
        dfs(S, sb, visited, res);
        
        return res.toArray(String[]::new);
    }
    
    public static void dfs(String str, StringBuilder sb, boolean[] isVisited, List<String> res) {
        
        if (sb.length() == 变量) {
        
            res.add(sb.toString());
            return;
        }
        
        for (int i = 0; i < str.length(); i++) {
        
            if (isVisited[i]) {
        
                continue;
            }
            
            sb.append(str.charAt(i));
            isVisited[i] = true;
            
            dfs(str, sb, isVisited, res);
            
            sb.deleteCharAt(sb.length() - 1);
            isVisited[i] = false;
        }
    }
    
    输入："qwe"
    
    变量=1
    ["q","w","e"]
    
    变量=2
    ["qw","qe","wq","we","eq","ew"]
    
    变量=3
    ["qwe","qew","wqe","weq","eqw","ewq"]
    
    变量=4
    []

### leetcode面试题 08.08. 有重复字符串的排列组合 ###

对于如上两个方法场景
    
    场景1：DFS基本模板
    
    输入："qww"
    
    变量=1
    ["q","w","w"]
    
    变量=2
    ["qq","qw","qw","wq","ww","ww","wq","ww","ww"]
    
    变量=3
    ["qqq","qqw","qqw","qwq","qww","qww","qwq","qww","qww","wqq","wqw","wqw","wwq","www","www","wwq","www","www","wqq","wqw","wqw","wwq","www","www","wwq","www","www"]
    
    变量=4
    ["qqqq","qqqw","qqqw","qqwq","qqww","qqww","qqwq","qqww","qqww","qwqq","qwqw","qwqw","qwwq","qwww","qwww","qwwq","qwww","qwww","qwqq","qwqw","qwqw","qwwq","qwww","qwww","qwwq","qwww","qwww","wqqq","wqqw","wqqw","wqwq","wqww","wqww","wqwq","wqww","wqww","wwqq","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","wwqq","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","wqqq","wqqw","wqqw","wqwq","wqww","wqww","wqwq","wqww","wqww","wwqq","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","wwqq","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww"]
    
    
    场景2：DFS排除自己
    
    变量=1
    ["q","w","w"]
    
    变量=2
    ["qw","qw","wq","ww","wq","ww"]
    
    变量=3
    ["qww","qww","wqw","wwq","wqw","wwq"]
    
    变量=4
    []
    
    场景2去重时只排除了自己，并没有排除不同位置相同的元素

如上去重时只排除了自己，并没有排除不同位置相同的元素

#### 方式1：追加去重逻辑 ####

public static String[] permutation(String S) {
        
        char[] arr = S.toCharArray();
        
        // 排序之后，相同字符位于字符数组中的相邻位置，可以利用这一特点去重
        Arrays.sort(arr);
        
        boolean[] visited = new boolean[S.length()]; // 标记是否走过
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(new String(arr), sb, visited, res);
        
        // 输出指定格式
        return res.toArray(String[]::new);
    }
    /**
     * @param str     素材字符串
     * @param sb      拼接字符串的临时变量
     * @param visited 标记是否走过
     * @param res     收集结果
     */
    public static void dfs(String str, StringBuilder sb, boolean[] visited, List<String> res) {
        
        if (sb.length() == 变量) {
        
            res.add(sb.toString());
            return;
        }
        
        for (int i = 0; i < str.length(); i++) {
        
            // 去重时排除自己
            // 已经加入当前排列，则不能多次加入当前排列
            if (visited[i]) {
        
                continue;
            }
            
            // 确保arr[i−1]在arr[i]前加入排列
            // arr[i−1]未加入当前排列,则不能将arr[i]加入当前排列,否则arr[i−1]将在arr[i]之后加入当前排列,导致出现重复排列
            if (0 < i && str.charAt(i) == str.charAt(i - 1) && !visited[i - 1]) {
        
                continue;
            }
            
            // 递归下去
            sb.append(str.charAt(i));
            visited[i] = true;
            
            dfs(str, sb, visited, res);
            
            // 回溯上来
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    输入："qww"
    
    变量=1
    [q, w]
    
    变量=2
    [qw, wq, ww]
    
    变量=3
    [qww, wqw, wwq]
    
    变量=4
    []

#### 方式2：08.07基础直接去重 ####

public static String[] permutation(String S) {
        
        List<String> res = new ArrayList<>();
        boolean[] visited = new boolean[S.length()];
        StringBuilder sb = new StringBuilder();
        dfs(S, sb, visited, res);
        
        // 去重
        List<String> collect = res.stream().distinct().collect(Collectors.toList());
        
        return collect.toArray(String[]::new);
    }
    public static void dfs(String str, StringBuilder sb, boolean[] isVisited, List<String> res) {
        
        if (sb.length() == 变量) {
        
            res.add(sb.toString());
            return;
        }
        
        for (int i = 0; i < str.length(); i++) {
        
            if (isVisited[i]) {
        
                continue;
            }
            
            sb.append(str.charAt(i));
            isVisited[i] = true;
            
            dfs(str, sb, isVisited, res);
            
            sb.deleteCharAt(sb.length() - 1);
            isVisited[i] = false;
        }
    }
    
    输入："qww"
    
    变量=1
    [q, w]
    
    变量=2
    [qw, wq, ww]
    
    变量=3
    [qww, wqw, wwq]
    
    变量=4
    []

### leetcode77. 组合 ###

public static List<List<Integer>> combine(int n, int k) {
        
        List<List<Integer>> res = new ArrayList<>();
        // 范围 [1, n] 中所有可能的 k 个数的组合
        // k<=0时没意义;
        // n<k时没意义,一共才n个想取k个不合理
        if (k <= 0 || n < k) {
        
            return res;
        }
        Deque<Integer> stack = new LinkedList<>();
        dfs(1, n, k, stack, res);
        return res;
    }
    
    public static void dfs(int start, int milestone, int limit, Deque<Integer> stack, List<List<Integer>> res) {
        
        if (stack.size() == limit) {
         // 一共收集limit层,已经收集到limit层时直接收工大退
            res.add(new ArrayList<>(stack));
            System.out.println(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i <= milestone; i++) {
        
            stack.push(i);
            dfs(i + 1, milestone, limit, stack, res);
            stack.pop();
        }
    }
    
    范围 [1, 5] 中所有可能的 3 个数的组合
    [3, 2, 1]
    [4, 2, 1]
    [5, 2, 1]
    [4, 3, 1]
    [5, 3, 1]
    [5, 4, 1]
    [4, 3, 2]
    [5, 3, 2]
    [5, 4, 2]
    [5, 4, 3]
    
    public static void dfs(int start, int milestone, int limit, Deque<Integer> stack, List<List<Integer>> res) {
        
        res.add(new ArrayList<>(stack));
        
        System.out.println(new ArrayList<>(stack));
        for (int i = start; i <= milestone; i++) {
        
            stack.push(i);
            dfs(i + 1, milestone, limit, stack, res);
            stack.pop();
        }
    }
    
    所有CASE:
    []
    [1]
    [2, 1]
    [3, 2, 1]
    [4, 3, 2, 1]
    [5, 4, 3, 2, 1]
    [5, 3, 2, 1]
    [4, 2, 1]
    [5, 4, 2, 1]
    [5, 2, 1]
    [3, 1]
    [4, 3, 1]
    [5, 4, 3, 1]
    [5, 3, 1]
    [4, 1]
    [5, 4, 1]
    [5, 1]
    [2]
    [3, 2]
    [4, 3, 2]
    [5, 4, 3, 2]
    [5, 3, 2]
    [4, 2]
    [5, 4, 2]
    [5, 2]
    [3]
    [4, 3]
    [5, 4, 3]
    [5, 3]
    [4]
    [5, 4]
    [5]

### leetcode491 找出整数数组中不同的递增子序列 ###

#### 方式1：第一步→DFS 基本模板 ####

public static List<List<Integer>> findSubsequences(int[] nums) {
        
        if (nums == null || nums.length < 2) {
        
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();
        dfs(0, nums, queue, res);
        
        return res.stream().distinct().collect(Collectors.toList());
    }
    
    public static void dfs(int start, int[] arr, Deque<Integer> queue, List<List<Integer>> res) {
        
        res.add(new ArrayList<>(queue));
        System.out.println(new ArrayList<>(queue));
        
        for (int i = start; i < arr.length; i++) {
        
            queue.addLast(arr[i]);
            dfs(i + 1, arr, queue, res);
            queue.removeLast();
        }
    }
    
    输入源：1 2 3 4
    
    []
    [1]
    [1, 2]
    [1, 2, 3]
    [1, 2, 3, 4]
    [1, 2, 4]
    [1, 3]
    [1, 3, 4]
    [1, 4]
    [2]
    [2, 3]
    [2, 3, 4]
    [2, 4]
    [3]
    [3, 4]
    [4]
    
    输入：4 6 3 7 7
    
    []
    [4]
    [4, 6]
    [4, 6, 3]
    [4, 6, 3, 7]
    [4, 6, 3, 7, 7]
    [4, 6, 3, 7]
    [4, 6, 7]
    [4, 6, 7, 7]
    [4, 6, 7]
    [4, 3]
    [4, 3, 7]
    [4, 3, 7, 7]
    [4, 3, 7]
    [4, 7]
    [4, 7, 7]
    [4, 7]
    [6]
    [6, 3]
    [6, 3, 7]
    [6, 3, 7, 7]
    [6, 3, 7]
    [6, 7]
    [6, 7, 7]
    [6, 7]
    [3]
    [3, 7]
    [3, 7, 7]
    [3, 7]
    [7]
    [7, 7]
    [7]

#### 方式1：第二步→只保留升序的元素 ####

public static List<List<Integer>> findSubsequences(int[] nums) {
        
        if (nums == null || nums.length < 2) {
        
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();
        dfs(0, nums, queue, res);
        
        return res.stream().distinct().collect(Collectors.toList());
    }
    
    public static void dfs(int start, int[] arr, Deque<Integer> queue, List<List<Integer>> res) {
        
        res.add(new ArrayList<>(queue));
        System.out.println(new ArrayList<>(queue));
        
        for (int i = start; i < arr.length; i++) {
        
            if (!queue.isEmpty() && queue.getLast() > arr[i]) {
        
                continue; // 不满足递增子序列(两整数相等视作递增)条件时，继续处理下一个数据
            }
            
            queue.addLast(arr[i]);
            dfs(i + 1, arr, queue, res);
            queue.removeLast();
        }
    }
    
    输入：4 6 3 7 7
    
    []
    [4]
    [4, 6]
    [4, 6, 7]
    [4, 6, 7, 7]
    [4, 6, 7]
    [4, 7]
    [4, 7, 7]
    [4, 7]
    [6]
    [6, 7]
    [6, 7, 7]
    [6, 7]
    [3]
    [3, 7]
    [3, 7, 7]
    [3, 7]
    [7]
    [7, 7]
    [7]

#### 方式1：第三步→（升序）+（>=2）+（去重） ####

/**
     * leetcode491 找出整数数组中不同的递增子序列
     */
    public static List<List<Integer>> findSubsequences(int[] nums) {
        
        if (nums == null || nums.length < 2) {
        
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();
        dfs(0, nums, queue, res);
        
        return res.stream().distinct().collect(Collectors.toList());
    }
    
    public static void dfs(int start, int[] arr, Deque<Integer> queue, List<List<Integer>> res) {
        
        if (queue.size() >= 2) {
         // 满足条件就快照一下
            res.add(new ArrayList<>(queue));
            System.out.println(new ArrayList<>(queue));
        }
        
        for (int i = start; i < arr.length; i++) {
        
            if (!queue.isEmpty() && queue.getLast() > arr[i]) {
        
                continue; // 不满足递增子序列(两整数相等视作递增)条件时，继续处理下一个数据
            }
            queue.addLast(arr[i]);
            dfs(i + 1, arr, queue, res);
            queue.removeLast();
        }
    }
    
    输入源：4 6 3 7 7
    [4, 6]
    [4, 6, 7]
    [4, 6, 7, 7]
    [4, 6, 7]
    [4, 7]
    [4, 7, 7]
    [4, 7]
    [6, 7]
    [6, 7, 7]
    [6, 7]
    [3, 7]
    [3, 7, 7]
    [3, 7]
    [7, 7]
    
    外层去重 res.stream().distinct().collect(Collectors.toList());

#### 方式2：添加直接去重逻辑 ####

public static List<List<Integer>> findSubsequences(int[] nums) {
        
        if (nums == null || nums.length < 2) {
        
            return new ArrayList<>();
        }
        
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();
        dfs(0, nums, queue, res);
        
        return res;
    }
    /**
     * 递归枚举子序列的通用模板
     */
    public static void dfs(int start, int[] arr, Deque<Integer> queue, List<List<Integer>> 
        if (queue.size() >= 2) {
         // 满足条件就快照一下
            res.add(new ArrayList<>(queue));
            System.out.println(new ArrayList<>(queue));
        }
        
        // 用hashset去重
        Set<Integer> visited = new HashSet<>();
        for (int i = start; i < arr.length; i++) {
        
            if (!queue.isEmpty() && queue.getLast() > arr[i]) {
        
                continue; // 不满足递增子序列(两整数相等视作递增)条件时，继续处理下一下
            }
            
            if (visited.contains(arr[i])) {
        
                continue;
            }
            
            visited.add(arr[i]);
            
            queue.addLast(arr[i]);
            dfs(i + 1, arr, queue, res);
            queue.removeLast();
        }
    }
    
    输入源：4 6 3 7 7
    
    [4, 6]
    [4, 6, 7]
    [4, 6, 7, 7]
    [4, 7]
    [4, 7, 7]
    [6, 7]
    [6, 7, 7]
    [3, 7]
    [3, 7, 7]
    [7, 7]