Mind palace

325. Maximum Size Subarray Sum Equals k

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

O(n) time

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> m{{0, -1}}; // 注意要初始化0的下标为-1
        int n = nums.size();
        int res = 0;
        for (int i = 0, sum = 0; i < n; ++i) {
            sum += nums[i];
            int t = sum - k;
            if (m.count(t)) {
                res = max(res, i - m[t]);
            }
            m[sum] = m.count(sum) ? m[sum] : i;
        }
        return res;
    }
};

O(n) time O(n) space

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1);
        unordered_map<int, int> m{{0, 0}};
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
            m[presum[i]] = max(m[presum[i]], i);
        }
        int res = 0;
        for (int i = 0; i <= n; ++i) {
            int t = presum[i] + k;
            if (m.count(t)) {
                res = max(res, m[t] - i);
            }
        }
        return res;
    }
};

286. Walls and Gates

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

bfs O(mn) time O(mn) space

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty() || rooms[0].empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int j = 0; j < 4; ++j) {
                int rr = r + dr[j], cc = c + dc[j];
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || rooms[rr][cc] != INT_MAX) continue;
                q.emplace(rr, cc);
                rooms[rr][cc] = rooms[r][c] + 1; // 提前修改可以避免后期处理的麻烦
            }
        }
    }
};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty() || rooms[0].empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        int dist = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto [r, c] = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int rr = r + dr[j], cc = c + dc[j];
                    if (rr < 0 || rr >= m || cc < 0 || cc >= n || rooms[rr][cc] != INT_MAX) continue;
                    q.emplace(rr, cc);
                    rooms[rr][cc] = dist; // 一定要提前修改
                }
            }
            ++dist;
        }
    }
};

567. Permutation in String

Posted on 2021-01-13 Edited on 2021-01-26 In LeetCode Disqus:
Symbols count in article: 2.8k Reading time ≈ 3 mins.

sliding window O(n) time O(1) space
维护定长sliding window和一个cnt，cnt表示当前sliding window内符合要求的字符的个数，只有当cnt为m即sliding window的长度时，说明所有字符都是符合要求的，则找到了一个permutation

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = size(s1), n = size(s2);
        if (m > n) return false;
        int f[26] = {0};
        for (char c : s1) {
            ++f[c - 'a'];
        }
        for (int cnt = 0, i = 0; i < n; ++i) {
            if (--f[s2[i] - 'a'] >= 0) {
                ++cnt;
            }
            if (i >= m && ++f[s2[i - m] - 'a'] > 0) {
                --cnt;
            }
            if (cnt == m) return true;
        }
        return false;
    }
};

1053. Previous Permutation With One Swap

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

O(n) time
相当于找prev_permutation，要在右边找一个小数换左边的一个大数，右边的小数要在尾部的升序序列里找
312右侧升序，从后往前找到第一个违反升序的31，再在升序序列里找『第一个』比3小的最大的数，也就是先找3的下界再往前找第一次出现的最大的数跟3交换即可

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = size(A), i = n - 1;
        while (i > 0 && A[i - 1] <= A[i]) --i;
        if (i == 0) return A;
        int j = lower_bound(begin(A) + i, end(A), A[i - 1]) - begin(A) - 1;
        j = lower_bound(begin(A) + i, begin(A) + j + 1, A[j]) - begin(A);
        swap(A[i - 1], A[j]);
        return A;
    }
};

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size(), x = n;
        for (int i = n - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                x = i; // 先从后往前找到第一个违反递减关系的数A[x]
                break;
            }
        }
        if (x == n) return A;
        int y = lower_bound(begin(A) + x + 1, end(A), A[x]) - begin(A) - 1; // 从后往前二分找到第一个小于A[x]的数A[y]
        y = lower_bound(begin(A) + x + 1, begin(A) + y + 1, A[y]) - begin(A); // 再找到第一个A[y]跟A[x]交换
        swap(A[x], A[y]);
        return A;
    }
};

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size(), x = n;
        for (int i = n - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                x = i;
                break;
            }
        }
        if (x == n) return A;
        auto y = lower_bound(begin(A) + x + 1, end(A), A[x]) - begin(A) - 1;
        while (x < y && A[y - 1] == A[y]) {
            --y;
        }
        swap(A[x], A[y]);
        return A;
    }
};

