Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 2.6k Reading time ≈ 2 mins.

Union-find O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int n = grid.size();
        int m = grid[0].size();
        int dx[] = {0, -1};
        int dy[] = {-1, 0};
        UnionFind uf(n * m);
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                if (grid[row][col] == '0') continue;
                int x = row * m + col;
                uf.add(x);
                for (int i = 0; i < 2; ++i) {
                    if (isValid(grid, row + dy[i], col + dx[i])) {
                        int y = (row + dy[i]) * m + col + dx[i];
                        uf.make_union(x, y);
                    }
                }
            }
        }
        return uf.count;
    }

    bool isValid(vector<vector<char>> &grid, int row, int col) {
        if (row < 0 || col < 0) {
            return false;
        }
        return grid[row][col] == '1';
    }

    struct UnionFind {
        UnionFind(int n) : count(0) {
            parent.resize(n);
        }

        void add(int x) {
            parent[x] = x;
            ++count;
        }

        void make_union(int x, int y) {
            int parent_x = find(x);
            int parent_y = find(y);
            if (parent_x != parent_y) {
                parent[parent_x] = parent_y;
                --count;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return parent[x];
        }

        vector<int> parent;
        int count;
    };
};

DFS O(mn) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        int res = 0;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(grid, i, j, dy, dx, n, m);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>> &grid, int i, int j, int dy[], int dx[], int n, int m) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0') return;
        grid[i][j] = '0';
        for (int k = 0; k < 4; ++k) {
            dfs(grid, i + dy[k], j + dx[k], dy, dx, n, m);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    ++res;
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>> &grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r - 1, c);
        dfs(grid, r, c - 1);
    }

    int m, n;
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

O(n) time O(1) space
sliding window
find the longest subarray with at most K zeros

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int res = 0;
        for (int l = 0, r = 0, cnt = 0; r < A.size(); ++r) {
            cnt += (A[r] == 0);
            while (cnt > K) {
                cnt -= (A[l++] == 0);
            }
            res = max(res, r + 1 - l);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int l = 0, n = A.size();
        for (int r = 0; r < n; ++r) {
            if (A[r] == 0) --K;
            if (K < 0 && A[l++] == 0) ++K; // 必须把K < 0放前头，K < 0说明0太多了，需要剔除一些（因为1是不会对K变小做贡献的）直到把K变成非负为止（或者r指针到头了）
        }
        return n - l;
    }
};

