2022-021ARTS：下半年開始

ARTS：Algorithm、Review、Tip、Share

• Algorithm 算法題
• Review 英文文章
• Tip 回想一下本周工作中學到的一個小技巧
• Share思考一個技術觀點、社會熱點、一個產品或是一個困惑

Algorithm

25. K 個一組翻轉鏈錶

給你鏈錶的頭節點 head ，每 k 個節點一組進行翻轉，請你返回修改後的鏈錶。

k 是一個正整數，它的值小於或等於鏈錶的長度。如果節點總數不是 k 的整數倍，那麼請將最後剩餘的節點保持原有順序。

你不能只是單純的改變節點內部的值，而是需要實際進行節點交換。

示例 1：

輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]
示例 2：

輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]

提示：
鏈錶中的節點數目為 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

進階：你可以設計一個只用 O(1) 額外內存空間的算法解决此問題嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/reverse-nodes-in-k-group

解法描述

雖然LeetCode上標識這道題為困難的級別，但看完題解感覺並不是很難了。主要是將入參鏈錶進行分組，然後對每一組進行反轉，過程中涉及到頭元素可能會變更的情况，技巧是在頭結點前面再生成一個虛擬節點，這樣即使進行了反轉，也可以通過虛擬節點的next指針拿到最終的頭結點。

具體反轉鏈錶的實現，面試中可謂很常見了，我記得我在2018年面試時問到的第一道算法題就是單純的一道反轉鏈錶題目，也對應了LeetCode的 206. 反轉鏈錶 當時因為沒有重視這方面的學習、也沒有練習，想了半天也沒有寫出來，其實在算法題目中，鏈錶相關的題目沒有什麼高深的算法，主要就是考察coding的能力了，平時多注意練習一些就可以了。

編碼實現

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

    ListNode pre = originalHeadPre;
    while (head != null) {
    
        ListNode tail = pre;
        // 依次得到k個元素的首尾元素
        for (int i = 0; i < k; i++) {
    
            tail = tail.next;
            if (tail == null) {
    
                return originalHeadPre.next;
            }
        }

        ListNode nextHead = tail.next;
        // 倒轉、接回源鏈錶
        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};
}

複雜度分析

時間複雜度O(N)
空間複雜度O(1)

Review

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

Tip

面試中經常被問到Spring管理的bean的生命周期具體是有哪些？我們可能從很多地方都能查到，從Spring根接口BeanFactory的注釋中能够得到官方的答案：

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

上周末終於把最近忙碌的一個項目上線了，上周的總結也比較負能量，抱怨了一通自己的負面情緒，這一周也算是一個休整吧，趁此機會也好好反思下自己的不足，過去的很多事自己都沒能做好，做的過程中也經常分心、無法專注，手頭的事情一多，也沒有個主次，再加上有意無意的被打斷、主動打斷的情况，更是積累的可憐，雖然也有意改變，但堅持不了兩天就又恢複原狀。最近在讀《被討厭的勇氣》，書上說糾結於過去的原因是沒有任何用的，重要的是在當下，我們的目的是什麼，究竟是否想要改變，自己後面也會更多的去思考，要做哪些事情，不做哪些事，哪些優先級更高，以及讓自己更加專注、專心。

不只不覺中已經來到了22年的下半年，期待自己變得越來越好。