[数据结构与算法]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年的下半年，期待自己变得越来越好。