LeetCode DayBackTracking Teil 1

77. Kombinationen

Gegeben zwei ganze Zahlen n und k, alle möglichen Kombinationen von k Zahlen zurückgeben, die aus dem Bereich [1, n] ausgewählt wurden.

Sie können die Antwort in beliebiger Reihenfolge zurückgeben.

Beispiel 1:

Eingabe: n = 4, k = 2
Ausgabe: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Erläuterung: Es gibt insgesamt 4 Kombinationen von 2 = 6.
Beachten Sie, dass Kombinationen ungeordnet sind, d. h. [1,2] und [2,1] gelten als dieselbe Kombination.
Beispiel 2:

Eingabe: n = 1, k = 1
Ausgabe: [[1]]
Erläuterung: Es gibt 1 Auswahl 1 = 1 Gesamtkombination.

Einschränkungen:

1 <= n <= 20
1 <= k <= n

Falscher Code

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> nums = new ArrayList<>();

        backTracking(list,1,1,n,k,nums);

        return list;
    }

    public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
    {
        if(size>k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; base<n; i++ ){
            nums.add(i);
            backTracking(list,i+1,size+1,n,k,nums);
            nums.remove(nums.size()-1);
        }
    }



</p>
<p>Aber es verursacht den Fehler „Speicherlimit überschritten“ in LeetCode</p>

<p>Hier gibt es einige Fehler. </p>

<p><img src="https://img.php.cn/upload/article/000/000/000/172112315134776.png" alt="Image description" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<p>1, die Schleifenbedingung ist falsch, wir sollten i verwenden, aber der obige Code verwendet base als Endauswertungsbedingung.<br>
2, der richtige Schwellenwert kann n sein, und wenn i<n, entfällt die Möglichkeit, dass n ein Element der möglichen Kombination ist. </p>
<h2>
  
  
  Feiner Code
</h2>


<pre class="brush:php;toolbar:false">    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> nums = new ArrayList<>();

        backTracking(list,1,1,n,k,nums);

        return list;
    }

    public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
    {
        if(size>k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; i<=n; i++ ){
            nums.add(i);
            backTracking(list,i+1,size+1,n,k,nums);
            nums.remove(nums.size()-1);
        }
    }

    List<List<Integer>> list = new LinkedList<>();
    List<Integer> nums = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(1,n,k);
        return list;
    }

    public void backTracking(int base, int n, int k)
    {
        if(nums.size()==k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; i<=n; i++ ){
            nums.add(i);
            backTracking(i+1,n,k);
            nums.removeLast();
        }
    }

Hier gibt es einige Unterschiede, die wir direkt von der Größe der globalen Pfadliste abhängen können, aber hier ist die Größe der Nummern die richtige Antwort!!!
Vorher ist die Größe nicht die richtige Antwort, da wir das letzte Element nicht zur Pfadliste hinzugefügt haben.

Es scheint, als ob die Einführung globaler Variablen zu einer Leistungseinbuße führen könnte?

Dies ist eine allgemeinere Methode, aber die Frage verlangt, dass wir nur Zahlen verwenden, die <= 9 und >= 1 sind

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n){
        if(path.size() == k){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=n; i++){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n );
            path.remove(path.size()-1);
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n){
        if(path.size() == k){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=9; i++){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n );
            path.remove(path.size()-1);
        }
    }

Es scheint, dass für die Summe einige redundante Berechnungen verwendet werden

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n, 0);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n, int sum){
        if(path.size() == k){
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=9; i++){
            sum += i;
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n, sum);
            path.remove(path.size()-1);
            sum -= i;
        }
    }

17. Buchstabenkombinationen einer Telefonnummer

Geben Sie bei einer gegebenen Zeichenfolge mit Ziffern von 2 bis einschließlich 9 alle möglichen Buchstabenkombinationen zurück, die die Zahl darstellen könnte. Geben Sie die Antwort in beliebiger Reihenfolge zurück.

Eine Zuordnung von Ziffern zu Buchstaben (genau wie auf den Telefontasten) finden Sie unten. Beachten Sie, dass 1 keinem Buchstaben zugeordnet werden kann.

Beispiel 1:

Eingabe: Ziffern = „23“
Ausgabe: [„ad“, „ae“, „af“, „bd“, „be“, „bf“, „cd“, „ce“, „cf“]
Beispiel 2:

Eingabe: Ziffern = ""
Ausgabe: []
Beispiel 3:

Eingabe: Ziffern = „2“
Ausgabe: ["a", "b", "c"]

Einschränkungen:

0 <= Ziffern.Länge <= 4
digits[i] ist eine Ziffer im Bereich ['2', '9'].

    public List<String> letterCombinations(String digits) {
        List<String> list = new LinkedList<>();
        if(digits.length() == 0){
            return list;
        }
        String[] arr = {
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        backTracking(list, new StringBuilder(), 0, digits, arr);
        return list;

    }

    public void backTracking(List<String> list, StringBuilder s, int start, String digits, String[] arr){
        if(start == digits.length()){
            list.add(s.toString());
            return;
        }

        int num = digits.charAt(start)-'0';
        String button = arr[num];
        for(int i=0; i<button.length(); i++){
            s.append(button.charAt(i));
            backTracking(list, s, start+1, digits, arr);
            s.setLength(s.length()-1);
        }
    }
</p>

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