算法题补充

前言

我需要补充一些烧鸡100和剑指offer没有的题目

回溯

47. 全排列 II - 力扣（LeetCode）

主要是掌握去重的套路

  1. 排序

  2. visit[]

  3. if(i>0&&nums[i]==nums[i-1]&&!visit[i-1])

    class Solution {
        List<Integer>path=new ArrayList<>();
        ArrayList<List<Integer>>res=new ArrayList<>();//设为全局变量就不用传递参数了
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            boolean[]used=new boolean[nums.length];
            back(nums,used);
            return res;
        }

        public void back(int[]nums,boolean[]used)
        {
            if(path.size()==nums.length)
            {
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i=0;i<nums.length;i++)
            {
                if(used[i]==true)
                {
                    continue;
                }
                if(i>0&&nums[i]==nums[i-1]&&!used[i-1])
                {
                    continue;
                }
                path.add(nums[i]);
                used[i]=true;
                back(nums,used);
                path.remove(path.size()-1);
                used[i]=false;
            }
        }
    }

具体为什么，建议看傻逼卡尔的讲解

← Posts