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 ["","qw","qe","wq","ww","we","eq","ew","ee"] 变量= 3→ 3*3*3=27 ["q","w","e","qwq","qww","qwe","qeq","qew","qee","w","wqw","wqe","wwq","www","wwe","weq","wew","wee","e","eqw","eqe","ewq","eww","ewe","eeq","eew","eee"] 变量=4 → 3*3*3*3=81 ["","qw","qe","wq","ww","we","eq","ew","ee","qw","qwqw","qwqe","qwwq","qwww","qwwe","qweq","qwew","qwee","qe","qeqw","qeqe","qewq","qeww","qewe","qeeq","qeew","qeee","wq","ww","we","wqwq","wqww","wqwe","wqeq","wqew","wqee","ww","wwqw","wwqe","wwwq","wwww","wwwe","wweq","wwew","wwee","we","weqw","weqe","wewq","weww","wewe","weeq","weew","weee","eq","ew","ee","eqwq","eqww","eqwe","eqeq","eqew","eqee","ew","ewqw","ewqe","ewwq","ewww","ewwe","eweq","ewew","ewee","ee","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 ["","qw","qw","wq","ww","ww","wq","ww","ww"] 变量=3 ["q","w","w","qwq","qww","qww","qwq","qww","qww","w","wqw","wqw","wwq","www","www","wwq","www","www","w","wqw","wqw","wwq","www","www","wwq","www","www"] 变量=4 ["","qw","qw","wq","ww","ww","wq","ww","ww","qw","qwqw","qwqw","qwwq","qwww","qwww","qwwq","qwww","qwww","qw","qwqw","qwqw","qwwq","qwww","qwww","qwwq","qwww","qwww","wq","ww","ww","wqwq","wqww","wqww","wqwq","wqww","wqww","ww","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","ww","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","wq","ww","ww","wqwq","wqww","wqww","wqwq","wqww","wqww","ww","wwqw","wwqw","wwwq","wwww","wwww","wwwq","wwww","wwww","ww","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]