LeetCode Solutions | 1 - 100

3. Longest Substring Without Repeating Characters

sliding window, instead of manually moving i to right each time, we can use a table to store the index the i will move to

5. Longest Palindromic Substring

dp[i][j] represents whether s[i..=j] can form a palindromic substring, dp[i][j] is true when s[i] equals to s[j] and s[i + 1..=j - 1] is a palindromic substring. When we found a palindrome, check if it's the longest one. Time complexity O(n^2).

for (let i = str.length - 1; i >= 0; i -= 1) {
    for (let j = i; j < str.length; j += 1) {
        // ...
        }
}

Manacher algorithm

15. 3Sum

sort to avoid duplicates; based on two sum

16. 3Sum Closest

sort & fix the left one, use two pointers to find the sum that minimizes the diff on the right part

17. Letter Combinations of a Phone Number

cartesian product + foldl

backtracking

22. Generate Parentheses

backtracking: chose left_paren or right_paren at curr
use left_cnt to cut branches

recursion based on n || dynamic programming

this approach will introduce duplicates

const prev = generateParenthesis(n - 1)
return [...prev.map(p => `()${p}`), ...prev.map(p => `${p}()`), ...prev.map(p => `(${p})`)]

better solution is divide the prev into two parts left and right

for (let i = 1; i <= n; i += 1) {
    for (let pairs_cnt_of_left = 0; pairs_cnt_of_left < i; pairs_cnt_of_left += 1) {
        for (const left_part of dp[pairs_cnt_of_left]) {
            for (const right_part of dp[i - 1 - pairs_cnt_of_left]) {
                dp[i].push(`(${left_part})${right_part}`)
            }
        }
    }
}

return dp[n]

23. Merge k Sorted Lists

merge lists one by one => merge with divide and conquer

heap with size k

25. Reverse Nodes in k-Group

const reverse = node => ... // do reverse in-place
const take = node => ... // take `k` nodes from node

// while `take` do `reverse`

26. Remove Duplicates from Sorted Array

two pointers, where to store, whats the current value, compare current value with last stored

31. Next Permutation

find the right_most peak

36. Valid Sudoku

the same with 348. Design Tic-Tac-Toe

38. count-and-say

just iterate

41. First Missing Positive

make an array, iterate through xs, mark array[x] as true, find the first index at which the value is false

O(1) space: move all elements within range to its right position, find the first index where the value is not right

the same with 448. Find All Numbers Disappeared in an Array

42. Trapping Rain Water

对每一个坑 heights[i]，应填充的水量为 cmp::max(0, cmp::min(ph, nh) - h) // cmp::min(ph, nh) 即为其两侧 bound 中较小的
用 DP 找到 max_height_from_left[] 与 max_height_from_right[]

注意到 max_height_from_left[] 和 max_height_from_right[] 中的每一个元素只用一次，尝试压缩

max_height_from_left 很容易，for i in 0..heights.len() 时实时更新即可，而 max_height_from_right[] 是从相反的方向构造的。所以这里我们也将 i 从两个方向逼近

let mut left = 0;
let mut max_before_left = 0;
let mut right = heights.len() - 1;
let mut max_after_right = 0;
while left <= right {
    // 说明 left 的小的那边的 bound 已经确定了
    if max_before_left <= max_after_right {
        if max_before_left > heights[left] {
            ret += max_before_left - heights[left];
        }
        max_before_left = cmp::max(max_before_left, heights[left]);
        left += 1;
    } else {
        if max_after_right > heights[right] {
            ret += max_after_right - heights[right];
        }
        max_after_right = cmp::max(max_after_right, heights[right]);
        right -= 1;
    }
}

monotonic stack: for every heights[i] find next_higher_or_equal[i] and prev_higher[i]

ret += (next_higher_or_equal[i] - prev_higher[i] - 1) * (cmp::min(heights[next_higher_or_equal[i]], heights[prev_higher[i]]) - heights[i])

next_higher_or_equal[] 保证了同一水坑的同一高度的行仅会计算一次

monotonic stack

// monotonic decreasing stack, which means that the current bar is bounded by the previous bar in the stack.
let mut stack = vec![];
for (i, h) in heights.into_iter().enumerate().skip_while(|&(_, h)| h == 0) {
    while let Some(&(ph, pi)) = stack.last() {
        if ph <= h {
            stack.pop();
            // 每次 pop 的时候相当于把区间内的坑填到了和 cmp::min(left_bound, h) 的高度
            if let Some(&(lbh, li)) = stack.last() {
                ret += (cmp::min(lbh, h) - ph) * (i - li - 1) as i32;
            }
        } else {
            break;
        }
    }
    stack.push((h, i));
}

46. Permutations

const curr: number[] = []
const selected: boolean[] = new Array(nums.length).fill(false)
const f = () => {
    if (curr.length == nums.length) {
        ret.push([...curr])
        return
    }

    for (let i = 0; i < nums.length; i += 1) {
        if (selected[i]) continue

        selected[i] = true
        curr.push(nums[i])
        f()
        curr.pop()
        selected[i] = false
    }
}

