LeetCode第47题全排列II

2023年 9月 27日 32.3k 0

继续打卡算法题,今天学习的是LeetCode第47题全排列II,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

哈哈,学习上一题46题全排列,本题只需要先排序,然后加一个去重复逻辑就可以了

比如下方的1223,第三个2和第二个2其实会搜索相同的数据组成排列,因此可以去重。

image.png

本题解题技巧

1、理解排列定义,排列是有顺序的。

2、每次都从第一个元素开始取数,但是一个数字在一个排列中只能出现一次

3、需要先排序,方便去除重复

编码解决

下面代码和组合总和II的代码非常相似。

class Solution {
    public List permuteUnique(int[] nums) {
        //递归 回溯
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtracking(nums, new ArrayList(), 0, 0, used);
        return result;
    }

    private List result = new ArrayList();


    public void backtracking(int[] nums,List path, int startIndex, int sum, boolean[] used) {

        //结束条件
        if( path.size() == nums.length) {
            result.add(new ArrayList(path));
            return;
        }
 
        //递归单层逻辑
        for(int i=startIndex; i 0 && nums[i] == nums[i-1] && used[i-1] == false )|| used[i] == true) {
                   continue;
               }
               path.add(nums[i]);
               sum += nums[i];
               used[i] = true;
               //开始递归 startIndex传i,就是考虑每个数字都可以重复使用的情况
               backtracking(nums, path, 0, sum, used);
               //回溯
               sum = sum - nums[i];
               used[i] = false;
               path.remove(path.size()-1);
        }
    }
}

总结

本题和46题解法几乎一致,排列问题通过回溯法解决,只加了一个减枝(去重复)。
需要注意减枝的情况是在同一层树上进行,同一个排列里不需要去重,也就不需要减枝。

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论