2022-021rts: from the second half of the year

ARTS：Algorithm、Review、Tip、Share

• Algorithm Algorithm problem
• Review English articles
• Tip Think back to a small skill learned at work this week
• Share Think about a technical point of view 、 Social hot spots 、 A product or a puzzle

Algorithm

25. K A set of flip list

Give you the head node of the list head , Every time k Group of nodes to flip , Please return to the modified linked list .

k Is a positive integer , Its value is less than or equal to the length of the linked list . If the total number of nodes is not k Integer multiple , Please keep the last remaining nodes in the original order .

You can't just change the values inside the node , It's about actually switching nodes .

Example 1：

Input ：head = [1,2,3,4,5], k = 2
Output ：[2,1,4,3,5]
Example 2：

Input ：head = [1,2,3,4,5], k = 3
Output ：[3,2,1,4,5]

Tips ：
The number of nodes in the linked list is n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Advanced ： You can design one that uses only O(1) Does the algorithm of extra memory space solve this problem ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/reverse-nodes-in-k-group

Solution description

although LeetCode Mark the difficulty level on the question , But it's not very difficult after reading the solution . It mainly groups the linked list of input parameters , Then reverse each group , The process involves the situation that the header element may change , The trick is to regenerate a virtual node in front of the head node , In this way, even if it is reversed , You can also use the next The pointer gets the final header .

Specific implementation of reverse linked list , It is very common in interviews , I remember I was 2018 The first algorithm question asked during the interview in was a simple reverse linked list question , It also corresponds to LeetCode Of 206. Reverse a linked list At that time, I didn't pay attention to this aspect of learning 、 No practice , After thinking for a long time, I didn't write it out , In fact, in the algorithm topic , There is no sophisticated algorithm for linked list related topics , The main thing is to investigate coding The ability to , Just pay more attention to practice at ordinary times .

coded

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

    ListNode pre = originalHeadPre;
    while (head != null) {
    
        ListNode tail = pre;
        //  In turn k The first and last elements of elements 
        for (int i = 0; i < k; i++) {
    
            tail = tail.next;
            if (tail == null) {
    
                return originalHeadPre.next;
            }
        }

        ListNode nextHead = tail.next;
        //  Reverse 、 Connect back to the source linked list 
        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};
}

Complexity analysis

Time complexity O(N)
Spatial complexity O(1)

Review

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

Tip

Often asked in an interview Spring Managed bean What is the specific life cycle of ？ We may find it in many places , from Spring Root interface BeanFactory Of notes Can get the official answer ：

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

Last weekend, I finally launched a recently busy project , Last week's summary was also negative , Complained about his negative emotions , This week is also a rest , Take this opportunity to reflect on your shortcomings , In the past, I failed to do many things well , Often distracted in the process 、 Unable to focus , There are many things at hand , There is no primary or secondary , Plus being interrupted intentionally or unintentionally 、 Active interruption , What's more, the accumulation is poor , Although it is also intended to change , But it will return to its original state after two days . Recently read 《 The courage to be hated 》, The book says that it's useless to dwell on the past , The important thing is in the present , What is our purpose , Whether you want to change , I will think more later , What to do , What not to do , Which priorities are higher , And make yourself more focused 、 Concentrate on .

Not only has it arrived unconsciously 22 Second half of , Expect yourself to become better and better .