288. Unique Word Abbreviation

Posted on 2021-01-13 Edited on 2021-01-26 In LeetCode Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n) time O(n) space
纯粹考对题目理解和corner case想的全不全
题目isunique的定义：

词典里没有这个词的缩写
词典里有这个词的缩写，原词都是这个词（意味着词典里如果有缩写相同的词，则必须相同且只能是这个词，即不能有歧义，同一个缩写只能对应唯一的词）

需要考虑的corner case：

词典里有重复词
词典里有缩写一样的不同词

为了节省空间，用一个hashmap，key是缩写，value存该缩写的唯一的这个词，如果词典里有重复词则跳过，如果词典里有缩写一样的不同词则把value置空

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string>& dictionary) {
        for (const auto &w : dictionary) {
            const auto &a = norm(w);
            if (m.count(a) == 0) { // 如果不存在这个词的缩写
                m[a] = w;
            } else if (!m[a].empty() && m[a] != w) { // 如果词典里有缩写一样的不同词
                m[a].clear();
            }
        }
    }

    bool isUnique(string word) {
        const auto a = norm(word);
        return m.count(a) == 0 || m[a] == word; // 如果找不到该词的缩写或者能找到该词的缩写且是同一个词的缩写，则是unique的
    }

    string norm(const string &w) {
        if (w.length() < 3) return w;
        string res(1, w[0]);
        res += to_string(w.length() - 2);
        res += w.back();
        return res;
    }

    unordered_map<string, string> m;
};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
 * bool param_1 = obj->isUnique(word);
 */

416. Partition Equal Subset Sum

Posted on 2021-01-12 Edited on 2021-01-26 In LeetCode Disqus:
Symbols count in article: 758 Reading time ≈ 1 mins.

solution
O(n)
bitset的第i位表示数i能不能通过若干个数组成，通过左移+或可以求出所有可能的和，左移相当于在利用之前所有数得到的所有可能的和的基础上再加上当前这个数，为了不丢失之前的结果还需要或上之前的所有可能的和

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        sum >>= 1;
        bitset<10001> sums(1); // 这里10001够了，因为累加和的一半不会超过10001
        for (int num : nums) {
            sums |= (sums << num);
        }
        return sums[sum];
    }
};

knapsack O(n * sum/2)

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = accumulate(begin(nums), end(nums), 0);
        if (s & 1) return false;
        s >>= 1;
        vector<int> f(s + 1);
        f[0] = true;
        for (int x : nums) {
            for (int t = s; t >= x; --t) {
                f[t] = f[t] || f[t - x];
            }
        }
        return f[s];
    }
};

332. Reconstruct Itinerary

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

基于dfs的类拓扑排序（不是真的拓扑排序） O(n) time O(n) space
后序遍历，当一个节点的所有子节点都被遍历过之后，将该节点加入，因为是倒序，所有最后要翻转过来，因为是类似拓扑排序，所以出度为0的末端点（最多一个）即便最先被访问也是第一个入栈，要排在最后
如果没有出度为0的点，前序遍历也是可以的，但是出度为0的点没有子节点所以必须最后访问，只有栈+后序遍历才能做到

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.empty()) return {};
        for (const auto &e : tickets) {
            g[e[0]].insert(e[1]);
        }
        dfs("JFK");
        return vector<string>(rbegin(res), rend(res));
    }

    void dfs(const string &u) {
        while (!g[u].empty()) {
            auto it = begin(g[u]);
            auto v = *it;
            g[u].erase(it); // 删除以避免重复访问
            dfs(v);
        }
        res.push_back(u);
    }

    vector<string> res;
    unordered_map<string, multiset<string>> g; // 因为需要字典序所以要用set，因为一个起点可以多次去一个中点所以要用multiset
};

