LeetCode Notebook

142 Linked List Cycle II

关于空间 O(1) 解法：

• 初始创建两个指向 head 的节点指针 A 和 B，每一次令 A 为其后继（前进 1 步），B 为其后继的后继（前进 2 步），重复直到 A 和 B 指向同一节点，此时二者的步数差为 cycle 长度的倍数，同时也是 A 走过的步数。

• 将 B 再次初始化为 head，维持 A 不变。每次令 A 前进 1 步，B 前进 1 步，重复直到 A 和 B 指向同一节点。显然当 B 走到 cycle 中的第一个节点时，A 因比 B 多走了 cycle 长度倍数的步数，而将和 B 指向同一节点；在此之前，A 必指向 cycle 中的节点，B 必指向不在 cycle 中的节点。综上，当 A 和 B 第一次指向同一节点，该节点就是 cycle 中的第一个节点。

• 相关：BSGS

32 Longest Valid Parentheses

DP 解法：

• 考虑每个前缀子串的最长合法括号序列后缀子串的长度。对长为 n 的前缀子串，记其本身为 p(n)，其最长合法括号序列后缀子串为 s(n)，长度为 f(n)。考虑 p(n) 结尾的括号 c。

  • 若 c 是左括号，s(n) 只能是空串。

  • 若 c 是右括号，考虑 s(n-1) 前的括号 c'。

    • 若 c' 是一个左括号，则可以和 c 配对，得到一个合法括号序列 s0。进而考虑 c' 左侧的后缀 p(n-1-f(n-1)-1)，其拥有的最优后缀 s(n-1-f(n-1)-1) 可以和 s0 共同构成 s(n)。于是 f(n) = 1+f(n-1)+1+f(n-1-f(n-1)-1)。

    • 若 c' 是一个右括号，则 s(n) 为空串。假如 s(n) 非空，就意味着在 c' 左侧还有一个左括号 c'' 与 c 配对，进而 c'' 与c 之间的子串构成一个比 s(n-1) 更长的合法括号序列，与 s(n-1) 的性质矛盾。

• 综上可以写出关于 f(n) 的状态转移方程。最后选取一个最大的 f(n) 即可。