【 catalogue d'algorithmes ~ 】 pour votre propre usage

Catalogue des articles

• • @[toc]
  • • HashAutres
    • • [1. Somme des deux nombres](https://leetcode-cn.com/problems/two-sum/)
      • [387. Le premier caractère unique de la chaîne](https://leetcode-cn.com/problems/first-unique-character-in-a-string/)
    • Fonctionnement de la liste de liens
    • • [2. Ajouter deux nombres](https://leetcode-cn.com/problems/add-two-numbers/)
      • [19. Supprimer l'avant - dernier de la liste N Noeuds](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
      • q25_kUne liste de liens inversés
      • [61. Liste des chaînes rotatives](https://leetcode-cn.com/problems/rotate-list/)
      • q138_Copier une liste liée avec un pointeur aléatoire
      • [206. Inverser la liste des liens](https://leetcode-cn.com/problems/reverse-linked-list/)
    • Double pointeur traversant /Fenêtre coulissante
    • Traversée rapide et lente du pointeur
    • Fusion des intervalles
    • Opération string
    • Fonctionnement numérique
    • Opération Array
    • • [54. Matrice hélicoïdale](https://leetcode-cn.com/problems/spiral-matrix/)
      • [581. Sous - Tableau séquentiel désordonné le plus court](https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/)
    • Stack - related
    • Heap - related
    • Récursion
    • Diviser et gouverner/Dichotomie
    • Planification dynamique
    • Méthode de rétrosuivi
    • Arbre du dictionnaire（Arbre préfixe）
    • Traversée de l'arbre
    • Arbre de recherche binaire corrélé

HashAutres

1. Somme des deux nombres

C'est facile.11915Le partage des collections passe à l'anglais pour recevoir des commentaires dynamiques

Donner un tableau entier nums Et une valeur cible entière target,Veuillez trouver dans ce tableau Et pour les valeurs cibles target Celui - là. Deux. Entier,Et renvoie leurs indices de tableau.

Vous pouvez supposer que chaque entrée ne correspond qu'à une seule réponse.Mais,Le même élément du tableau ne peut pas être répété dans la réponse.

Vous pouvez retourner les réponses dans n'importe quel ordre.

Exemple 1：

Entrée：nums = [2,7,11,15], target = 9
Produits：[0,1]
Explication：Parce que nums[0] + nums[1] == 9 ,Retour [0, 1] .

Exemple 2：

Entrée：nums = [3,2,4], target = 6
Produits：[1,2]

Exemple 3：

Entrée：nums = [3,3], target = 6
Produits：[0,1]

Conseils：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Il n'y aura qu'une seule réponse valide

**Niveau avancé：**Vous pouvez penser à une complexité temporelle inférieure à O(n2) L'algorithme de？

class Solution {
    
    // Violence
    public int[] twoSum(int[] nums, int target) {
    
        int[] res = new int[2];
        int len=nums.length;
        for(int i=0;i<=len-1;i++){
    
            for(int j=i+1;j<=len-1;j++){
    
                if(nums[i]+nums[j]==target){
    
                    res[0]=i;
                    res[1]=j;
                    return res;
                }
            }
        }
        return res;
    }

}


/** * Encore une foishash Tempso(n) Espaceo(n) */

import java.util.Map;
import java.util.HashMap;
class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        Map<Integer,Integer> map =new HashMap<Integer,Integer>();
       
        int len=nums.length;
        for(int i=0;i<=len-1;i++){
    
            if(map.containsKey(target-nums[i])){
    
                return new int[]{
    map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }

}

387. Le premier caractère unique de la chaîne

C'est facile.429Le partage des collections passe à l'anglais pour recevoir des commentaires dynamiques

Donner une chaîne,Trouve son premier caractère non dupliqué,Et renvoie son index.S'il n'existe pas,Renvoie -1.

Exemple：

s = "leetcode"
Retour 0

s = "loveleetcode"
Retour 2

**Conseils：**Vous pouvez supposer que la chaîne ne contient que des lettres minuscules.

import java.util.*;
class Solution {
    

    public int firstUniqChar(String s) {
    
        char[] chars = s.toCharArray();
        
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        
        // Dupliquer les caractères en haut-1;
        for(int i=0;i<=s.length()-1;i++){
    
            if(map.containsKey(chars[i])){
    
                map.put(chars[i],-1);
            }else{
    
                map.put(chars[i],i);
            }
        }
        // Si c'est la première fois qu'on ne fait pas-1 On revient.
        for(int i=0;i<=s.length()-1;i++){
    
           int value = map.get(chars[i]);
            if(value!=-1){
    
                return value;
            }
            
        }
        return -1; 
    }
}

Fonctionnement de la liste de liens

2. Ajouter deux nombres

Difficulté moyenne6636

Deux pour toi. Non vide Liste des liens,Représente deux entiers non négatifs.Chacun d'eux est basé sur Ordre inverse Stocké,Et chaque noeud ne peut stocker que Un homme Nombre.

Veuillez additionner les deux nombres,Et renvoie une liste de liens représentant et sous la même forme.

Vous pouvez supposer qu'en plus des chiffres 0 Au - delà,Ni l'un ni l'autre ne compte 0 Au début.

Exemple 1：

Entrée：l1 = [2,4,3], l2 = [5,6,4]
Produits：[7,0,8]
Explication：342 + 465 = 807.

Exemple 2：

Entrée：l1 = [0], l2 = [0]
Produits：[0]

Exemple 3：

Entrée：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Produits：[8,9,9,9,0,0,0,1]

Conseils：

• Le nombre de noeuds dans chaque liste de liens est dans la plage [1, 100] Intérieur
• 0 <= Node.val <= 9
• Les chiffres indiqués dans la liste d'assurance des données sur les sujets ne contiennent pas de zéros en tête

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */

/** * Deux traversées * Première traversée：Les deux listes de liens correspondent à la somme de chaque noeud,S'il y a un noeud vide, le noeud vide prend0,Créer une nouvelle liste de liens. * Deuxième traversée：Traversée de la nouvelle liste de liens pour la somme récupérée,Jugez le présentvalEst supérieur ou égal à10,Supérieur ou égal à lui - même-10LenextPlus1,SinextNouveau si vide0Noeud. */

class Solution {
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        ListNode res=new ListNode(l1.val+l2.val);
        ListNode link1=l1.next;
        ListNode link2=l2.next;
        ListNode p=res;
        while(link2!=null||link1!=null){
    
            int a=0;
            int b=0;
            if(link1!=null){
    
                a=link1.val;
            }
            if(link2!=null){
    
                b=link2.val;
            }

            int t=a+b;

            p.next=new ListNode(t);
            p=p.next;

            if(link1!=null){
    
                link1=link1.next;
            }
            if(link2!=null){
    
                link2=link2.next;
            }
        }
        p=res;
        while(p!=null){
    
            if(p.val>=10){
    
                p.val=p.val-10;
                if(p.next==null){
    
                   p.next=new ListNode(0);
                }
                p=p.next;
                p.val=p.val+1;
            }
            else{
    
                p=p.next;
            }
        }
        return res;
    }
}

19. Supprimer l'avant - dernier de la liste N Noeuds

Difficulté moyenne1525

Voici une liste de liens,Supprimer l'avant - dernier de la liste n Noeuds,Et renvoie le noeud d'en - tête de la liste liée.

**Niveau avancé：**Pouvez - vous essayer une implémentation de scan？

Exemple 1：

Entrée：head = [1,2,3,4,5], n = 2
Produits：[1,2,3,5]

Exemple 2：

Entrée：head = [1], n = 1
Produits：[]

Exemple 3：

Entrée：head = [1,2], n = 1
Produits：[1]

Conseils：

• Le nombre de noeuds dans la liste est sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
    
                ListNode res = new ListNode(0);
                res.next=head;
                ListNode fast=res;
                ListNode slow=res;

                for(int i=1;i<=n+1;i++){
    
                    fast=fast.next;
                }

                while(fast!=null){
    
                    fast=fast.next;
                    slow=slow.next;
                }

                slow.next=slow.next.next;
                return res.next;
    }

    
}

q25_kUne liste de liens inversés

61. Liste des chaînes rotatives

Difficulté moyenne615

Pour vous donner un noeud d'en - tête de liste head ,Liste des chaînes rotatives,Déplacer chaque noeud de la liste vers la droite k Position.

Exemple 1：

Entrée：head = [1,2,3,4,5], k = 2
Produits：[4,5,1,2,3]

Exemple 2：

Entrée：head = [0,1,2], k = 4
Produits：[2,0,1]

Conseils：

• Le nombre de noeuds dans la liste de liens est dans la plage [0, 500] Intérieur
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode rotateRight(ListNode head, int k) {
    
        if(head==null|| k==0){
    
            return head;
        }
        int len=1;
        ListNode tail=head;
        ListNode pre=head;
        ListNode res=head;
        while(tail.next!=null){
    
            tail=tail.next;
            len++;
        }
        tail.next=head;
        //Nombre de mouvements de la liste cyclique,BientôtresPointeur déplacé vers la fink%lenDivision
        int loop=len-(k%len);
        System.out.println(k);
        for(int i=0;i<loop;i++){
    
            pre=res;
            res=res.next;
        }
        pre.next=null;
        return res;
    }
}

q138_Copier une liste liée avec un pointeur aléatoire

206. Inverser la liste des liens

C'est facile.1921

Voici le noeud d'en - tête de la table à chaîne unique head ,Veuillez inverser la liste,Et renvoie la liste des liens inversés.

Exemple 1：

Entrée：head = [1,2,3,4,5]
Produits：[5,4,3,2,1]

Exemple 2：

Entrée：head = [1,2]
Produits：[2,1]

Exemple 3：

Entrée：head = []
Produits：[]

Conseils：

• La plage de nombre de noeuds dans la liste de liens est [0, 5000]
• -5000 <= Node.val <= 5000

**Niveau avancé：** La liste des liens peut être inversée de façon itérative ou récursive .Pouvez - vous résoudre le problème de deux façons？

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        //Tête insérée
        ListNode p=new ListNode(0);
        p.next=null;
        ListNode temp=head;
        while(head!=null){
    
            temp=head.next;
            head.next=p.next;
            p.next=head;
            head=temp;
        }

        return p.next;
    }
}

Double pointeur traversant /Fenêtre coulissante

• q3_Sous - chaîne la plus longue sans caractères dupliqués
• q11_Contenant contenant le plus d'eau
• q15_Somme des trois
• q16_La somme des trois plus proches
• q26_Supprimer les duplicatas dans le tableau de tri
• q42_Prends la pluie
• q121_Le meilleur moment pour acheter et vendre des actions
• q209_Sous - tableau de longueur minimale

Traversée rapide et lente du pointeur

• q141_Liste des anneaux
• q202_Happy Number
• q876_Noeud intermédiaire de la liste de liens

Fusion des intervalles

• q56_Fusionner les intervalles

Opération string

• q6_ZTransformation des glyphes
• q14_Préfixe public le plus long
• q763_Diviser les intervalles de lettres

Fonctionnement numérique

• q7_Entier inversé
• q8_Entier de conversion de chaîne
• q9_Nombre de réponses
• q43_Multiplication des chaînes
• q172_ Zéro après factoriel
• q258_Tout le monde additionne

Opération Array

54. Matrice hélicoïdale

Difficulté moyenne859Le partage des collections passe à l'anglais pour recevoir des commentaires dynamiques

Pour toi m D'accord n Matrice des colonnes matrix ,Veuillez suivre Séquence hélicoïdale dans le sens des aiguilles d'une montre ,Renvoie tous les éléments de la matrice.

Exemple 1：

Entrée：matrix = [[1,2,3],[4,5,6],[7,8,9]]
Produits：[1,2,3,6,9,8,7,4,5]

Exemple 2：

Entrée：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Produits：[1,2,3,4,8,12,11,10,9,5,6,7]

Conseils：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

• q73_Matrice à zéro

• q78_Sous - ensemble

• q384_Brouiller le tableau

581. Sous - Tableau séquentiel désordonné le plus court

Difficulté moyenne693

Pour vous donner un tableau entier nums ,Tu dois trouver un Sous - tableaux consécutifs ,Si ce sous - tableau est trié par ordre croissant,Alors tout le tableau devient un tri ascendant.

S'il vous plaît, trouvez ce qui correspond au titre Le plus court Sous - Tableau,Et la sortie de sa longueur.

Exemple 1：

Entrée：nums = [2,6,4,8,10,9,15]
Produits：5
Explication：Tu as juste besoin d'avoir raison. [6, 4, 8, 10, 9] Tri ascendant,Alors toute la table devient un tri ascendant.

Exemple 2：

Entrée：nums = [1,2,3,4]
Produits：0

Exemple 3：

Entrée：nums = [1]
Produits：0

Conseils：

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

class Solution {
    
    public int findUnsortedSubarray(int[] nums) {
    
        if (nums == null || nums.length < 1) {
    
            return 0;
        }

        int[] cloneNums = nums.clone();
        Arrays.sort(nums);

        int begin = Integer.MAX_VALUE;
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
    
            if (nums[i] != cloneNums[i]) {
    
                begin = Math.min(begin, i);
                end = Math.max(end, i);
            }
        }
        return Math.max(end - begin + 1, 0);
    }

}

• q945_ Rendre le tableau unique par incréments minimaux

Stack - related

• q20_Parenthèses valides
• q32_Parenthèses valides les plus longues
• q155_La plus petite pile
• q224_Calculatrice de base
• q232_Mise en file d'attente avec pile
• q316_Supprimer les lettres en double

Heap - related

• q215_Dans le tableauKÉlément maximum
• q347_AvantKDes éléments à haute fréquence

Récursion

• q21_Fusionner deux listes ordonnées
• q101_Arbre binaire symétrique
• q104_Profondeur maximale de l'arbre binaire
• q226_Retourner l'arbre binaire
• q236_L'ancêtre public le plus proche de l'arbre binaire
• q1325_ Supprimer le noeud de feuille pour une valeur donnée

Diviser et gouverner/Dichotomie

• q23_FusionnerKListe des liens de tri
• q33_Recherche d'un tableau de tri rotatif
• q34_Trouver la première et la dernière position de l'élément dans le tableau de tri

Planification dynamique

• q5_Sous - chaîne palindrome la plus longue
• q53_Sous - ordre maximum et
• q62_Différents chemins
• q64_Chemin minimal et
• q70_Escaliers
• q118_Yang hui triangle
• q300_La plus longue séquence ascendante
• q1143_La plus longue sous - séquence commune
• q1277_ Toutes les statistiques sont 1Sous - matrice carrée de

Méthode de rétrosuivi

• q10_Les expressions régulières correspondent
• q22_Génération de parenthèses
• q40_Total combiné2
• q46_Disposition complète

Arbre du dictionnaire（Arbre préfixe）

• q648_Substitution de mots

Traversée de l'arbre

• q94_Traversée du milieu de l'arbre binaire
• q102_Traversée hiérarchique de l'arbre binaire
• q110_Arbre binaire équilibré
• q144_Traversée pré - ordonnée de l'arbre binaire
• q145_Traversée post - ordre de l'arbre binaire

Arbre de recherche binaire corrélé

• q98_Valider l'arbre de recherche binaire
• q450_Supprimer les noeuds de l'arbre de recherche binaire
• q701_Insertion dans l'arbre de recherche binaire