Algorithm
本周选择的算法题是：Longest Valid Parentheses
规则如下：
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
Solution
这题解法多且复杂，值得深挖。
栈
Runtime：52 ms，快过 73.59%。
Memory：14.3 MB，低于 5.55%。
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack, max_length = [-1], 0
for i in range(len(s)):
char = s[i]
if char == '(':
stack.append(i)
else:
stack.pop()
if stack:
# 栈不是空的，括号配对成功，通过栈顶元素计算有效长度
max_length = max(max_length, i - stack[-1])
else:
stack.append(i)
return max_length
dp
Runtime：48 ms，快过 91.03%。
Memory：14.1 MB，低于 5.55%。
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s: return 0
dp = [0] * len(s)
for i in range(1, len(s)):
char = s[i]
if char == ')':
if s[i - 1] == '(':
# 满足条件，至少 + 2，如果'('前还有有效长度，继续加上
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
# 满足条件，符合 (())
# 如果 (()) 前还有()，继续加上
dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
return max(dp)
常量级空间复杂度
Runtime：68 ms，快过 16.94%。
Memory：13.9 MB，低于 16.67%。
class Solution:
def longestValidParentheses(self, s: str) -> int:
def traversal(iterator, reset_checker) -> int:
left, right, max_length = 0, 0, 0
for i in iterator:
char = s[i]
if char == '(':
left += 1
else:
right += 1
if left == right:
# 满足条件，配对成功
max_length = max(max_length, left + right)
if reset_checker(left, right):
left, right = 0, 0
return max_length
return max(
# 先从左往右
traversal(range(len(s)), lambda left, right: right > left),
# 再从右往左
traversal(range(len(s)-1, -1, -1), lambda left, right: left > right)
)
Review
What’s the Difference Between a Framework and Library? 一文读懂 Framework 和 Library 的区别。
以前端最流行的三大框架为例：Angular、Vue、React，摆事实讲道理列出了各自设计的优缺点，做一个总结。
你告诉 Library 要做什么；Framework 告诉你要做什么
Framework
以 Angular 和 Vue 为代表，它们提供了一个“最佳实践”，你只需要无脑跟即可。
优点
- 工具链齐全（组件、状态管理、路由等）
- 有官方的“最佳实践”，可以短时间内提高生产力
- 容易招聘，技能统一
- 清晰的演化路径
缺点
- 性能降低，如果你只需要一点点功能，仍然需要所有的代码
- 小项目不需要它，过于复杂
- 不容易定制，如果 Framework 不提供某个支持，你很难拓展
- 有一堆东西要学习
- 过于舒适，也可以认为是技术栈单一
Library
以 React 为代表，你可以控制一切。
优点
- 单一原则，React 只负责创建 UI，其他的像状态管理由 Redux 提供
- 容易控制
- 只增加你需要的功能，这很好理解，一个 Library 只做好一件事，拓展时只需要和其他的 Library 进行组合即可
- 学习很多其他的工具，换个视角看，你的技术栈比较全面
缺点
- 没有统一的架构
- 大量的技术选型，通常你需要花很多时间在工具相同的 Library 之间进行选择
- 仍然有一堆东西需要学习，无论是采用 Framework or Library，应用的体量、架构都会影响学习曲线
- 潜在的升级风险，如果每次更新都使你的 Library 之间出现兼容性问题，这就是灾难
Tip
CI、CD 的核心是“频繁”，如果代码合并容易出错，那就频繁合并，如果部署很蛋疼，那就频繁部署。
在提测流程中，影响效率的还有“速度”，想象一天产生 N 个测试包，你需要多少时间来消化？在保持“频繁”的前提下还需要提高“速度”，如改善自动化测试流程等。
我们公司也采用了一种“拓展”方案来提高“速度”，我们内部把它称为 dogfood - 吃自己的狗粮。
Share
思路清晰，全是干货，新(cai)手(niao)都看得懂！