LeetCode DayBackTracking Teil 4

491. Nicht abnehmende Teilfolgen

Gibt bei einem gegebenen ganzzahligen Array nums alle verschiedenen möglichen nicht abnehmenden Teilsequenzen des gegebenen Arrays mit mindestens zwei Elementen zurück. Sie können die Antwort in beliebiger Reihenfolge zurückgeben.

Beispiel 1:

Eingabe: nums = [4,6,7,7]
Ausgabe: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6, 7,7],[7,7]]
Beispiel 2:

Eingabe: nums = [4,4,3,2,1]
Ausgabe: [[4,4]]

Einschränkungen:

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

    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. ​​Permutationen
</h2>

<p>Geben Sie bei einer gegebenen Array-Anzahl unterschiedlicher Ganzzahlen alle möglichen Permutationen zurück. Sie können die Antwort in beliebiger Reihenfolge zurückgeben.</p>

<p>Beispiel 1:</p>

<p>Eingabe: nums = [1,2,3]<br>
Ausgabe: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]<br>
Beispiel 2:</p>

<p>Eingabe: nums = [0,1]<br>
Ausgabe: [[0,1],[1,0]]<br>
Beispiel 3:</p>

<p>Eingabe: nums = [1]<br>
Ausgabe: [[1]]</p>

<p>Einschränkungen:</p>

<p>1 <= nums.length <= 6<br>
-10 <= nums[i] <= 10<br>
Alle ganzen Zahlen von Zahlen sind eindeutig.<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. Permutationen II

Gegeben eine Sammlung von Zahlen, nums, die möglicherweise Duplikate enthalten, alle möglichen eindeutigen Permutationen in beliebiger Reihenfolge zurückgeben.

Beispiel 1:

Eingabe: nums = [1,1,2]
Ausgabe:
[[1,1,2],
[1,2,1],
[2,1,1]]
Beispiel 2:

Eingabe: nums = [1,2,3]
Ausgabe: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

Einschränkungen:

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

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

        }

    }

Das obige ist der detaillierte Inhalt vonLeetCode DayBackTracking Teil 4. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!