Mind palace

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

Posted on 2021-01-09 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

O(mklog(min(n, k))) time O(min(n, k)) space
373. Find K Pairs with Smallest Sums的followup
不要想复杂了！！！直接做m - 1遍就行了
利用这种原理还可以做并行的两两merge

class Solution {
    vector<int> kSmallestPairs(const vector<int>& nums1, const vector<int>& nums2, int k) {
        if (nums1.empty() || nums2.empty() || k == 0) return {};
        using pii = pair<int, int>;
        auto cmp = [&nums1, &nums2](const pii &a, const pii &b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second]; };
        priority_queue<pii, vector<pii>, decltype(cmp)> q(cmp);
        int m = nums1.size(), n = nums2.size();
        for (int j = 0, sz = min(k, n); j < sz; ++j) {
            q.emplace(0, j);
        }
        vector<int> res;
        while (k-- > 0 && !q.empty()) {
            auto [i, j] = q.top(); q.pop();
            res.push_back(nums1[i] + nums2[j]);
            if (i + 1 < m) {
                q.emplace(i + 1, j);
            }
        }
        return res;
    }
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = min((int)mat[0].size(), k);
        vector<int> v(begin(mat[0]), begin(mat[0]) + n);
        for (int r = 1; r < m; ++r) {
            v = kSmallestPairs(v, mat[r], k);
        }
        return v.back();
    }
};

并行merge版
跟23. Merge k Sorted Lists思路一样

class Solution {
    vector<int> kSmallestPairs(const vector<int>& nums1, const vector<int>& nums2, int k) {
        if (k == 0) return {};
        if (nums1.empty()) return nums2;
        if (nums2.empty()) return nums1;
        using pii = pair<int, int>;
        auto cmp = [&nums1, &nums2](const pii &a, const pii &b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second]; };
        priority_queue<pii, vector<pii>, decltype(cmp)> q(cmp);
        int m = nums1.size(), n = nums2.size();
        for (int j = 0, sz = min(k, n); j < sz; ++j) {
            q.emplace(0, j);
        }
        vector<int> res;
        while (k-- > 0 && !q.empty()) {
            auto [i, j] = q.top(); q.pop();
            res.push_back(nums1[i] + nums2[j]);
            if (i + 1 < m) {
                q.emplace(i + 1, j);
            }
        }
        return res;
    }
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int m = size(mat);
        for (int step = 1; step < m; step <<= 1) {
            for (int i = 0; i + step < m; i += (step << 1)) {
                mat[i] = kSmallestPairs(mat[i], mat[i + step], k);
            }
        }
        return mat[0].back();
    }
};

1424. Diagonal Traverse II

Posted on 2021-01-09 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 553 Reading time ≈ 1 mins.

O(C) time O(log(max(m, n))) space
当一个binary tree来level order traverse

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q{{{0, 0}}};
        vector<int> res;
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            res.push_back(nums[r][c]);
            if (r + 1 < nums.size() && c == 0) { // 因为每一行都非空，所以只有第一个需要添加左子，剩下的统一添加右子即可去重
                q.emplace(r + 1, c);
            }
            if (c + 1 < nums[r].size()) {
                q.emplace(r, c + 1);
            }
        }
        return res;
    }
};

109. Convert Sorted List to Binary Search Tree

Posted on 2021-01-09 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 2.5k Reading time ≈ 2 mins.

O(n) time O(logn) space
采用中序遍历思想，先确定链表长度，然后二分递归进行中序遍历
是108. Convert Sorted Array to Binary Search Tree的升级版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        this->head = head;
        int n = 0;
        for (auto p = head; p; p = p->next) {
            ++n;
        }
        return dfs(0, n);
    }

    TreeNode *dfs(int b, int e) {
        if (b == e) return nullptr;
        int m = b + (e - b) / 2;
        auto l = dfs(b, m);
        auto res = new TreeNode(head->val);
        head = head->next;
        res->left = l;
        res->right = dfs(m + 1, e);
        return res;
    }

    ListNode *head;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        node = head;
        int n = 0;
        for (auto x = head; x; x = x->next) {
            ++n;
        }
        return inorder(0, n - 1);
    }

    TreeNode *inorder(int l, int r) {
        if (l > r) return nullptr;
        int m = l + (r - l) / 2;
        auto left = inorder(l, m - 1); // 采用双闭区间
        auto res = new TreeNode(node->val); // 这一步一定要后于左半边递归，因为node此时并非真正的root，等左半边遍历过以后，node才是root
        node = node->next;
        res->left = left;
        res->right = inorder(m + 1, r);
        return res;
    }

    ListNode *node;
};