O(nlogn) time O(1) space
bisection + sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int lo = 0, hi = n;
        while (lo <= hi) {
            int m = lo + (hi - lo) / 2;
            auto ret = isValid(A, K, m);//cout<<"m = "<<m<<", ret = "<<ret<<endl;
            if (ret) {
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return lo - 1;
    }

    bool isValid(const vector<int> &A, int K, int m) {
        for (int l = 0, r = 0, cnt = 0; r < A.size(); ++r) {
            if (A[r] == 0) {
                ++cnt;
            }
            if (cnt <= K && r - l + 1 == m) return true;
            while (l < r && cnt > K) {
                if (A[l++] == 0) --cnt;
            }
        }
        return m == 0;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 696 Reading time ≈ 1 mins.

two pointer O(nlogn) time O(n) space
这道题找的是subsequence不是subarray！！！
举例nums = [5,2,4,1,7,6,8], target = 11
对于1来说因为最大的数是8使得两数之和小于target11 所以除了自身必须要在subsequence里 其他任何数（包括8）都可在可不在所选的subsequence里 所以这样的subsequence共有26个
对于5来说 除了7和8不能选 其他不小于5的数都可选 这样的数只有6一个 所以这样的subsequence共有2个
所以这道题的答案跟每个数的原始位置没有任何关系！！！直接排序即可！！！然后按照two sum去做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(begin(nums), end(nums));
        int l = 0, n = nums.size(), r = n - 1, M = 1e9 + 7, res = 0;
        vector<int> pow2(n, 1);
        for (int i = 1; i < n; ++i) {
            pow2[i] = (pow2[i - 1] * 2) % M;
        }
        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                res = (res + pow2[r - l++]) % M;
            } else {
                --r;
            }
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 482 Reading time ≈ 1 mins.

O(n) n是路径层数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        istringstream input(path);
        string s;
        while (getline(input, s, '/')) {
            if (s.empty() || s == ".") continue;
            if (s == "..") {
                 if (!v.empty()) {
                     v.pop_back();
                 }
            } else {
                v.push_back(s);
            }
        }
        if (v.empty()) return "/";
        string res;
        for (const auto &s : v) {
            res = res + "/" + s;
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> res;
        nums.push_back(upper); // padding好处理，而且nums可能是空的
        long l = lower;
        for (auto it = lower_bound(begin(nums), end(nums), lower);
            it != upper_bound(begin(nums), end(nums), upper);
            ++it) {
            long u = it == prev(end(nums)) ? *it : *it - 1L; // 注意integer overflow，比如[-2147483648, 0]
            if (l == u) {
                res.push_back(to_string(l));
            } else if (l < u) {
                res.push_back(to_string(l) + "->" + to_string(u));
            }
            l = *it + 1L;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        int n = size(nums);
        vector<string> res;
        nums.push_back(upper); // padding好处理，而且nums可能是空的
        long l = lower;
        for (int i = 0; i <= n; ++i) {
            long u = i == n ? nums[i] : ((long)nums[i] - 1); // 注意integer overflow，比如[-2147483648, 0]
            if (l == u) {
                res.push_back(to_string(l));
            } else if (l < u) {
                res.push_back(to_string(l) + "->" + to_string(u));
            }
            l = (long)nums[i] + 1;
        }
        return res;
    }
};

O(n) time O(n) space
先按照228. Summary Ranges总结现有区间，然后再找出missing区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<pair<long, long>> v;
        v.emplace_back(LONG_MIN, lower - 1L);
        vector<string> res;
        auto add = [&v](long x) {
            if (v.back().second + 1 < x) {
                v.emplace_back(x, x);
            } else {
                v.back().second = x;
            }
        };
        for (auto it = lower_bound(begin(nums), end(nums), lower);
            it != upper_bound(begin(nums), end(nums), upper);
            ++it) {
            add(*it);
        }
        add(upper + 1L);
        for (int i = 1; i < size(v); ++i) {
            if (v[i - 1].second + 2 < v[i].first) {
                res.push_back(to_string(v[i - 1].second + 1) + "->" + to_string(v[i].first - 1));
            } else {
                res.push_back(to_string(v[i].first - 1));
            }
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

bfs
有数学方法 不实际

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x), y = abs(y);
        unordered_map<int, int> m{{0, 0}};
        int dx[] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        using tdii = tuple<double, int, int>;
        priority_queue<tdii, vector<tdii>, greater<tdii>> q;
        q.emplace(0, 0, 0);
        while (!q.empty()) {
            auto [_, xx, yy] = q.top(); q.pop();
            if (xx == x && yy == y) return m[x * 1000 + y];
            for (int i = 0; i < 8; ++i) {
                int nx = xx + dx[i], ny = yy + dy[i], k = nx * 1000 + ny;
                if (nx < -1 || ny < -1 || abs(nx) + abs(ny) > 300 || m.count(k)) continue;
                m[k] = m[xx * 1000 + yy] + 1;
                q.emplace(m[k] + dist(nx, ny, x, y), nx, ny);
            }
        }
        return 0;
    }

    double dist(int xx, int yy, int x, int y) {
        return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
    }
};

用这个