257. Binary Tree Paths

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

postorder

/**
 * 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:
    vector<string> binaryTreePaths(TreeNode* root) {
        if (!root) return {};
        auto val = to_string(root->val);
        if (!root->left && !root->right) return {val};
        vector<string> res;
        for (auto &&str : binaryTreePaths(root->left)) {
            res.push_back(val + "->" + str);
        }
        for (auto &&str : binaryTreePaths(root->right)) {
            res.push_back(val + "->" + str);
        }
        return res;
    }
};

54. Spiral Matrix

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

O(mn) time O(mn) space

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0}, m = matrix.size(), n = matrix[0].size(), sz = m * n;
        vector<int> res;
        vector<vector<bool>> v(m, vector<bool>(n));
        int r = 0, c = 0, i = 0;
        while (sz-- > 0) {
            res.push_back(matrix[r][c]);
            v[r][c] = true;
            r += dr[i];
            c += dc[i];
            if (r < 0 || r >= m || c < 0 || c >= n || v[r][c]) {
                r -= dr[i];
                c -= dc[i];
                i = (i + 1) % 4;
                r += dr[i];
                c += dc[i];
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), sz = m * n;
        vector<bool> visited(sz);
        vector<int> res;
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0}; // 按右下左上的顺序
        for (int i = 0, r = 0, c = 0, j = 0; i < sz; ++i) {
            if (0 <= r && r < m && 0 <= c && c < n && !visited[r * n + c]) {
                res.push_back(matrix[r][c]);
                visited[r * n + c] = true;
            } else { // 如果越界
                r -= dr[j]; // 回退
                c -= dc[j];
                --i;
                j = (j + 1) % 4; // 换向
            }
            r += dr[j]; // 尝试前进一步
            c += dc[j];
        }
        return res;
    }
};

O(1) space

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        enum D {N, E, W, S};
        int dx[] = {0, 1, -1, 0}, dy[] = {-1, 0, 0, 1};
        int n = matrix.size(), m = matrix[0].size();
        int size = n * m;
        D d = E;
        vector<int> res;
        for (int i = 0, row = 0, col = 0, t = -1, b = n, l = -1, r = m; i < size; ++i) { // 用tblr来标记当前的上下左右的bound
            res.push_back(matrix[row][col]);
            switch (d) {
                case N: if (row + dy[d] == t) { d = E; ++l; } break;
                case E: if (col + dx[d] == r) { d = S; ++t; } break;
                case W: if (col + dx[d] == l) { d = N; --b; } break;
                case S: if (row + dy[d] == b) { d = W; --r; } break;
                default: break;
            }
            row += dy[d];
            col += dx[d];
        }
        return res;
    }
};

1329. Sort the Matrix Diagonally

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

heap O((m+n)max(m, n)log(max(m, n))) time O(mn) space
从右上到左下r - c的差递增，从左上往右下扫描，根据差值存入对应的heap，再扫描一遍取出来即可

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, priority_queue<int, vector<int>, greater<>>> hm;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                hm[r - c].push(mat[r][c]);
            }
        }
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                mat[r][c] = hm[r - c].top();
                hm[r - c].pop();
            }
        }
        return mat;
    }
};

O((m+n)max(m, n)log(max(m, n))) time O(max(m, n)) space
这个方法节省空间，但算边界比较麻烦，外层循环根据r - c的差值递增，内层循环根据r递增，d = r - c，因为0 <= c = r - d <= n - 1所以d <= r <= n - 1 + d并且0 <= r <= m - 1，所以max(d, 0) <= r <= min(m - 1, n - 1 + d)

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int d = 1 - n; d <= m - 1; ++d) {
            vector<int> v;
            for (int r = max(d, 0); r <= min(m - 1, n - 1 + d); ++r) {
                v.push_back(mat[r][r - d]);
            }
            sort(begin(v), end(v), greater());
            for (int r = max(d, 0); r <= min(m - 1, n - 1 + d); ++r) {
                mat[r][r - d] = v.back();
                v.pop_back();
            }
        }
        return mat;
    }
};