Journal quotidien des questions (11)

Première question: Un doigt d'épée. Offer II 005. Produit maximal de la longueur du mot

LeetCode: Un doigt d'épée. Offer II 005. Produit maximal de la longueur du mot
Description:
Avec un tableau de chaînes words,S'il vous plaît calculer quand deux chaînes words[i] Et words[j] Sans les mêmes caractères,La valeur maximale du produit de leur longueur.Supposons que la chaîne ne contienne que des minuscules lettres anglaises.S'il n'y a pas une paire de chaînes qui ne contiennent pas les mêmes caractères,Retour 0.

Comment résoudre le problème:

1. La longueur utilisée ici est words.length Tableau de ret Pour enregistrer chaque word Format de chaîne à binaire pour .
   Par exemple: ac ===> 101 ; ad ===> 1001 ; bd ===> 1010
2. Méthode de mise en œuvre de la conversion de chaîne en binaire , C'est traverser chaque caractère , Jean ret[i] |= (1<<words[i].charAt(j)) , Ça veut dire...: Le caractère actuel apparaît , Notez donc le bit correspondant sous forme binaire , Parce que les caractères sont a~z 26- Oui., De droite à gauche, Tant qu'il y en a.1, Cela signifie que l'élément courant apparaît .
3. Traversée, Deux. Avec Opération, Tant que le résultat est égal à 0 , Cela signifie que les deux ne contiennent pas les mêmes éléments . En ce moment, Enregistrer le produit de longueur des deux plus grandes chaînes sans le même élément .

Mise en œuvre du Code:

class Solution {
    
