Algorithm
本周选择的算法题是：Minimum Window Substring。
规则
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".
Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Example 2:
Input: s = "a", t = "a"
Output: "a"
Constraints:
1 <= s.length, t.length <= 105sandtconsist of English letters.
Solution
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
count = Counter(t)
curr_count, curr_window = defaultdict(list), []
ans = None
for i, char in enumerate(s):
if char in count:
curr_count[char].append(i)
curr_window.append(i)
if len(curr_count[char]) > count[char]:
curr_window.remove(curr_count[char].pop(0))
if len(curr_window) == len(t) and (not ans or curr_window[-1] - curr_window[0] < ans[1]):
ans = curr_window[0], i - curr_window[0]
return "" if not ans else s[ans[0]: ans[0] + ans[1] + 1]
代码比较简洁和直观，但由于对数组操作较多导致时间复杂度和空间复杂度较高，其实没必要用数组记录所有潜在字符的位置：
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
count, remaining = Counter(t), len(t)
l, ans = 0, None
for r, char in enumerate(s):
if char in count:
count[char] -= 1
if count[char] >= 0:
remaining -= 1
while remaining == 0:
curr_len = r - l + 1
if not ans or curr_len < ans[1]:
ans = l, curr_len
l_char = s[l]
if l_char in count:
count[l_char] += 1
if count[l_char] > 0:
remaining += 1
l += 1
return "" if not ans else s[ans[0]: ans[0] + ans[1]]
Review
What went wrong with the libdispatch. A tale of caution for the future of concurrency.
这篇文章实际是作者借着对 libdispatch 的吐槽传达几个观点：
- 多线程程序需要精心设计 - 这是显然的，却很容易忘记
- 通过设计”提高”使用多线程的门槛，迫使开发者在使用时多思考 - 不过这也太冰冷了，感觉缺少温度
- libdispatch 可以用（with care）
libdispatch 减少了使用多核的门槛，用起来很方便，但开发者也要有追求极致的决心，精心设计你的应用程序，这样才不枉 libdispatch 的诞生。
最后我们憧憬下未来 80 核的个人电脑吧 :)
Tip
在 bash 里远程登录并执行某个脚本：
bash -l -c "xctoken"
学习了 numpy 和 scipy 库的用法。