1
2
3
// hashmap for pair
auto cmp = [](const auto &a) { return hash<long>{}(a.first) ^ hash<long>{}((long)a.second << 32); };
unordered_map<pair<int, int>, std::vector<pair<int, int>>, decltype(cmp)> m(101, cmp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x), y = abs(y); // 所有坐标调整为第一象限quadrant
        unordered_set<int> s{0};
        int res = 0, dx[] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        queue<pair<int, int>> q{{{0, 0}}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto [xx, yy] = q.front(); q.pop();
                if (xx == x && yy == y) return res;
                for (int j = 0; j < 8; ++j) {
                    int nx = xx + dx[j], ny = yy + dy[j], k = nx * 1000 + ny; // 这里乘1000因为x和y的绝对值都不超过300
                    if (nx < -1 || ny < -1 || abs(nx) + abs(ny) > 300 || s.count(k)) continue; // 这里检查nx和ny是否小于-1是因为到(1, 1)最少步数必须跨象限先到(2, -1)或者(-1, 2)，其他所有走法都比这个差，实际上从0开始跨象限最多到-1到不了-2即从1到-1因为走日字步长最多为2
                    q.emplace(nx, ny);
                    s.insert(k);
                }
            }
            ++res;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minKnightMoves(int x, int y) {
        int t = abs(x) * 1000 + abs(y);
        unordered_set<int> s{0};
        int res = 0, dx[] = {1000, 2000, 2000, 1000, -1000, -2000, -2000, -1000}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        queue<int> q{{0}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int u = q.front(); q.pop();
                if (u == t) return res;
                for (int j = 0; j < 8; ++j) {
                    int v = u + dx[j] + dy[j];
                    if (v < 0 || s.count(v)) continue;
                    q.emplace(v);
                    s.insert(v);
                }
            }
            ++res;
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 727 Reading time ≈ 1 mins.

O(mn) time O(1) space
逐行扫描，每一行前n-1个应该和下一行后n-1个一样

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = size(matrix), n = size(matrix[0]);
        for (int r = 1; r < m; ++r) {
            for (int c = 1; c < n; ++c) {
                if (matrix[r][c] != matrix[r - 1][c - 1]) return false;
            }
        }
        return true;
    }
};

朴素解法，检查每个对角线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = size(matrix), n = size(matrix[0]);
        for (int i = 1 - n; i <= m - 1; ++i) {
            bool set1st = false;
            int x = 0;
            for (int r = max(0, i); r <= min(m - 1, i + n - 1); ++r) {
                if (!set1st) {
                    x = matrix[r][r - i];
                    set1st = true;
                }
                if (x != matrix[r][r - i]) return false;
            }
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {

    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        auto it = cache[key];
        history.splice(begin(history), history, it);
        return it->second;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            auto it = cache[key];
            history.splice(begin(history), history, it);
            it->second = value;
            return;
        }
        if (capacity == size(cache)) {
            auto key_to_delete = history.back().first;
            history.pop_back();
            cache.erase(key_to_delete);
        }
        cache[key] = history.emplace(begin(history), key, value);
    }

    unordered_map<int, list<pair<int, int>>::iterator> cache;
    list<pair<int, int>> history;
    int capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class LRUCache{
public:
    LRUCache(int capacity) : m_capacity(capacity) {}

    int get(int key) {
        auto it(cache.find(key));
        if (it == cache.end()) return -1;
        history.splice(history.begin(), history, it->second); // 把找到的键值对放到链表首表明是最新被访问的
        return it->second->second;
    }

    void set(int key, int value) {
        auto it(cache.find(key));
        if (it != cache.end()) {
            history.splice(history.begin(), history, it->second);
            it->second->second = value;
            return; // cache不需要增加新的键值对，直接返回
        }
        if (cache.size() == m_capacity) { // 一定要先删后加！！！
            auto key_to_be_deleted = history.back().first;
            history.pop_back(); // 弹出最近最少被访问的键值对
            cache.erase(key_to_be_deleted);
        }
        history.emplace_front(key, value); // 把最新的键值对插入链表首
        cache[key] = history.begin();
        // cache[key] = history.insert(begin(history), {key, value});
    }

private:
    unordered_map<int, list<pair<int, int> >::iterator> cache;
    list<pair<int, int> > history;
    size_t m_capacity;
};

Posted on Edited on In Disqus:
Symbols count in article: 958 Reading time ≈ 1 mins.

O(n+k) time O(n) space
bucket sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> f;
        for (int x : nums) {
            ++f[x];
        }
        int n = size(nums);
        vector<vector<int>> m(n + 1);
        for (auto [x, v] : f) {
            m[v].push_back(x);
        }
        vector<int> res;
        for (int i = n; i >= 0; --i) {
            for (int x : m[i]) {
                res.push_back(x);
                if (res.size() == k) return res;
            }
        }
        return res;
    }
};