    public int maxProduct(String[] words) {
    
        int[] ret = new int[words.length];
        for(int i = 0; i < words.length; i++) {
    
            for(int j = 0; j < words[i].length(); j++) {
    
            	//  Tant que ce caractère apparaît ,  Changez cette position en 1
                ret[i] = ret[i] | (1 << (words[i].charAt(j) - 'a'));
            }
        }
        int ans = 0;
        for(int i = 0; i < words.length-1; i++) {
    
            for(int j = i + 1; j < words.length; j++) {
    
            	//  Deux paires et l'opération 
                if((ret[i] & ret[j]) == 0) {
    
                	//  Enregistrer le produit maximum 
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

Deuxième question: Un doigt d'épée. Offer II 007. Tableau neutre 0 Trois de

LeetCode: Un doigt d'épée. Offer II 007. Tableau neutre 0 Trois de

Description:
Compte tenu d'un contenant n Un tableau d'entiers nums,Jugement nums Y a - t - il trois éléments dans a ,b ,c ,De faire a + b + c = 0 ？Veuillez trouver tous les 0 Et Pas de répétition Triplet de.

Comment résoudre le problème:

1. Trier d'abord,
2. Prenez d'abord le i - Oui. Élément, Jeanleft = i+1, right = len - 1;
3. Des éléments restants , Prends - le., Tant quenums[left] + nums[right] == target Prends ça.3 Éléments placés dans l'ensemble de résultats , Attention ici, Après l'adhésion, Pour le moment leftValeur de l'indice Et right La valeur de l'indice est effacée , Pour éviter les ajouts répétés
4. Attention à chaque fois que vous prenez un élément , Quand i > 0 Quand. Attention à prendre les mêmes éléments à plusieurs reprises . nums[i] = nums[i-1]

Mise en œuvre du Code:

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
    	// Trier
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2;i++) {
    
            //  Ceci empêche la prise répétée des mêmes éléments 
            if(i != 0 && nums[i] == nums[i-1]) continue;
            // Parce que je l'ai.nums[i]  Pour ajouter 0,  Il faut trouver et  -nums[i]De
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length-1;
            while (left < right) {
    
                if (nums[left] + nums[right] == target) {
    
                    //  Voici le nombre de deux indices qui répondent aux exigences ,  Ajoutez ces trois éléments à l'ensemble 
                    List<Integer> ret = new ArrayList<>();
                    ret.add(nums[i]);
                    ret.add(nums[left]);
                    ret.add(nums[right]);
                    ans.add(ret);
                    //  Ici, pour prévenir leftEtright Répétez sous l'indice pour obtenir la même valeur , Pour enlever le poids
                    int tmp = nums[left];
                    while (left < right && nums[left] == tmp){
    
                        left++;
                    }
                    tmp = nums[right];
                    while (left < right && nums[right] == tmp) {
    
                        right--;
                    }
                }else if (nums[left] + nums[right] < target) {
    
                    left++;
                }else {
    
                    right--;
                }
            }
        }
        return ans;
    }
}

Question n° 3: Un doigt d'épée. Offer II 008. Et supérieur ou égal à target Sous - Tableau le plus court de

LeetCode: Un doigt d'épée. Offer II 008. Et supérieur ou égal à target Sous - Tableau le plus court de

Description:
Compte tenu d'un contenant n Un tableau d'entiers positifs et un entier positif target .

Trouvez dans ce tableau la somme de ≥ target La plus petite longueur de Sous - tableaux consécutifs [numsl, numsl+1, ..., numsr-1, numsr] ,Et renvoie sa longueur.Si aucun sous - Tableau admissible n'existe,Retour 0 .

Comment résoudre le problème:

1. La méthode de la fenêtre coulissante est utilisée ici
2. Jeanleft = 0, right =0, La taille initiale de la fenêtre est 0
3. Avec total Enregistrement nums[right] Valeur de. Juge le courant total Et targetValeur
   • Si actuellement total >= target , Enregistrer le courant Distance de l'indice ( En fin de compte, seul le plus petit ) , À ce stade, total -= nums[left] , left++,
4. Chaque fois que la boucle fait right++
5. La taille de la fenêtre coulissante reste toujours [left,right]
6. Renvoie la distance minimale de l'indice
   

Mise en œuvre du Code:

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int start = 0;
        int end = 0;
        int ans = Integer.MAX_VALUE;
        int total = 0;
        // La taille est [start,end] Fenêtre coulissante pour
        while (end < nums.length) {
    
            total += nums[end];
            while (total >= target) {
    
                ans = Math.min(ans, end-start+1);
                total -= nums[start];
                start++;
            }
            end++;
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

Question n° 4: Un doigt d'épée. Offer II 009. Produit inférieur à K Un sous - tableau de

LeetCode: Un doigt d'épée. Offer II 009. Produit inférieur à K Un sous - tableau de

Description:
Compte tenu d'un tableau entier positif numsEt entier k ,Veuillez trouver le produit dans ce tableau inférieur à k Nombre de sous - tableaux consécutifs de.

Comment résoudre le problème:

1. Utilisez la fenêtre coulissante pour résoudre le problème
2. Chaque fois que le produit courant est enregistré ret *= nums[j], Déterminer si elle est supérieure àk
   • Si c'est plus grand que k, Laissez la limite gauche de la fenêtre se déplacer (i++), Enregistrer l'indice actuel
3. Renvoie tous les temps possibles

Mise en œuvre du Code:

class Solution {
    
    public int numSubarrayProductLessThanK(int[] nums, int k) {
    
        int i = 0;
        int ret = 1;
        int ans = 0;
        // Fenêtre coulissante [i,j]
        for (int j = 0; j < nums.length; j++) {
    
            ret *= nums[j];
            while(i <= j && ret >= k) {
    
                ret /= nums[i];
                i++;
            }
            //  Cette méthode est utilisée ici pour calculer et éviter les doubles comptages 
            ans += j - i + 1;
        }
        return ans;
    }
}

Question 5: Un doigt d'épée. Offer II 010. Et pour k Un sous - tableau de

LeetCode: Un doigt d'épée. Offer II 010. Et pour k Un sous - tableau de

Description:
Compte tenu d'un tableau entier et d'un entier k ,S'il vous plaît trouver le tableau neutre avec k Nombre de sous - tableaux consécutifs de.

Comment résoudre le problème:

1. Utilisez la table de hachage ici , Notez les valeurs actuelles et ret.
2. Jugement Si l'élément existe ret-k, Et ça s'additionne pour k, Enregistrer la présence actuelle valueValeur
3. Attention ici k = nums[i] Situation, Doit être ajouté à l'avance 0Situation.

Mise en œuvre du Code:

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        Map<Integer,Integer> map = new HashMap<>();
        int ans = 0; 
        map.put(0,1);
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
    
            ret += nums[i];
            if (map.containsKey(ret - k)) {
    
                ans += map.get(ret - k);
            }
            map.put(ret,map.getOrDefault(ret,0)+1);
        }
        return ans;
    }
}

Question 6: Un doigt d'épée. Offer II 011. 0 Et 1 Même nombre de sous - tableaux

LeetCode: Un doigt d'épée. Offer II 011. 0 Et 1 Même nombre de sous - tableaux

Description:
Compte tenu d'un tableau binaire nums , Trouvé avec la même quantité de 0 Et 1 Sous - Tableau continu le plus long de,Et renvoie la longueur du sous - Tableau.

Comment résoudre le problème:

1. Tout d'abord, laissez tout dans le tableau être 0L'élément de-1, Il suffit de juger si l'addition est 0, On le saura.0Et1 Est - ce que le nombre de .
2. Si l'élément courant n'existe pas dans la table de hachage , Ajouter à la table de hachage ,value La valeur est l'indice courant
3. Si l'élément courant existe dans la table de hachage , Enregistrer l'écart maximal actuel de l'indice

Mise en œuvre du Code:

class Solution {
    
    public int findMaxLength(int[] nums) {
    
        for(int i = 0; i < nums.length; i++) {
    
            if(nums[i] == 0) nums[i] = -1;
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int ans = 0;
        int target = 0;
        for(int i = 0; i < nums.length; i++) {
    
            target += nums[i];
            if (map.containsKey(target)) {
    
                ans = Math.max(ans,i-map.get(target));
            }else {
    
                map.put(target,i);
            }
        }
        return ans;
    }
}