713. Subarray Product Less Than K

sliding window

718. Maximum Length of Repeated Subarray

// dp[i][j] represents the max length of subarray starting from (i, j)
if (xs[i] == ys[j]) { dp[i][j] = 1 + dp[i + 1][j + 1]; }

首先看暴力的做法，时间复杂度为 O(n^3)

int ret = 0;
for (int i = 0; i < xs.size(); i += 1) {
    for (int j = 0; j < ys.size(); j += 1) {
        ret = max(ret, common_subarry(i, j));
    }
}

以 xs = [3, 6, 1, 2, 4], ys = [7, 1, 2, 9] 为例，它们的最长重复子数组是 [1, 2]，在 xs 与 ys 中的开始位置不同。

但如果我们知道了开始位置，我们就可以根据它们将 A 和 B 进行「对齐」，即

xs = [3, 6, 1, 2, 4]
ys =    [7, 1, 2, 9]
            ↑  ↑

此时，最长重复子数组在 A 和 B 中的开始位置相同，我们就可以对这两个数组进行一次遍历，得到子数组的长度，而两个数组的对齐方式个数是 O(n) 的，则总复杂度为 O(n^2)

int ret = 0;
for (int j = ys.size() - 1; j >= 0; j -= 1) {
    ret = max(ret, common_subarry(0, j));
}
for (int i = 0; i < xs.size(); i += 1) {
    ret = max(ret, common_subarry(i, 0));
}

722. Remove Comments

记录当前状态：line_no, line_pos, in_comment_block。再用一个数组 aceept_seq 记录应保留的字符 aceept_seq.push_back(sources[line_no][line_pos]). 在行末以及遇到 // 时推入 ret.push_back(aceept_seq)

用状态机的思路，每个字符作为输入（需要用到 followed_by

726. Number of Atoms

stack