LeetCode DayBackTracking Bahagian 1

77. Gabungan

Diberi dua integer n dan k, kembalikan semua kemungkinan kombinasi nombor k yang dipilih daripada julat [1, n].

Anda boleh mengembalikan jawapan dalam sebarang susunan.

Contoh 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Penjelasan: Terdapat 4 pilih 2 = 6 jumlah kombinasi.
Ambil perhatian bahawa gabungan tidak tertib, iaitu, [1,2] dan [2,1] dianggap sebagai gabungan yang sama.
Contoh 2:

Input: n = 1, k = 1
Output: [[1]]
Penjelasan: Terdapat 1 pilih 1 = 1 jumlah kombinasi.

Kekangan:

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

Kod yang salah

    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>Tetapi ia menyebabkan Ralat Melebihi Had Memori dalam LeetCode</p>

<p>Terdapat beberapa ralat di sini. </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, keadaan gelung adalah salah kita harus menggunakan i tetapi kod di atas menggunakan asas sebagai syarat penilaian akhir.<br>
2, ambang yang betul boleh menjadi n dan jika i<n ia akan terlepas kemungkinan apabila n ialah unsur gabungan potensi. </p>
<h2>
  
  
  Kod Baik
</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();
        }
    }

Terdapat beberapa perbezaan di sini yang kita boleh bergantung secara langsung pada saiz senarai laluan global tetapi di sini saiz nombor itu adalah jawapan yang betul!!!
Sebelum saiz bukan jawapan yang betul kerana kami belum menambah elemen terakhir pada senarai laluan.

Nampaknya penggunaan pembolehubah global boleh menyebabkan penurunan prestasi?

Ini adalah kaedah yang lebih umum tetapi soalan bertanya bahawa kita hanya menggunakan nombor yang <= 9 dan >= 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<=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);
        }
    }

Nampaknya beberapa pengiraan berlebihan digunakan untuk jumlah

    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. Huruf Gabungan Nombor Telefon

Memandangkan rentetan yang mengandungi digit daripada 2-9 termasuk, kembalikan semua kemungkinan kombinasi huruf yang boleh diwakili oleh nombor itu. Kembalikan jawapan dalam sebarang susunan.

Pemetaan digit kepada huruf (sama seperti pada butang telefon) diberikan di bawah. Ambil perhatian bahawa 1 tidak memetakan kepada mana-mana huruf.

Contoh 1:

Input: digit = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Contoh 2:

Input: digit = ""
Output: []
Contoh 3:

Input: digit = "2"
Output: ["a","b","c"]

Kekangan:

0 <= digit.panjang <= 4
digit[i] ialah digit dalam julat ['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>

Atas ialah kandungan terperinci LeetCode DayBackTracking Bahagian 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!