LeetCode DayBackTracking パート 4

491. 非減少サブシーケンス

整数配列 nums を指定すると、少なくとも 2 つの要素を持つ、指定された配列のさまざまな非減少サブシーケンスをすべて返します。回答はどの順序で返しても構いません。

例 1:

入力: nums = [4,6,7,7]
出力: [[4,6]、[4,6,7]、[4,6,7,7]、[4,7]、[4,7,7]、[6,7]、[6, 7,7],[7,7]]
例 2:

入力: nums = [4,4,3,2,1]
出力: [[4,4]]

制約:

1 -100 オリジナルページ

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> seq = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        backTracking(list, seq, nums, 0, set);

        return list;

    }
    public void backTracking(List<List<Integer>>list, List<Integer> seq, int[] nums, int start, Set<Integer> set){
        if(start == nums.length){
            return;
        }

        for(int i=start; i<nums.length; i++){
            // pruming the same elements
            if(i!=start && set.contains(nums[i])){
                continue;
            }

            if(seq.size() >= 1 && (nums[i] < seq.get(seq.size()-1))){
                continue;
            }
            // the first element
            set.add(nums[i]);

            seq.add(nums[i]);

            // evaluate non-decreasing
            if(seq.size() > 1 && nums[i]>= seq.get(seq.size()-2)){
                list.add(new ArrayList<>(seq));  
            }

            if(seq.size() == 1 || nums[i]>= seq.get(seq.size()-1)){
                backTracking(list,seq, nums, i+1, new HashSet<>());
            }
                // backTracking
            seq.remove(seq.size()-1);
        }
    }

46. 順列

個別の整数の配列 num を指定すると、考えられるすべての順列を返します。回答は任意の順序で返すことができます。

例 1:

入力: nums = [1,2,3]
出力: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
例 2:

入力: nums = [0,1]
出力: [[0,1],[1,0]]
例 3:

入力: nums = [1]
出力: [[1]]

制約:

1 -10 num の整数はすべて一意です。

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> permutation = new LinkedList<>();

        Integer[] numsI = Arrays.stream(nums).boxed().toArray(Integer[]::new);

        List<Integer> numList = new ArrayList(Arrays.asList(numsI));

        backTracking(list, permutation, numList);
        return list;

    }

    public void backTracking(List<List<Integer>> list, List<Integer> permutation, List<Integer> nums){
        if(nums.size()==0){
            list.add(new ArrayList<>(permutation));
            return;
        }

        for(int i=0; i<nums.size(); i++){
            permutation.add(nums.get(i));

            List<Integer> workNums = new ArrayList<>(nums);
            workNums.remove(Integer.valueOf(nums.get(i)));
            backTracking(list, permutation, workNums);

            permutation.remove(permutation.size()-1);

        }
    }

47. 順列 II

重複を含む可能性のある数値のコレクション nums を指定すると、考えられるすべての一意の順列を任意の順序で返します。

例 1:

入力: nums = [1,1,2]
出力:
[[1,1,2]、
[1,2,1]、
[2,1,1]]
例 2:

入力: nums = [1,2,3]
出力: [[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1] ]

制約:

1 -10 オリジナルページ

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> permutation = new LinkedList<>();
        int[] flags = new int[nums.length];

        backTracking(permutation, nums, flags);

        return list;        
    }

    public void  backTracking(List<Integer> permutation, int[] nums, int[] flags){
        if(permutation.size() == nums.length){
            list.add(new ArrayList<>(permutation));
            return;
        }

        Set<Integer> set = new HashSet<>();
        for(int i=0; i<nums.length; i++){
            // flag work for recursion, set work for loop 
            if(flags[i] != 0 || set.contains(nums[i])){
                continue;
            }

            int num = nums[i];
            permutation.add(num);
            set.add(num);
            flags[i] = 1;
            backTracking(permutation, nums, flags);
            //recover to flag;
            flags[i] = 0;
            permutation.remove(permutation.size()-1);

        }

    }

以上がLeetCode DayBackTracking パート 4の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。