Algorithm
本周选择的算法题是：Longest Increasing Subsequence
规则如下：
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(\(n^{2}\)) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Solution
我实现的方案：
解法一：dp
Runtime：1132 ms，快过 24.85%。
Memory：14.1 MB，低于 5.61%。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
length = len(nums)
dp = [1] * length
for i in range(1, length):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[j] + 1, dp[i])
return max(dp)
dp 的解法比较简单粗暴，时间耗时也长。
时间复杂度是 O(\(n^{2}\))，该题最后有一个追加：用 O(n log n) 解决它。
解法二：dp with binary search
Runtime：48 ms，快过 89.69%。
Memory：13.9 MB，低于 5.61%。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
length = len(nums)
dp = [None] * length
dp_length = 0
def binary_search(num: int, length: int) -> int:
low, high = 0, length
while low < high:
middle = low + (high - low) // 2
if dp[middle] == num:
return middle
elif dp[middle] < num:
low = middle + 1
else:
high = middle
return low
for num in nums:
position = binary_search(num, dp_length)
dp[position] = num
dp_length += dp[dp_length] == num
return dp_length
这个算法在 GeeksforGeeks 详细解释过，推导过程如下。
构建 active lists
active lists 记录了所有潜在的最长上升子序列，构建过程根据以下三个原则(i 表示当前正在遍历的索引)：
- 如果 A[i] 小于所有 active lists 的最后一个元素，则开启一个新的长度为1的 active list
- 如果 A[i] 大于所有 active lists 的最后一个元素，则克隆最长的那个 active list，并追加 A[i]
- 如果 A[i] 处于两者之间，则找到小于 A[i] 的最长 active list，克隆并追加 A[i]，然后将与这个新 active list 长度相同的其他 list 丢弃
以序列 [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] 为例，整个过程如下：
A[0] = 0. Case 1. There are no active lists, create one.
0.
-----------------------------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
-----------------------------------------------------------------------------
A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
-----------------------------------------------------------------------------
A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
-----------------------------------------------------------------------------
A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
-----------------------------------------------------------------------------
A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
-----------------------------------------------------------------------------
A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
-----------------------------------------------------------------------------
A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
-----------------------------------------------------------------------------
A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
-----------------------------------------------------------------------------
A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
-----------------------------------------------------------------------------
A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------------------------
A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------------------------
[0, 2, 6, 9, 11, 15] 就是最长上升子序列。
再次观察
我们有必要存储完整的 active lists 么？毕竟题目的要求是返回最长上升子序列的长度就够了。
我们用一个一维的辅助数组记录每个 list 最后一个元素即可。最终的问题其实是：
何时拓展或替换最后一个元素是安全的？
问题到这里就结束了。
我实现的 leftmost 不够简洁优雅，这里有一个更好的版本：
def CeilIndex(A, l, r, key):
while (r - l > 1):
m = l + (r - l)//2
if (A[m] >= key):
r = m
else:
l = m
return r
Review
耐心排序，这是最长上升子序列背后的算法，来自于纸牌游戏 patience，其规则是：
- 初始时，没有任何牌组，所以第一张牌会开始一个新的牌组
- 后续的牌如果小于等于现有牌组的最后一个元素，就插入到第一个小于等于的牌组里
- 后续的牌如果大于现有牌组的最后一个元素，就创建一个新的牌组
- 发牌游戏结束；用多路归并算法得到最终结果
这里贴一个 python 的实现：
from functools import total_ordering
from bisect import bisect_left
from heapq import merge
@total_ordering
class Pile(list):
def __lt__(self, other): return self[-1] < other[-1]
def __eq__(self, other): return self[-1] == other[-1]
def patience_sort(n):
piles = []
# sort into piles
for x in n:
new_pile = Pile([x])
i = bisect_left(piles, new_pile)
if i != len(piles):
piles[i].append(x)
else:
piles.append(new_pile)
# use a heap-based merge to merge piles efficiently
n[:] = merge(*[reversed(pile) for pile in piles])
if __name__ == "__main__":
a = [4, 65, 2,-31, 0, 99, 83, 782, 1]
patience_sort(a)
print(a)
Tip
本周学习到的一些内容：
Xcode 11 Beta (iOS 13)中不再返回
PHImageFileURLKey，作为替代方案，有几个选择：利用
PHContentEditingInput获取：asset.requestContentEditingInput(with: nil, completionHandler: { (input, info) in if let input = input { print(input.fullSizeImageURL) // file:///xxx } })利用 KVC 从
PHAsset获取原始文件名：asset.value(forKey: "filename") // IMG_xxx.HEIC利用
PHAssetResource获取原始文件名和文件路径：if let resource = PHAssetResource.assetResources(for: asset).first { print(resource.originalFilename) // IMG_xxx.HEIC print(resource.value(forKey: "_privateFileURL")) // file:///xxx }还有一种 bad way，使用正则从
debugDescription中提取
Share
本周分享：
对 The most important skill a programmer can learn 做了一个翻译，记录在这里：