O(nlogn) time O(logn) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);
        ListNode dummy_head(0), *slow = &dummy_head, *fast = head;
        dummy_head.next = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto root = slow->next;
        auto res = new TreeNode(root->val);
        slow->next = nullptr;
        res->left = sortedListToBST(head);
        res->right = sortedListToBST(root->next);
        return res;
    }
};

1382. Balance a Binary Search Tree

Posted on 2021-01-09 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

O(n) time O(n) space
先dfs扫一遍得到所有的node然后二分构造bst

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        dfs(root);
        return reconstruct(0, nodes.size());
    }

    void dfs(TreeNode *root) {
        if (!root) return;
        dfs(root->left);
        root->left = nullptr;
        nodes.push_back(root);
        auto r = root->right;
        root->right = nullptr;
        dfs(r);
    }

    TreeNode *reconstruct(int b, int e) {
        if (b == e) return nullptr;
        int m = (b + e) / 2;
        auto res = nodes[m];
        res->left = reconstruct(b, m);
        res->right = reconstruct(m + 1, e);
        return res;
    }

    vector<TreeNode *> nodes;
};

DSW O(n) time O(1) space
解法
先通过多次右旋变成right-skew的单链，再按照树高（以及子树高）多次左旋

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int makeVine(TreeNode *grand, int cnt = 0) {
      auto n = grand->right;
      while (n != nullptr) {
        if (n->left != nullptr) {
          auto old_n = n;
          n = n->left;
          old_n->left = n->right;
          n->right = old_n;
          grand->right = n;
        }
        else {
            ++cnt;
            grand = n;
            n = n->right;
        }
      }
      return cnt;
    }
    void compress(TreeNode *grand, int m) {
      auto n = grand->right;
      while (m-- > 0) {
        auto old_n = n;
        n = n->right;
        grand->right = n;
        old_n->right = n->left;
        n->left = old_n;
        grand = n;
        n = n->right;
      }
    }
    TreeNode* balanceBST(TreeNode *root) {
      TreeNode grand;
      grand.right = root;
      auto cnt = makeVine(&grand);
      int m = pow(2, int(log2(cnt + 1))) - 1;
      compress(&grand, cnt - m);
      for (m = m / 2; m > 0; m /= 2)
        compress(&grand, m);
      return grand.right;
    }
};

647. Palindromic Substrings

Posted on 2021-01-09 Edited on 2021-02-11 In LeetCode Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(n) manacher’s algorithm不会
brute force O(n²) time O(1) space
跟5. Longest Palindromic Substring一样，直接数数即可

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += helper(s, i, i);
            cnt += helper(s, i, i + 1);
        }
        return cnt;
    }

    int helper(const string &s, int l, int r) {
        int cnt = 0;
        for (int n = size(s); l >= 0 && r < n && s[l] == s[r]; ++cnt, --l, ++r);
        return cnt;
    }
};

划分型dp O(n²) time O(n²) space
isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1]
f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + isPalin[i][j]

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n));
        vector<vector<bool>> isPalin(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
            f[i][i + 1] = 2 + isPalin[i][i + 1];
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                isPalin[i][j] = (s[i] == s[j] && isPalin[i + 1][j - 1]);
                f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + isPalin[i][j];
            }
        }
        return f[0][n - 1];
    }
};

其实没有必要维护一个计数的矩阵，直接用一个cnt就可以了

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<bool>> isPalin(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        int cnt = n;
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
            cnt += isPalin[i][i + 1];
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                isPalin[i][j] = (s[i] == s[j] && isPalin[i + 1][j - 1]);
                cnt += isPalin[i][j];
            }
        }
        return cnt;
    }
};

329. Longest Increasing Path in a Matrix

Posted on 2021-01-09 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 738 Reading time ≈ 1 mins.

dfs + memo O(mn) time O(mn) space

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = size(matrix), n = size(matrix[0]);
        int res = 0;
        f.resize(m, vector<int>(n));
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                res = max(res, dfs(matrix, r, c, -1));
            }
        }
        return res;
    }

    int dfs(vector<vector<int>> &A, int r, int c, int prev) {
        if (r < 0 || r >= m || c < 0 || c >= n || A[r][c] <= prev) return 0;
        if (f[r][c] > 0) return f[r][c];
        int res = 1;
        for (int i = 0; i < 4; ++i) {
            res = max(res, dfs(A, r + dr[i], c + dc[i], A[r][c]) + 1);
        }
        return f[r][c] = res;
    }

    int m, n, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    vector<vector<int>> f;
};

