ARTS - Week 10

ARTS - Week 10

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 24 - Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

Difficulty: Medium

Example:

Swap Nodes in Pairs

Solution

自己的解法

保存遍历时的前结点和当前节点的第二个后节点,进行一次性转换指针

# Python

class Solution:
    def swapPairs(self, head):
        if not head or not head.next:
            return head
        prev = ListNode(None)
        node = head
        new_head = head.next
        while node and node.next:
            node.next.next, prev.next, node.next, prev = node, node.next, node.next.next, node
            node = node.next

        return new_head

复杂度

  • Time complexity: O(N);
  • Space complexity: O(N);

运行结果

Python:
Runtime: 32 ms.
Your runtime beats 100.00 % of python3 submissions.
Your memory usage beats 71.35 % of python3 submissions.

这种方法里一次性赋值转换指针的逻辑不是很顺,查看别人的讨论发现了更优的解法。

更优解法

记录遍历的前节点,当前节点,当前节点的后节点。一次性赋值转换指针时依次从前节点的后节点往后进行赋值,例如prev>a>b>b.next>prev>b>a>b.next。这样逻辑更清晰。

# Python

class Solution:
    def swapPairs(self, head):
        prev, prev.next = self, head
        while prev.next and prev.next.next:
            a = prev.next
            b = a.next
            prev.next, b.next, a.next = b, a, b.next
            prev = a

        return self.next

复杂度

  • Time complexity: O(N);
  • Space complexity: O(N);

运行结果

Python:
Runtime: 32 ms.
Your runtime beats 100.00 % of python3 submissions.
Your memory usage beats 71.35 % of python3 submissions.


Review

Anti-If: The missing patterns

本文作者讨论了如果不使用 if ... else 语句,应该怎么写代码。因为很多情况下 if ... else ... 语句属于误用,会造成以下问题:

  • 一开始 if ... else ... 的逻辑会比较容易理解。但当逻辑变得越来越复杂后,会出现各种嵌套逻辑,不利于后期扩展和维护;
  • 使用 if ... else ... 会造成代码冗余;
  • 协作者得花费时间去理解大量分支逻辑。

作者给出了以下的改进模式:

  • 如果函数中存在布尔类型的参数,并且 if ... else ... 是基于这个参数,那么可以改写成两个独立的方法;
  • 当函数中根据不同类型,有不同的行为时,可以考虑使用多态的特性;
  • 当需要判断变量是否为 None 时,使用 NullObject 或者可选的类型;
  • 不要写出 return True if foo and bar这种代码,因为可以简化为 return foo and bar
  • 善于应用print('The sex is:', getattr(person, 'sex', default_value))这种模式

Tip

Python3 中类似三元运算符的方式有以下两种:

  1. print(a) if a > b else print(b)
  2. (a, b)[a > b]
    • 第二种方法使用元组实现。这种方法之所以能正常工作,是因为在 Python 中,True 等于 1,而 False 等于 0,这就相当于在元组中使用 0 和 1 来选取数据。
    • 这种表达式没有被广泛使用的原因是,元组中的两部分不管在何种情况下均会执行,会浪费一部分性能。而第一种方法中不存在这种问题。

# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×