LeetCode DayBackTracking Partie 1

77. Combinaisons

Étant donné deux entiers n et k, renvoie toutes les combinaisons possibles de k nombres choisis dans la plage [1, n].

Vous pouvez renvoyer la réponse dans n'importe quel ordre.

Exemple 1 :

Entrée : n = 4, k = 2
Sortie : [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explication : Il y a 4 choix 2 = 6 combinaisons totales.
Notez que les combinaisons ne sont pas ordonnées, c'est-à-dire que [1,2] et [2,1] sont considérées comme la même combinaison.
Exemple 2 :

Entrée : n = 1, k = 1
Sortie : [[1]]
Explication : Il y a 1 choix 1 = 1 combinaison totale.

Contraintes :

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

Mauvais 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>Mais cela provoque une erreur de dépassement de limite de mémoire dans LeetCode</p>

<p>Il y a quelques erreurs ici. </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, la condition de boucle est fausse, nous devrions utiliser i mais le code ci-dessus utilise base comme condition d'évaluation de fin.<br>
2, le bon seuil peut être n et si i<n, il manquera la possibilité que lorsque n soit un élément de la combinaison potentielle. </p>
<h2>
  
  
  Code des amendes
</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();
        }
    }

Il y a ici quelques différences dont nous pouvons dépendre directement de la taille de la liste de chemins globale mais ici, la taille des nombres est la bonne réponse !!!
Avant la taille n'est pas la bonne réponse car nous n'avons pas ajouté le dernier élément à la liste des chemins.

Il semble que l'adoption de variables globales puisse entraîner une diminution des performances ?

Il s'agit d'une méthode plus générale mais la question demande d'utiliser uniquement des nombres <= 9 et >= 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);
        }
    }

Il semble que certains calculs redondants soient utilisés pour la somme

    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. Combinaisons de lettres d'un numéro de téléphone

Étant donné une chaîne contenant des chiffres de 2 à 9 inclus, renvoie toutes les combinaisons de lettres possibles que le nombre pourrait représenter. Renvoyez la réponse dans n'importe quel ordre.

Un mappage des chiffres aux lettres (tout comme sur les boutons du téléphone) est donné ci-dessous. Notez que 1 ne correspond à aucune lettre.

Exemple 1 :

Saisie : chiffres = "23"
Sortie : ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Exemple 2 :

Saisie : chiffres = ""
Sortie : []
Exemple 3 :

Saisie : chiffres = "2"
Sortie : ["a","b","c"]

Contraintes :

0 <= chiffres.longueur <= 4
digits[i] est un chiffre compris dans la plage ['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>

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!