ARTS #138

Algorithm

规则

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

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]

Constraints:

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

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = jump = ListNode()
        dummy.next = right = left = head
        while True:
            count = 0
            while right and count < k:
                right = right.next
                count += 1
            if count == k:
                pre, node = right, left
                for _ in range(k):
                    node.next, node, pre = pre, node.next, node
                jump.next, jump, left = pre, left, right
            else:
                return dummy.next

Review

Avoiding Premature Software Abstractions

计算机领域有一句著名的话：“计算机科学中遇到的所有问题都可通过增加一层抽象来解决”，但往往会忽视后半句“除了抽象层太多的问题”，原话是：

All problems in computer science can be solved by another layer of abstraction… Except for the problem of too many layers of abstraction.
— Butler Lampson

仅仅出于“关注点分离”或“不依赖于具体实现”之类的理论而增加抽象层是不可取的，每抽象一层都会带来更高的复杂性，每次引入新的复杂性时，都应该出于有具体、实用、现实的好处，否则将与计算机领域另外两条设计原则冲突：

YAGNI - You Aren’t Gonna Need It - 不要设计当前用不到的功能、不要保留无用代码
KISS - Keep It Simple Stupid - 保持简单易懂

代码库的目标是保证修改和重构（部署）是简单而快速的，要避免随着时间推移引入越来越多/老化的抽象层，

Tip

基本上验证了 Kotlin Native 在 iOS/Android 跨端的可行性。

分享一个故事吧：

约翰是好莱坞著名的编剧，多次获得过艾美奖。可他自己知道，这一切荣誉的背后，是一个支离破碎的家。
当约翰还在拍摄他的第一部电视剧的时候，他几乎整日整夜都在待命，确保每周的节目能顺利播出。与此同时，他的妻子玛戈独立承担起照顾两个孩子的重任，她快被压垮了。
每天晚上是约翰和玛戈唯一可以互相见面聊聊天的时候，但晚餐时约翰还经常要通过手机应付工作中的突发情况，每当这时，玛戈就会送来「死亡凝视」。
约翰很委屈，他对玛戈说：我奋斗了这么多年就是为了这个机会，我必须要抓住它。
如约翰所愿，观众们得到了一部好看的电视剧，但约翰得到了一位愤怒、委屈的妻子。
成功的约翰变得更忙了，收入也不断提高。
在工作的同时，他尽可能花周末的时间来陪玛戈和孩子。他觉得手机简直是上天赐予自己的礼物，这让无法同时出现在片场和家里的自己可以「兼顾」工作和生活。
「在陪你们的同时接几个电话又能怎么样呢？」
在一次外出旅行的前夜，玛戈问约翰，她在假期中能不能不打电话。这是孩子们盼望已久的一次家庭旅行，而且只有三天的时间。
「除非有人死了，请不要接那该死的电话」，玛戈说。
为了避免更多的争吵，约翰答应了。
他对剧组说，如果没有紧急情况，请不要给自己打电话，这个旅行对自己和家人很重要。只有三天时间，他相信大家可以解决问题的。
一路上，约翰、玛戈和孩子们欢声笑语，他们看着路边的风景，聊着过去的事情，对即将开始的旅途兴奋不已。
约翰感受到了很久未曾感受到的平静，他相信过去的一切都会被解决，慢慢都会好的。
这时，约翰的电话响了。
电话就放在车的仪表盘上，约翰瞟了电话一眼，也注意到玛戈送来的「死亡凝视」。
约翰很清楚，他已经再三对剧组说，除非紧急情况不要给自己打电话了。难道，真的发生了紧急情况？
「别接」，玛戈说。
「我只是想看看谁打来的。」
「该死」，这是玛戈第一次在孩子面前说脏话。
「别他妈的骂我」，约翰也忍不住了。
除了手机铃声，一切都仿佛凝固了。
过了一会儿，手机不响了。
约翰请玛戈看一下是谁打来的电话，玛戈失望地把头扭向了车窗外。
约翰伸出自己的右手去拿手机，就在他低头查看的一瞬间，一辆黑色越野车向他们撞了过来。
盖比，他们最小的孩子，当场被夺去了生命。
在失控的越野车撞向他们的那一瞬间，约翰在低头拿手机，玛戈则生气地望着窗外。
阅读《别找替罪羊》的过程中，我总是想起了约翰和玛戈的故事。
身处局外的我们可能会觉得，如果约翰忽略那个电话就好了，或者如果玛戈帮他查看一下来电就好了。可惜，永远没有如果。
约翰和玛戈的反应，并不是那个来电引发的。
他们分别居住在自己的盒子里，在那里，他们看到的并不是双方真实的样子。
我甚至难过地觉得：
也许玛戈期待这个来电，「看，他根本做不到自己的承诺，完全没有把家当回事儿」。
也许约翰期待玛戈的反应，「看，她就是这样不理解我，完全不可理喻」。
那个未被接通的来电，原来是别人打错了。

这段来自我长期关注的一位博主，在他最新的一篇欺骗里提到了《也许你该找个人聊聊》。我认为判断是非对错的天平并不总是公正的，内在想法和外部行动也不能真实反映一个人的全部，如果因不能接受自己犯错而期待对方做那些你讨厌的事情，虽然能让自己感到舒服和自洽，但却将自己封闭进自我欺骗的盒子，不再能以客观的视角来看待他人和他的行动。所以，承认错误和自责是两回事，产生的结果也是不同的。

Algorithm

规则

Solution

Review

Tip

Share