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
这样的划分并不是绝对的,展示组件内也可以有容器组件。
如此这般的好处在于:
- 逻辑层与 UI 层解耦。
- 展示组件具有更高的重用性。
- 可以像使用七巧板一样使用展示组件,以构造出合理的用户界面。
- 强迫你去思考组件的结构。
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,因为对于同一类型的问题,解决问题的范式是类似的,这样可以及时巩固学到的思路,也能提高学习的效果。