ARTS #4

Algorithm

LeetCode 26. Remove Duplicates from Sorted Array

输入一个列表，要求返回去重后列表的长度，且必须在源列表上操作，空间复杂度限制为O(1)。

这道题乍看上去很简单，特别是使用 Python、JavaScript 这类语言的话，语言本身自带了一些列表去重的方法（转为 Set 再转回 List）。不过，这与题意相悖，而且要求空间复杂度为 O(1)，关于内置转换方法的空间复杂度是否为 O(1) 这一点存疑。

一个更加通用的解法是使用快慢指针实现原址排列。快慢指针即使用两个指针遍历列表（或其它可遍历对象），然后据此作出对应的比较，是一种很常见的方法。时间复杂度为 O(n)，空间复杂度为 O(1)。

Code Talks:

def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    if n==0:
        return 0
    i = 0
    for j in range(1, n):
        if nums[i] != nums[j]:
            nums[i+1] = nums[j]
            i += 1
    return i+1

27. Remove Element

和第 26 题很相似。当然可以使用 Python 自带的 .remove 方法，不过这有点 cheat 的感觉。

同样使用了双指针，只是在具体的处理上略有不同。

def removeElement(nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """
    n = len(nums)
    if n==0:
        return
    i = 0
    for j in range(n):
        if nums[j] != val:
            nums[i] = nums[j]
            i += 1
    return i

203. Remove Linked List Elements

和上一题类似，不过现在操作的是链表，而不是数组。基本的思路还是使用快慢指针。

Solution 1 fakeHead

这里有一个小技巧，创建一个 fakeHead 的变量，并将其 next 指向原本的 head，方便最后输出。

def removeElements(head, val):
    fakeHead = ListNode(-1)
    fakeHead.next = head
    slow, fast = fakeHead, head
    while fast:
        if fast.val == val:
            slow.next = fast.next
        else:
            slow = slow.next
        fast = fast.next
    return fakeHead.next

Solution 2

这是另外一个思路。本质上要想删除链表上某个值，只需要将其父节点的 next 指向其子节点（跳过待删除的节点）即可。

def removeElements(head, val):
    if not head:
        return None
    pointer = head
    while pointer.next:
        if pointer.next.val == val:
            pointer.next = pointer.next.next
        else:
            pointer = pointer.next
    return head if head.val != val else head.next

Review

Presentational and Container Components

本文介绍了 React 里面的两种组件模式：展示组件和容器组件，或者说是木偶组件和智能组件。

展示组件（木偶组件）：

• 关注如何展示
• 通常具有 DOM 节点和样式
• 通常允许通过 this.props.children 来传递内容
• 不依赖 App 的其余部分，如 Actions 和 Store
• 通过 props 接收数据和回调
• 一般没有自己的状态（state），如果有也是为了管理 UI 状态
• 一般是函数式组件，除非需要 state、生命周期钩子或者性能优化
• 举例：Avatar、Sidebar、Story

容器组件（智能组件）：

• 关注事件逻辑
• 通常不具有 DOM 节点（除了 wrappers）和样式
• 提供数据和回调给展示组件
• 依赖 App 的其它部分，如 Actions、Store
• 通常是有状态的
• 通常由高阶函数生成，如 React Redux 的 connect()
• 举例：UserPage

这样的划分并不是绝对的，展示组件内也可以有容器组件。

如此这般的好处在于：

1. 逻辑层与 UI 层解耦。
2. 展示组件具有更高的重用性。
3. 可以像使用七巧板一样使用展示组件，以构造出合理的用户界面。
4. 强迫你去思考组件的结构。

Tips

分享一个很实用的 bash 命令：tree，尤其是在看项目结构或者写文档的时候，非常方便。

这个命令是 Linux 自带的，macOS 用户可以 brew install tree。

src
├── api
├── components
├── ...
├── views
├── App.vue
├── ...
└── index.template.html

有几个比较常用的参数：

• --dirsfirst 目录排在最前
• -L [数字] 指定列出的层数
• -d 只列出目录
• -o [filename] 结果输出到指定文件
• -J 以 JSON 格式输出

其余参数可以参考 --help

Share

偶然看到这篇文章A LeetCode Grinding Guide，大概可以作为 LeetCode 刷题的一个指北。

个人感觉，可以利用好 LeetCode 的 Tag 筛选和每个题目的 Related Question，因为对于同一类型的问题，解决问题的范式是类似的，这样可以及时巩固学到的思路，也能提高学习的效果。