300. Longest Increasing Subsequence

memoized recursion | dp

最基本的，我们有两种状态的定义方式:

• dp[curr][prev] 表示上一个数是 prev 的情况下，从 curr.. 的区间内的最大长度 （应该也是 O(n^2) 的复杂度，但是 TLE 了，可能常数太大

fn f(nums: &[i32], curr: usize, prev: i32) -> i32 {
    if curr == nums.len() { return 0; }

    let mut ret = 0;
    if nums[curr] > prev {
        ret = ret.max(1 + f(nums, curr + 1, nums[curr]));
    }
    ret = ret.max(f(nums, curr + 1, prev));

    ret
}

• dp[curr] 表示以 nums[curr] 为开头的子序列的最大长度

fn f(nums: &[i32], curr: usize) -> i32 {
    if curr == nums.len() { return 0; }

    let mut res = 1;
    for right in curr + 1..nums.len() {
        if nums[right] > nums[curr] {
            res = res.max(1 + f(nums, right));
        }
    }

    res
}

还有一种比较 tricky 的定义是 minimum_ending_with[len] 表示长度为 len 的子序列的最小结尾，minimum_ending_with[0] 初始化为 INT_MIN，其它的初始化为 INT_MAX。显然 minimum_ending_with[] 是递增的

for (int i = 0; i < nums.size(); i += 1) {
    // 将 `nums[i]` 接到仅可能长的子序列后面
    // 当前已确定的长度最大可能为 `i`，所以 `right_bound` 是 `i`
    int prev_len = greatest_smaller(0, i, nums[i]);
    // prev_len 是尾元素小于 `nums[i]` 的最大长度
    assert(prev_len != -1);

    minimum_ending_with[prev_len + 1] =
        min(minimum_ending_with[prev_len + 1], nums[i]);
    ret = max(ret, prev_len + 1);
}

307. Range Sum Query - Mutable

segment tree

312. Burst Balloons

memoized recursion / dp

每次戳破一个气球，会导致两个气球从不相邻变成相邻，使得后续操作难以处理。

反向思考，考虑逆过程，每次添加一个气球得到的分数根据其在原数组中的位置是确定的

const f = (i: number, j: number): number => {
    if (i > j) return 0

    let ret = 0
    const partial_gain = (i > 0 ? nums[i - 1] : 1) * (j < nums.length - 1 ? nums[j + 1] : 1)
    for (let k = i; k <= j; k += 1) {
        ret = Math.max(ret, partial_gain * nums[k] + f(i, k - 1) + f(k + 1, j))
    }
    return ret
}

315. Count of Smaller Numbers After Self

利用归并排序 (decreasing)，每次合并的时候计算右边部分能贡献多少逆序对.

let xi = 0
let yi = 0
while (xi < xs.length && yi < ys.length) {
    // 选择 `xs[xi]` 意味着，ys 中还剩下 `ys.length - yi` 个小于 `xs[xi]` 的数
    // because `ys` is decreasing
    if (xs[xi][0] > ys[yi][0]) {
        ret[xs[xi][1]] += ys.length - yi
        zs.push(xs[xi])
        xi += 1
    } else {
        zs.push(ys[yi])
        yi += 1
    }
}

322. Coin Change

memorized recursion or dp

325. Maximum Size Subarray Sum Equals k

very much like Two Sum

326. power-of-three

binary search

let a be the biggest number which is the power of 3 within int, then a % n == 0

change base, only the most significant position is not 0.

340. Longest Substring with At Most K Distinct Characters

sliding window

can be optimized: instead of doing i += 1 repeatedly, remember where to jump

341. Flatten Nested List Iterator

flatten it in the constructor (I guess we can use call/cc to pause the recursion so we can lazy flatten it? I will check this when I fully master cps)

manually maintain a stack, in this way, each time we call next(), we execute one

342. Power of Four

bit mask, every two position - if num is a power of two: x > 0 and x & (x - 1) == 0 - num & (101010...10)_2 == 0

347. Top K Frequent Elements

heap

count occurrence using a hash map, and then store them in an array using occurrence as the index, [element] as value, take first k element from the right side of the array

348. Design Tic-Tac-Toe

maintain tow arrays and two variables for rows, cols, diagonal and anti-diagonal indicating they belong to whom or in mixed-status

349. Intersection of Two Arrays{href=https://leetcode.com/problems/intersection-of-two-arrays/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china .nav}

sort two arrays, then merge

sort one array, binary search (use set to avoid duplicates

two sets

393. UTF-8 Validation

do it using bitmask

394. Decode String

use stack to extract strings and counts

parsec