114. Flatten Binary Tree to Linked List

Posted on 2021-01-08 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        helper(root);
    }

    TreeNode *helper(TreeNode *root) { // 返回flatten之后的最后一个结点
        if (!root) return root;
        auto l = helper(root->left); // 要保证l和r至少有一个不为空
        auto r = helper(root->right);
        if (l) { // 如果l不为空，root->right要接到l右边
            l->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
        return r ? r : l ? l : root; // 如果r也不为空，返回r，如果l不为空，返回l，否则返回root
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        flatten_helper(root);
    }

private:
    TreeNode *flatten_helper(TreeNode *root) {
        if (!root || !root->left && !root->right)
            return root;
        auto left_last(flatten_helper(root->left));
        if (left_last) {
            left_last->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
        return left_last ? flatten_helper(left_last) : flatten_helper(root->right);
    }
};

341. Flatten Nested List Iterator

Posted on 2021-01-08 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 4k Reading time ≈ 4 mins.

amortized O(1)
stack类似BST iterator

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        s.assign(rbegin(nestedList), rend(nestedList));
    }

    int next() {
        int res = s.back().getInteger();
        s.pop_back(); // 别忘了pop
        return res;
    }

    bool hasNext() {
        while (!s.empty() && !s.back().isInteger()) {
            auto lst = s.back().getList();
            s.pop_back();
            s.insert(end(s), rbegin(lst), rend(lst));
        }
        return !s.empty();
    }

    vector<NestedInteger> s;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (auto rit = nestedList.rbegin(); rit != nestedList.rend(); ++rit) {
            s.push(*rit);
        }
    }

    int next() {
        auto res = s.top().getInteger();
        s.pop();
        return res;
    }

    bool hasNext() {
        while (!s.empty() && !s.top().isInteger()) {
            auto lst = s.top().getList();
            s.pop();
            for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
                s.push(*rit);
            }
        }
        return !s.empty();
    }

    stack<NestedInteger> s;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

iterator版

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        s.emplace(begin(nestedList), end(nestedList));
    }

    int next() {
        int res = s.top().first->getInteger();
        s.top().first++;
        return res;
    }

    bool hasNext() {
        while (!s.empty()) {
            auto &[b, e] = s.top();
            if (b == e) {
                s.pop();
            } else if (!b->isInteger()) {
                s.emplace(begin(b->getList()), end(b->getList()));
                ++b;
            } else break;
        }
        return !s.empty();
    }

    using vnii = vector<NestedInteger>::iterator;
    stack<pair<vnii, vnii>> s;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

515. Find Largest Value in Each Tree Row

Posted on 2021-01-08 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 814 Reading time ≈ 1 mins.

O(n) BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            int v = INT_MIN;
            for (int i = q.size(); i > 0; --i) {
                auto x = q.front(); q.pop();
                v = max(v, x->val);
                if (x->left) {
                    q.push(x->left);
                }
                if (x->right) {
                    q.push(x->right);
                }
            }
            res.push_back(v);
        }
        return res;
    }
};

1209. Remove All Adjacent Duplicates in String II

Posted on 2021-01-08 Edited on 2021-01-25 In LeetCode Disqus:
Symbols count in article: 801 Reading time ≈ 1 mins.

stack O(n) time O(n) space
维护一个<字符+频数>的stack 累计连续频数每次连续频数达到k就出栈最后把所有字符按频数拼接即可

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> stk;
        for (char c : s) {
            if (stk.empty() || stk.back().first != c) {
                stk.emplace_back(c, 1);
            } else if (++stk.back().second == k) {
                stk.pop_back();
            }
        }
        string res;
        for (auto [c, n] : stk) {
            res.append(n, c);
        }
        return res;
    }
};

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> stk;
        for (char c : s) {
            if (stk.empty() || stk.back().first != c) {
                stk.emplace_back(c, 0);
            }
            if (++stk.back().second == k) {
                stk.pop_back();
            }
        }
        string res;
        for (auto [c, n] : stk) {
            res.append(n, c);
        }
        return res;
    }
};