quick selection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (int x : nums) {
            ++m[x];
        }
        vector<pair<int, int>> v(begin(m), end(m));
        auto cmp = [](const auto &a, const auto &b){ return a.second > b.second; };
        nth_element(begin(v), begin(v) + k, end(v), cmp); // k或k - 1都行
        vector<int> res;
        for (int i = 0; i < k; ++i) {
            res.push_back(v[i].first);
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.7k Reading time ≈ 2 mins.

dp 非典型 O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> w(n - k + 1);
        w[0] = accumulate(begin(nums), begin(nums) + k, 0);
        for (int i = 1; i < w.size(); ++i) {
            w[i] = w[i - 1] - nums[i - 1] + nums[i + k - 1];
        }
        vector<int> left(n - 3 * k + 1);
        for (int i = 0, best = i; i < left.size(); ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best;
        }
        vector<int> right(n - k + 1);
        for (int i = n - k, best = i; i >= 2 * k; --i) {
            if (w[i] >= w[best]) {
                best = i;
            }
            right[i] = best;
        }
        vector<int> res;
        for (int i = k, best = 0; i <= n - 2 * k; ++i) {
            int l = left[i - k], r = right[i + k];
            if (w[l] + w[i] + w[r] > best) {
                best = w[l] + w[i] + w[r];
                res = {l, i, r};
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1); // 计算前缀和
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        vector<int> w(n - k + 1); // 计算所有的相邻k个元素和
        for (int i = 0; i < w.size(); ++i) {
            w[i] = presum[i + k] - presum[i];
        }
        vector<int> left(n - 3 * k + 1); // 计算左边的所有下标使得对应下标开始的k元素和是到当前下标为止最大的
        int best = 0;
        for (int i = 0; i < left.size(); ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best; // best是全局最优，对每个left[i]记录当前全局最优值
        }
        vector<int> right(w.size()); // 因为用的是绝对下标，所以right数组的大小要和w保持一致
        best = w.size() - 1; // 右侧全局最优值从倒数第k个开始
        for (int i = w.size() - 1; i >= 0; --i) { // 这里一定要从右往左计算，因为我们只关心当前下标右侧的全局最优值
            if (w[i] >= w[best]) { // 这里一定要是>=因为我们要取字典序较小的下标，如果两个下标对应的k元素和相等，则取左侧较小的下标
                best = i;
            }
            right[i] = best;
        }
        int mx = 0;
        vector<int> res;
        for (int i = k; i < w.size() - k; ++i) { // 遍历中间的下标
            int l = left[i - k], r = right[i + k]; // 获取当前下标左侧和右侧的最优下标
            int sum = w[l] + w[i] + w[r]; // 查看三个下标对应的k元素和是否是整个数组最大和，是的话就更新
            if (sum > mx) {
                mx = sum;
                res = {l, i, r};
            }
        }
        return res;
    }
};

用这个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = size(nums);
        vector<int> w(n);
        w[0] = accumulate(begin(nums), begin(nums) + k, 0);
        for (int i = 1; i + k <= n; ++i) {
            w[i] = w[i - 1] - nums[i - 1] + nums[i - 1 + k];
        }
        vector<int> left(n);
        int best = 0;
        for (int i = 1; i + k <= n; ++i) {
            if (w[i] > w[best]) {
                best = i;
            }
            left[i] = best;
        }
        vector<int> right(n);
        best = n - k;
        for (int i = n - k; i >= 0; --i) {
            if (w[i] >= w[best]) {
                best = i;
            }
            right[i] = best;
        }
        vector<int> res;
        best = 0;
        for (int i = k; i + k + k <= n; ++i) {
            int l = left[i - k], r = right[i + k];
            if (w[l] + w[i] + w[r] > best) {
                best = w[l] + w[i] + w[r];
                res = {l, i, r};
            }
        }
        return res;
    }
};