LeetCode DayBackTracking Teil 2

39. Kombinationssumme

Gibt eine Liste aller eindeutigen Kombinationen von Kandidaten zurück, bei denen sich die ausgewählten Zahlen zum Ziel summieren, wenn ein Array aus verschiedenen Ganzzahlkandidaten und ein ganzzahliges Zielziel gegeben sind. Sie können die Kombinationen in beliebiger Reihenfolge zurückgeben.

Die gleiche Anzahl von Kandidaten kann unbegrenzt oft ausgewählt werden. Zwei Kombinationen sind eindeutig, wenn das
Häufigkeit
von mindestens einer der gewählten Zahlen unterschiedlich ist.

Die Testfälle werden so generiert, dass die Anzahl der eindeutigen Kombinationen, die sich zum Ziel summieren, weniger als 150 Kombinationen für die gegebene Eingabe beträgt.

Beispiel 1:

Eingabe: Kandidaten = [2,3,6,7], Ziel = 7
Ausgabe: [[2,2,3],[7]]
Erklärung:
2 und 3 sind Kandidaten und 2 + 2 + 3 = 7. Beachten Sie, dass 2 mehrfach verwendet werden kann.
7 ist ein Kandidat und 7 = 7.
Dies sind die einzigen beiden Kombinationen.
Beispiel 2:

Eingabe: Kandidaten = [2,3,5], Ziel = 8
Ausgabe: [[2,2,2,2],[2,3,3],[3,5]]
Beispiel 3:

Eingabe: Kandidaten = [2], Ziel = 1
Ausgabe: []

Einschränkungen:

1 <= Candidates.length <= 30
2 <= Kandidaten[i] <= 40
Alle Elemente von Kandidaten sind unterschiedlich.
1 <= Ziel <= 40

Originalseite

Der Unterschied zwischen dieser Frage und den gestern gelösten Fragen ist nicht ganz groß.


Das BackTracking eignet sich immer noch gut für die Suche nach Tiefenmöglichkeiten und die Verwendung einer Schleife zur Breitensteuerung.


Der Teil, der Aufmerksamkeit erfordert, ist, dass wir hier dieselben Elemente hinzufügen und dann die gesamte Kombination einzigartig halten können.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> combs = new LinkedList<>();
        backTracking(list, combs, candidates, target, 0, 0);
        return list;
    }

    public void backTracking(List<List<Integer>>list, List<Integer> combs, int[] candidates, int target, int sum, int start){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=start; i<candidates.length; i++){
            combs.add(candidates[i]);
            sum += candidates[i];
            backTracking(list, combs, candidates, target, sum, i);
            combs.remove(combs.size()-1);
            sum -= candidates[i];
        }




</p>
<h2>
  
  
  40. Kombinationssumme II
</h2>

<h3>
  
  
  Zeitlimit überschritten
</h3>



<pre class="brush:php;toolbar:false">    Set<List<Integer>> set = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0);

        return new ArrayList<>(set);
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum){
        if(sum > target){
            return;
        }
        if(sum == target){
            set.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum);
            sum -= candidates[i];
            combs.remove(combs.size()-1);

        }
    }

Weil es einige Elemente gibt, die bereits zuvor verwendet wurden, z. [1,1,1,2,3] 112 wurde in der ersten Rekursion verwendet, aber die Schleife durchläuft alle Elemente, die bei 1 bis 3 beginnen, und es gibt drei „1“, wenn es also um die zweite „1“ geht, Es wird auch die Kombination 112 gefunden, die in früheren Rekursionsschritten gefunden wurde, daher sollten wir diese redundanten Schritte reduzieren (ähnlicherweise kann dies auch beim Rekursionsdurchlauf und beim Rekursionsdurchlauf passieren.

Beheben Sie das Problem

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0, false);

        return list;
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum, boolean horizon){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            if(i!=0 && candidates[i] == candidates[i-1] && horizon){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum, false);
            sum -= candidates[i];
            combs.remove(combs.size()-1);
            horizon = true;
        }
    }

131. Palindrom-Partitionierung

Partitionieren Sie bei einer gegebenen Zeichenfolge s so, dass jedes
Teilzeichenfolge
der Partition ist ein
Palindrom
. Gibt alle möglichen Palindrom-Partitionierungen von s zurück.

Beispiel 1:

Eingabe: s = "aab"
Ausgabe: [["a", "a", "b"],["aa", "b"]]
Beispiel 2:

Eingabe: s = "a"
Ausgabe: [["a"]]

Einschränkungen:

1 <= s.length <= 16
s enthält nur englische Kleinbuchstaben.
Originalseite

    List> list = new ArrayList<>();
    public List> partition(String s) {
        List combs = new ArrayList<>();

        backTracking(combs, new StringBuilder(s), 0);
        return list;
    }

    public void backTracking(List combs, StringBuilder str, int start){
        if(start == str.length()){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=1; i+start <= str.length(); i++){

            String cur = str.substring(start, start+i);

            if(!isParlindrome(cur)){
                continue; 
            } 

            combs.add(cur);
            backTracking(combs, str, start+i);
            combs.remove(combs.size()-1);
        }

    }

    public boolean isParlindrome(String s){
        int left = 0;
        int right = s.length()-1;

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