function<void(int)> backtrack = [&](int from) {
    if (from == nums.size()) {
        ret.push_back(vector<int>(nums));
        return;
    }

    for (int curr = from; curr < nums.size(); curr += 1) {
        swap(nums[from], nums[curr]);
        backtrack(from + 1);
        swap(nums[from], nums[curr]);
    }
};

47. Permutations II

nums.sort((a, b) => a - b)

const curr: number[] = []
const selected: boolean[] = new Array(nums.length).fill(false)
const f = () => {
    if (curr.length == nums.length) {
        ret.push([...curr])
        return
    }

    for (let i = 0; i < nums.length; i += 1) {
        if (selected[i] || (nums[i] == nums[i - 1] && !selected[i - 1])) continue

        selected[i] = true
        curr.push(nums[i])
        f()
        curr.pop()
        selected[i] = false
    }
}

fn backtracking(nums: &mut [i32], pos: usize, ret: &mut Vec<Vec<i32>>) {
    if pos == nums.len() {
        ret.push(Vec::from(nums));
        return;
    }

    let mut selection = pos;
    let mut selected = HashSet::new();
    while selection < nums.len() {
        if selected.contains(&nums[selection]) {
            selection += 1
        } else {
            nums.swap(pos, selection);
            backtracking(nums, pos + 1, ret);
            nums.swap(pos, selection);

            selected.insert(nums[selection]);
            selection += 1;
        }
    }
}

45. Jump Game II

calc min steps from tail to head
bfs, use a curr and prev furthest value to indicating current level

48. Rotate Image

49. Group Anagrams

其实就是按照字符串中每个元素出现的个数分类，可以用一个长度位 26 的数组作为 key，遍历字符串的时候 arr[c] += 1，相同 key 对应的字符串就应该被归类在一起

如果个数只有 0，或者一，26 位的数组就可以用 26bit 的二进制数优化

如果空间有限的话，可以把每个 char 对应到一个素数，key = \prod primes

53. Maximum Subarray

一眼看上去就很像标准的 sliding window 问题，设立 i，j 两个指针表示范围。当范围内的和为正的时候表示这段距离还有价值，保留，增加 j。当范围内的和为负的时候，不如舍弃这一段让 i=j，sum 从零开始

仔细观察发现，其实 i 没有实际意义，可以只用 j，四舍五入就是直接遍历数组就行了，sum = max(0, sum)，每次 sum 取 0 就代表舍弃了前面的那段

let ret = -Infinity
let curr = 0
for (let i = 0; i < nums.length; i += 1) {
    curr = Math.max(curr + nums[i], nums[i])
    ret = Math.max(ret, curr)
}

f i j = max left_sum cross_sum right_sum
    where left_sum = f i (m - 1)
          cross_sum = max $ subarray (contains m)
          right_sum = f (m + 1) j

54. Spiral Matrix

simulate the walking path

layer by layer

55. Jump Game

memorized recursion or dp

check from the back, if the final lastpos that can reach the end(or the prev lastpos) equals to zero, then return true

56. Merge Intervals

sort then merge using a stack

57. Insert Interval

use binary search to find when to merge the new interval

59. Spiral Matrix II

simulate the walking path

layer by layer

60. Permutation Sequence

based on next_permutation

对于 selections[]，根据 k % factorial(selections.length - 1) 判断当前位应该选择 selections 中第几大的。递归以上步骤

71. Simplify Path

use an array, . makes no change, .. decrease length by one

72. Edit Distance

dp (insertion is equal to deletion

73. Set Matrix Zeroes

use two arrays to indicate elemen ts on which rows and cols should be set 0

instead of using two arrays, use the first element on the row and col

78. Subsets

backtracking a tree-like structure

external link

79. Word Search

check neighbors with a visited hash or making a mark on the board

80. Remove Duplicates from Sorted Array II

two pointers, next position to check and next position to store, compare next value with last 2 stored value

82. Remove Duplicates from Sorted List II

continuing check to following values to determine if its acceptable

83. Remove Duplicates from Sorted List

inplace, check curr with last

another list to store, check last stored value with curr value

84. Largest Rectangle in Histogram

use monotonic stack to calc prev_smaller[] and next_smaller[]

let ret = -Infinity
for (let i = 0; i < heights.length; i += 1) {
    ret = Math.max(ret, heights[i] * (next_smaller[i] - prev_smaller[i] - 1))
}

return ret

85. Maximal Rectangle

calc heights[][] for every points using dp
for every row, its the same with 84. Largest Rectangle in Histogram

86. Partition List

two list

87. Scramble String

memoized recursion || dp

const f = (xi: number, xj: number, yi: number, yj: number): boolean

can be optimized into

const f = (xi: number, yi: number, length: number): boolean

89. Gray Code

trash problem, dont do it remember how to get/set the bit number at specified position is enough

90. Subsets II

use a hash set to get the count of every number, recursion on unique numbers, decide how many are selected

instead of recursion, iter, get result from prev decided expr

93. Restore IP Addresses

just do it

95. Unique Binary Search Trees II

recursion (kinda like brute force