Journal quotidien des questions (6)

Première question: Un doigt d'épée. Offer II 079. Tous les sous - ensembles

LeetCode: Un doigt d'épée. Offer II 079. Tous les sous - ensembles
Description:
Donner un tableau entier nums ,Éléments du tableau Ils sont différents les uns des autres .Renvoie tous les sous - ensembles possibles du tableau（Ensemble de puissance）.
Ensemble de solutions Je ne peux pas Contient un sous - ensemble en double.Vous pouvez appuyer sur N'importe quel ordre Renvoie un ensemble de solutions.

Comment résoudre le problème:

Un problème classique de rétrospection ;
Attention à la coupe ici .

• Couper1: Le même élément ne peut pas être réutilisé
• Couper2: Ne peut pas contenir de sous - ensembles dupliqués

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
    
        dfs(nums,0);
        return result;
    }
    public void dfs(int[] nums, int start) {
    
        result.add(new ArrayList<>(ret));
        // Couper1: i=start  Est de s'assurer qu'il n'y a pas de sous - ensemble dupliqué 
        for(int i = start; i < nums.length; i++) {
    
            ret.add(nums[i]);
            // Couper2: Ici. i+1  Assurez - vous de ne pas réutiliser le même élément 
            dfs(nums,i+1);
            ret.remove(ret.size()-1);
        }
    }
}

Deuxième question: Un doigt d'épée. Offer II 080. Contient: k Une combinaison d'éléments

LeetCode: Un doigt d'épée. Offer II 080. Contient: k Une combinaison d'éléments
Description:
Donner deux entiers n Et k,Retour 1 ... n Tous les k Une combinaison de nombres.

Comment résoudre le problème:

Rétrospective classique
Attention à la coupe.

• Couper1: Les éléments dupliqués ne peuvent pas être utilisés
• Couper2: Il ne peut pas y avoir de sous - ensembles dupliqués

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
    
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
    
            arr[i] = i+1;
        }
        dfs(arr,0,k);
        return result;
    }
    public void dfs(int[] arr,int start, int k) {
    
        if(ret.size() == k) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        // Couper1: Jeani=start  Assurez - vous qu'il n'y a pas de sous - ensembles dupliqués 
        for(int i = start; i < arr.length; i++) {
    
            ret.add(arr[i]);
            // Couper2: Entrée i+1  Assurez - vous que les éléments dupliqués ne sont pas utilisés 
            dfs(arr,i+1,k);
            ret.remove(ret.size() - 1);
        }
    }
}

Question n° 3: Un doigt d'épée. Offer II 081. Autoriser la sélection répétée des combinaisons d'éléments

LeetCode: Un doigt d'épée. Offer II 081. Autoriser la sélection répétée des combinaisons d'éléments
Description:
Compte tenu d'unAucun élément en doubleUn tableau entier positif de candidates Et un entier positif target ,Trouver candidates Tous les nombres peuvent être additionnés au nombre cible target La seule combinaison de.

candidates Nombre en Peut être sélectionné à plusieurs reprises sans limitation .Si au moins un nombre sélectionné est différent,Alors les deux combinaisons sont différentes.

Pour une entrée donnée,Garantie et target Le nombre de combinaisons uniques est inférieur à 150 - Oui..

Comment résoudre le problème:

Rétrospective classique
Attention à la coupe.

• Couper1: Ne pas répéter la situation

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        Arrays.sort(candidates);
        dfs(candidates,0,target);
        return result;
    }
    public void dfs(int[] candidates, int start, int target) {
    
        if (target == 0) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        // Couper1: i = start  Assurez - vous que le Sous - ensemble ne se répète pas 
        for(int i = start; i < candidates.length; i++) {
    
            if(candidates[i] <= target){
    
                ret.add(candidates[i]);
                // Entréei  L'élément courant est réutilisé 
                dfs(candidates,i,target-candidates[i]);
                ret.remove(ret.size()-1);
            }
        }
    }
}

