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,因为对于同一类型的问题,解决问题的范式是类似的,这样可以及时巩固学到的思路,也能提高学习的效果。

标签: none

添加新评论