编程知识 cdmana.com

【 catalogue d'algorithmes ~ 】 pour votre propre usage


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:

img

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:

img

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:

img

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

Exemple 2:

img

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:

img

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

Exemple 2:

img

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

Traversée rapide et lente du pointeur

Fusion des intervalles

Opération string

Fonctionnement numérique

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:

img

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

Exemple 2:

img

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:

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);
    }

}

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é

版权声明
本文为[Sun zhongming]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211945011g.html

Scroll to Top