Question n° 4: Un doigt d'épée. Offer II 082. Une combinaison contenant une collection d'éléments répétitifs

LeetCode: Un doigt d'épée. Offer II 082. Une combinaison contenant une collection d'éléments répétitifs
Description:
Compte tenu d'un tableau entier qui peut avoir des nombres dupliqués candidates Et un nombre cible target ,Trouver candidates Tout ce qui rend les nombres et target Combinaison de.

candidates Chaque chiffre dans chaque combinaison Ne peut être utilisé qu'une seule fois,Ensemble de solutionsNe peut pas contenir de duplicatasCombinaison de.

Comment résoudre le problème:

Rétrospective classique :
Attention à la coupe :

• Couper1: Les combinaisons répétées ne peuvent pas se produire
• Couper2: L'élément ne peut pas être réutilisé
• Couper3: Le tableau contient des éléments dupliqués

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        Arrays.sort(candidates);
        boolean[] tmp = new boolean[candidates.length];
        dfs(candidates,0,target,tmp);
        return result;
    }
    public void dfs(int[] candidates, int start, int target,boolean[] tmp) {
    
        if(target == 0) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        // Couper1: i=start Assurez - vous qu'il n'y a pas de combinaisons répétées 
        for (int i = start; i < candidates.length; i++) {
    
         	// Couper3: UtiliserbooleanUn tableau pour marquer, Assurez - vous que les éléments dupliqués se produisent 
            if(i>0 && candidates[i] == candidates[i-1] && !tmp[i-1]){
    
                continue;
            }
            if(candidates[i] <= target) {
    
                ret.add(candidates[i]);
                tmp[i] = true;
                // Couper2: i+1 Pour s'assurer qu'il n'y a pas d'utilisation de soi ,  Mais vous pouvez utiliser quelqu'un d'autre 
                dfs(candidates,i+1,target-candidates[i],tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
            
        }
    }
}

Question 5: Un doigt d'épée. Offer II 083. Il n'y a pas de répétition de l'arrangement complet de la collection d'éléments

LeetCode: Un doigt d'épée. Offer II 083. Il n'y a pas de répétition de l'arrangement complet de la collection d'éléments
Description:
Compte tenu d'un tableau entier sans duplicata nums ,Retour à Tous les arrangements possibles .C'est bon. Dans n'importe quel ordre Retour à la réponse.

Comment résoudre le problème:

Rétrospective classique
Attention à la coupe.

• Couper1: Impossible de réutiliser l'élément courant

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
    
        boolean[] tmp = new boolean[nums.length];
        dfs(nums,tmp);
        return result;
    }
    public void dfs(int[] nums, boolean[] tmp) {
    
        if (ret.size() == nums.length) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
    
            // Couper1: UtiliserbooleanUn tableau pour marquer,  Si l'indice actuel est falseÇa n'a pas marché
            if (!tmp[i]) {
    
                tmp[i] = true;
                ret.add(nums[i]);
                dfs(nums,tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
        }
    }
}

Question 6: Un doigt d'épée. Offer II 084. Disposition complète avec une collection d'éléments dupliqués

LeetCode: Un doigt d'épée. Offer II 084. Disposition complète avec une collection d'éléments dupliqués
Description:
Compte tenu d'un ensemble entier qui peut contenir des nombres dupliqués nums ,Dans n'importe quel ordre Renvoie tout ce qui ne se répète pas Tout l'Arrangement de.

Comment résoudre le problème:

Rétrospective classique
Attention à la coupe.

• Couper1: Impossible de réutiliser l'élément courant
• Couper2: Notez les éléments dupliqués dans le tableau

