linkedin onsite double check

32. Minimum Window Substring

30. Insert Interval

417. Valid Number

86. Binary Search Tree Iterator

1360. Symmetric Tree

934. Unlock Problem

932. Friends Within Three Jumps

1488. Longest Sequence

933. Tuple Multiply

650. Find Leaves of Binary Tree

645. Find the Celebrity(https://blog.csdn.net/magicbean2/article/details/74729767)


649. Binary Tree Upside Down

*836. Partition to K Equal Sum Subsets //优化，注意从大到小排序后的剪枝处理
（Partition Equal Subset Sum）//DP解法，背包问题
can I win

面经
1132. Valid Triangle Number

528. Flatten Nested List Iterator(stack的神奇使用) //queue也可以用

474. Lowest Common Ancestor II (parent节点)

max stack

private:
    list<int> v;
    map<int, vector<list<int>::iterator>> m;

All in O(1)

private:
    struct Bucket { int val; unordered_set<string> keys; };
    list<Bucket> buckets;
    unordered_map<string, list<Bucket>::iterator> m;

366 find leaves of binary tree
insert, delete, getrandom in O(1)

private:
    vector<int> nums;
    unordered_map<int, unordered_set<int>> m;

factor combination
merge intervals
HashMap
363. Trapping Rain Water
island number

Trie
LRU

int cap;
    list<pair<int, int>> l;
    unordered_map<int, list<pair<int, int>>::iterator> m;

LFU

int cap, minFreq;
    unordered_map<int, pair<int, int>> m;
    unordered_map<int, list<int>> freq;
    unordered_map<int, list<int>::iterator> iter;

罗马转整数

paint house I/II

int minCostII(vector<vector<int>>& costs) {
        if (costs.empty() || costs[0].empty()) return 0;
        vector<vector<int>> dp = costs;
        int min1 = -1, min2 = -1;
        for (int i = 0; i < dp.size(); ++i) {
            int last1 = min1, last2 = min2;
            min1 = -1; min2 = -1;
            for (int j = 0; j < dp[i].size(); ++j) {
                if (j != last1) {
                    dp[i][j] += last1 < 0 ? 0 : dp[i - 1][last1];
                } else {
                    dp[i][j] += last2 < 0 ? 0 : dp[i - 1][last2];
                }
                if (min1 < 0 || dp[i][j] < dp[i][min1]) {
                    min2 = min1; min1 = j;
                } else if (min2 < 0 || dp[i][j] < dp[i][min2]) {
                    min2 = j;
                }
            }
        }
        return dp.back()[min1];
    }

Nested list weight num I/II
II

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int res = 0;
        vector<int> v;
        for (auto a : nestedList) {
            helper(a, 0, v);
        }
        for (int i = v.size() - 1; i >= 0; --i) {
            res += v[i] * (v.size() - i);
        }
        return res;
    }
    void helper(NestedInteger ni, int depth, vector<int> &v) {
        if (depth >= v.size()) v.resize(depth + 1); //关键
        if (ni.isInteger()) {
            v[depth] += ni.getInteger();
        } else {
            for (auto a : ni.getList()) {
                helper(a, depth + 1, v);
            }
        }
    }
};

142. Linked List Cycle II

intersection-of-two-linked-lists 以及有环时的扩展。
https://blog.csdn.net/fengxinlinux/article/details/78885764

667. Longest Palindromic Subsequence

vs Longest Palindromic substring

vs 837. Palindromic Substrings找个数。一样的解法