LeetCode DayBackTracking Partie 4

491. Sous-séquences non décroissantes

Étant donné un tableau entier nums, renvoie toutes les différentes sous-séquences non décroissantes possibles du tableau donné avec au moins deux éléments. Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Exemple 1 :

Entrée : nums = [4,6,7,7]
Sortie : [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6, 7,7],[7,7]]
Exemple 2 :

Entrée : nums = [4,4,3,2,1]
Sortie : [[4,4]]

Contraintes :

1 <= nums.length <= 15
-100 <= nums[i] <= 100
Page originale

    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);
        }
    }




</p>
<h2>
  
  
  46. ​​Permutations
</h2>

<p>Étant donné un tableau nums d'entiers distincts, renvoie toutes les permutations possibles. Vous pouvez renvoyer la réponse dans n'importe quel ordre.</p>

<p>Exemple 1 :</p>

<p>Entrée : nums = [1,2,3]<br>
Sortie : [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]<br>
Exemple 2 :</p>

<p>Entrée : nums = [0,1]<br>
Sortie : [[0,1],[1,0]]<br>
Exemple 3 :</p>

<p>Entrée : nums = [1]<br>
Sortie : [[1]]</p>

<p>Contraintes :</p>

<p>1 <= nums.length <= 6<br>
-10 <= nums[i] <= 10<br>
Tous les nombres entiers sont uniques.<br>
</p>

<pre class="brush:php;toolbar:false">    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. Permutations II

Étant donné une collection de nombres, nums, qui peuvent contenir des doublons, renvoie toutes les permutations uniques possibles dans n'importe quel ordre.

Exemple 1 :

Entrée : nums = [1,1,2]
Sortie :
[[1,1,2],
[1,2,1],
[2,1,1]]
Exemple 2 :

Entrée : nums = [1,2,3]
Sortie : [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

Contraintes :

1 <= nums.length <= 8
-10 <= nums[i] <= 10
Page originale

    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);

        }

    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!