代码随想录算法训练营第二十五天-491递增子序列、46全排列、47全排列 II

前言
状态：491 超时。46AC。47 不是很对，要看解析，主要是去重那一步。
更新

1 2	24-06-11 初始记录 24-06-12 完成

初步题解

491 递增子序列

题目链接：(https://leetcode.cn/problems/non-decreasing-subsequences)

超时了，主要是去重那一步应该。

public static List<List<Integer>> findSubsequences(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    findSubsequencesDFS(0 , nums, resultOne, result);  
    return result;  
}  
  
private static void findSubsequencesDFS(int startIndex, int[] nums, List<Integer> resultOne, List<List<Integer>> result) {  
    // 先这样判断是否重复  
    if (resultOne.size() >= 2 && !result.contains(resultOne)) {  
        result.add(new ArrayList<>(resultOne));  
    }  
  
    for (int i = startIndex; i < nums.length; i++) {  
        if (resultOne.size() != 0 && resultOne.get(resultOne.size() - 1) > nums[i]) {  
            continue;  
        }  
        resultOne.add(nums[i]);   
        findSubsequencesDFS(i + 1, nums, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

46 全排列

题目链接：(https://leetcode.cn/problems/permutations/description/)

// 排列每个变量都要统计，所以不需要startIndex
public static List<List<Integer>> permute(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    if (nums == null || nums.length == 0) {  
        return result;  
    }  
  
    permuteDFS(nums, resultOne, result);  
    return result;  
}  
  
private static void permuteDFS(int[] nums, List<Integer> resultOne, List<List<Integer>> result) {  
    if (resultOne.size() == nums.length) {  
        result.add(new ArrayList<>(resultOne));  
        return;  
    }  
  
    for (int i = 0; i < nums.length; i++) {  
        if (resultOne.contains(nums[i])) {  
            continue;  
        }  
        resultOne.add(nums[i]);  
        permuteDFS(nums, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

47 全排列 II

题目链接：(leetcode.cn/problems/permutations-ii/)

/**  
 * 和上一题唯一的区别就是数组元素重复。  
 * 所以不能用数组直接统计，得用index记录这个是否被记过  
 * 还有点缺陷。重复元素会按不同下标被重复计入.  
 * 和之前一样，单层元素不能重复。  
 * @param nums nums  
 * @return 结果  
 */  
public static List<List<Integer>> permuteUnique(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
  
    if (nums == null || nums.length == 0) {  
        return result;  
    }  
  
    Arrays.sort(nums);  
    permuteUniqueDFS(nums, new ArrayList<>(), resultOne, result);  
    return result;  
}  
  
private static void permuteUniqueDFS(int[] nums, List<Integer> resultIndex, List<Integer> resultOne, List<List<Integer>> result) {  
    if (resultOne.size() == nums.length) {  
        result.add(new ArrayList<>(resultOne));  
        return;  
    }  
  
    // 判断这层有没有使用过这个数字，和LE491一样  
    HashSet<Integer> set = new HashSet<>();  
    // set记录下标  
    for (int i = 0; i < nums.length; i++) {  
        if (resultIndex.contains(i)) {  
            continue;  
        }  
        if (set.contains(nums[i])) {  
            continue;  
        }  
        resultIndex.add(i);  
        resultOne.add(nums[i]);  
        set.add(nums[i]);  
        permuteUniqueDFS(nums, resultIndex, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
        resultIndex.remove(resultIndex.size() - 1);  
    }  
}

看题解

491 递增子序列

(https://programmercarl.com/0491.递增子序列.html)

视频讲解：(https://www.bilibili.com/video/BV1EG4y1h78v)

加了剪枝操作的优化。

public static List<List<Integer>> findSubsequences(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    findSubsequencesDFS(0 , nums, resultOne, result);  
    return result;  
}  
  
private static void findSubsequencesDFS(int startIndex, int[] nums, List<Integer> resultOne, List<List<Integer>> result) {   
    if (resultOne.size() >= 2) {  
        result.add(new ArrayList<>(resultOne));  
    }  
  
    HashMap<Integer,Integer> map = new HashMap<>();  
    for (int i = startIndex; i < nums.length; i++) {  
        if (resultOne.size() != 0 && resultOne.get(resultOne.size() - 1) > nums[i]) {  
            continue;  
        }  
        // 判断这层是否使用  
        if (map.getOrDefault(nums[i], 0) >= 1) {  
            continue;  
        }  
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);  
        resultOne.add(nums[i]);  
        findSubsequencesDFS(i + 1, nums, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

46 全排列

(https://programmercarl.com/0046.全排列.html)

视频讲解：(https://www.bilibili.com/video/BV19v4y1S79W)

47 全排列 II

(https://programmercarl.com/0047.全排列II.html)

视频讲解：(https://www.bilibili.com/video/BV1R84y1i7Tm)

public static List<List<Integer>> permuteUnique(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
  
    if (nums == null || nums.length == 0) {  
        return result;  
    }  
  
    Arrays.sort(nums);  
    permuteUniqueDFS(nums, new boolean[]{}, resultOne, result);  
    return result;  
}  
  
/**  
 * 用数组标记因为这个树更像一个矩阵  
 * 数组可以标记nums又可以标记层数  
 */  
private static void permuteUniqueDFS(int[] nums, boolean[] used, List<Integer> resultOne, List<List<Integer>> result) {  
    if (resultOne.size() == nums.length) {  
        result.add(new ArrayList<>(resultOne));  
        return;  
    }  
  
    // set记录下标  
    for (int i = 0; i < nums.length; i++) {  
        // 记录了index值，即这index被使用了（这里可以理解）  
        if (used[i]) {  
            continue;  
        }  
  
        // 如果这个数值和前面的数值相同  
        // 首先一定要排序，这样nums数组中的前面一个节点，就一定是被用过了  
        // 然后现在到这个节点，前面一个节点的状态是false(这里横向看)，说明已经回溯了。节点已经被添加，跳过这层  
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {  
            continue;  
        }  
        // 这层是否使用过  
        used[i] = true;  
        resultOne.add(nums[i]);  
        permuteUniqueDFS(nums, used, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
        used[i] = false;  
    }  
}