2022 - 021arts: début du deuxième semestre

ARTS：Algorithm、Review、Tip、Share

• Algorithm Problème d'algorithme
• Review Article en anglais
• Tip Rappelez - vous une petite astuce que vous avez apprise au travail cette semaine
• SharePenser à un point de vue technique、Points chauds sociaux、Un produit ou une confusion

Algorithm

25. K Une liste de liens inversés

Voici le noeud d'en - tête de la liste head ,Chaque k Les noeuds tournent en groupes,Veuillez retourner à la liste modifiée.

k C'est un entier positif,Sa valeur est inférieure ou égale à la longueur de la liste.Si le nombre total de noeuds n'est pas k Nombre entier de fois de,Alors gardez les derniers noeuds restants dans l'ordre d'origine.

Vous ne pouvez pas simplement changer les valeurs à l'intérieur d'un noeud,Au lieu de cela, un échange de noeuds réel est nécessaire.

Exemple 1：

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

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

Conseils：
Le nombre de noeuds dans la liste de liens est n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Niveau avancé：Vous pouvez en concevoir un qui n'utilise que O(1) L'algorithme de l'espace mémoire supplémentaire résout - il ce problème？

Source:：Boucle de force（LeetCode）
Liens：https://leetcode.cn/problems/reverse-nodes-in-k-group

Description de la solution

Bien queLeetCode C'est un niveau difficile. , Mais ce n'est pas si difficile à comprendre. . Il s'agit principalement de grouper les listes de liens entrants , Puis inversez chaque groupe , Les situations dans lesquelles les éléments d'en - tête peuvent être modifiés au cours du processus , L'astuce est de régénérer un noeud virtuel devant le noeud de tête , De cette façon, même si l'inversion est faite , Vous pouvez également utiliser le next Pointeur vers le noeud final de la tête .

Réalisation d'une liste de liens inversés spécifiques , C'est assez courant dans les interviews ,Je me souviens que j'étais2018 La première question algorithmique que j'a i posée à l'entrevue était une simple question de liste inversée. ,Ça correspond aussiLeetCodeDe 206. Inverser la liste des liens Parce qu'il n'y avait pas d'accent sur l'apprentissage 、 Pas d'entraînement non plus , J'y ai réfléchi et je ne l'ai pas écrit. , En fait, dans le titre de l'algorithme , Il n'y a pas d'algorithme profond pour les problèmes liés à la Liste ,C'est surtout l'inspectioncodingLa capacité de, Faites attention à la pratique. .

Mise en œuvre du codage

public ListNode reverseKGroup(ListNode head, int k) {
    
    ListNode originalHeadPre = new ListNode(-1);
    originalHeadPre.next = head;

    ListNode pre = originalHeadPre;
    while (head != null) {
    
        ListNode tail = pre;
        // Dans l'ordrek Élément de tête et de queue de l'élément 
        for (int i = 0; i < k; i++) {
    
            tail = tail.next;
            if (tail == null) {
    
                return originalHeadPre.next;
            }
        }

        ListNode nextHead = tail.next;
        // Marche arrière、 Retour à la liste des sources 
        ListNode[] htGroup = this.myReverse(head, tail);
        pre.next = htGroup[0];
        htGroup[1].next = nextHead;

        pre = htGroup[1];
        head = nextHead;
    }

    return originalHeadPre.next;
}

ListNode[] myReverse(ListNode head, ListNode tail) {
    
    ListNode newNext = tail.next;
    ListNode cur = head;

    while (newNext != tail) {
    
        ListNode curNext = cur.next;
        cur.next = newNext;

        newNext = cur;
        cur = curNext;
    }
    return new ListNode[]{
    tail, head};
}

Analyse de la complexité

Complexité temporelleO(N)
Complexité spatialeO(1)

Review

How does one begin to tackle understanding a large open source code base?

Tip

On me demande souventSpringGestionbean Quel est le cycle de vie de ？ On peut le trouver dans de nombreux endroits. ,DeSpringInterface racineBeanFactoryDeNotes Pour obtenir une réponse officielle ：

Bean factory implementations should support the standard bean
lifecycle interfaces as far as possible. The full set of
initialization methods and their standard order is:

1. BeanNameAware’s setBeanName
2. BeanClassLoaderAware’s setBeanClassLoader
3. BeanFactoryAware’s setBeanFactory
4. EnvironmentAware’s setEnvironment
5. EmbeddedValueResolverAware’s setEmbeddedValueResolver
6. ResourceLoaderAware’s setResourceLoader (only applicable when running in an application context)
7. ApplicationEventPublisherAware’s setApplicationEventPublisher (only applicable when running in an application context)
8. MessageSourceAware’s setMessageSource (only applicable when running in an application context)
9. ApplicationContextAware’s setApplicationContext (only applicable when running in an application context)
10. ServletContextAware’s setServletContext (only applicable when running in a web application context)
11. postProcessBeforeInitialization methods of BeanPostProcessors
12. InitializingBean’s afterPropertiesSet
13. a custom init-method definition
14. postProcessAfterInitialization methods of BeanPostProcessors

On shutdown of a bean factory, the following lifecycle methods apply:

1. postProcessBeforeDestruction methods of DestructionAwareBeanPostProcessors
2. DisposableBean’s destroy
3. a custom destroy-method definition

Share

J'a i enfin mis en ligne un projet très occupé le week - end dernier. , Le bilan de la semaine dernière était négatif. , Se plaindre d'un sentiment négatif , C'est une semaine de repos. , Profitez de cette occasion pour réfléchir à vos lacunes , Beaucoup de choses n'ont pas ét é faites par moi - même dans le passé. , Ils sont souvent distraits. 、Je ne peux pas me concentrer., Beaucoup de choses à faire , Et il n'y a pas de Maître , En plus d'être interrompu intentionnellement ou involontairement 、 Cas d'interruption active , C'est une accumulation de misère , Bien qu'il y ait eu un changement intentionnel , Mais pas dans deux jours. .Lire récemment《Le courage d'être haï》, Il n'y a pas de raison de s'attarder sur le passé. , L'important, c'est que dans le moment présent ,Quel est notre but?, Voulez - vous vraiment changer , J'en penserai plus après moi - même. ,Que faire?, Ne rien faire , Quelles sont les priorités les plus élevées , Et se concentrer davantage 、Concentre - toi.

Non seulement il est arrivé par inadvertance, 22Le second semestre de l'année, Attendez - vous à ce que vous vous amélioriez. .