Mise en œuvre du Code:

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> ret = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        Arrays.sort(nums);
        boolean[] tmp = new boolean[nums.length];
        dfs(nums,tmp);
        return result;
    }
    public void dfs(int[] nums, boolean[] tmp) {
    
        if (ret.size() == nums.length) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
    
       		// Couper2: En commençant par le deuxième élément,  Si l'élément courant est le même que l'élément précédent , Et l'élément précédent n'est pas utilisé , Sauter directement
            if(i > 0 && nums[i] == nums[i-1] && !tmp[i-1]){
    
                continue;
            }
            // Couper1: UtiliserbooleanUn tableau pour marquer,  Si l'indice actuel est falseÇa n'a pas marché
            if(!tmp[i]){
    
                tmp[i] = true;
                ret.add(nums[i]);
                dfs(nums,tmp);
                tmp[i] = false;
                ret.remove(ret.size()-1);
            }
        }
    }
}

Question 7: Un doigt d'épée. Offer II 085. Générer des parenthèses correspondantes

LeetCode: Un doigt d'épée. Offer II 085. Générer des parenthèses correspondantes
Description:
Entier positif n Représente le logarithme des parenthèses générées,Veuillez concevoir une fonction,Utilisé pour générer toutes les possibilités et Efficace Combinaison de parenthèses.

Comment résoudre le problème:

Ici.left Indique le nombre d'inclusions à gauche , right Indique le nombre de parenthèses de fermeture
Couper1: rightOuleft<0
Couper2: right<left ( Assurez - vous d'utiliser d'abord la parenthèse gauche , La situation illégale a été exclue )

Mise en œuvre du Code:

class Solution {
    
    public List<String> generateParenthesis(int n) {
    
        List<String> result = new ArrayList<>();
        backstrack(result,"",n,n);
        return result;
    }
    public void backstrack(List<String> result,String str,int left, int right) {
    
    	// Couper1
        if(left < 0 || right <0) return;
        // Couper2
        if(left > right) return;
        if(left == 0 && right == 0 ) {
    
            result.add(str);
            return;
        }
        backstrack(result,str+"(",left-1,right);
        backstrack(result,str+")",left,right-1);
    }
}

Question 8: Un doigt d'épée. Offer II 086. Diviser la Sous - chaîne de palindrome

LeetCode: Un doigt d'épée. Offer II 086. Diviser la Sous - chaîne de palindrome

Description:
Donner une chaîne s ,S'il vous plaît. s Diviser en sous - chaînes,Faire en sorte que chaque substrat soit Une chaîne de palindromes ,Retour s Tous les schémas de partition possibles.

Une chaîne de palindromes C'est la même chaîne que la lecture directe et la lecture inversée.

Comment résoudre le problème

Rétrospective classique
Attention à la coupe.
Couper1: Impossible de réutiliser l'élément courant
Couper2: Les combinaisons répétées ne peuvent pas se produire
Couper3: Ça doit être un palindrome

Mise en œuvre du Code:

class Solution {
    
    List<List<String>> result = new ArrayList<>();
    List<String> ret = new ArrayList<>();
    public String[][] partition(String s) {
    
        bfs(s,0);
        String[][] str = new String[result.size()][];
        int i = 0;
        for(List<String> list : result){
    
            str[i++] = list.toArray(new String[list.size()]);
        }
        return str;
    }
    public void dfs(String s,int start) {
    
        if(s.length() == start) {
    
            result.add(new ArrayList<>(ret));
            return;
        }
        // Couper1:  Les combinaisons répétées ne peuvent pas se produire 
        for(int i = start; i < s.length(); i++) {
    
       		// Couper3:  Ça doit être un palindrome 
            if(isHui(s,start,i)) {
    
            	// Couper2:  Le même élément ne peut pas être réutilisé 
                ret.add(s.substring(start,i+1));
                bfs(s,i+1);
                ret.remove(ret.size()-1);
            }
        }
    }
    public boolean isHui(String s,int left, int right) {
    
        while(left<right) {
    
            if(s.charAt(left) == s.charAt(right)){
    
                left++;
                right--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}