Shawn's Blog

Posted on Edited on In 
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
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) -> bool { return a.second < b.second; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        vector<int> boundaries;
        for (auto& building : buildings) {
            boundaries.emplace_back(building[0]);
            boundaries.emplace_back(building[1]);
        }
        sort(boundaries.begin(), boundaries.end());
        vector<vector<int>> ans;
        int n = buildings.size(), i = 0;
        for (auto& b : boundaries) {
            while (i < n && buildings[i][0] <= b) {
                q.emplace(buildings[i][1], buildings[i][2]);
                ++i;
            }
            while (!q.empty() && q.top().first <= b)
                q.pop();
            int maxn = q.empty() ? 0 : q.top().second;
            if (ans.empty() || maxn != ans.back()[1])
                ans.push_back({b, maxn});
        }
        return ans;
    }
};
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 List<List<Integer>> getSkyline(int[][] buildings) {
        int n = buildings.length, i = 0, prevh = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int[] boundaries = new int[n * 2];
        for (int[] b : buildings) {
            boundaries[i++] = b[0];
            boundaries[i++] = b[1];
        }
        Arrays.sort(boundaries);
        ArrayList<List<Integer>> ans = new ArrayList<>();
        i = 0;
        for (int b : boundaries) {
            while (i < n && buildings[i][0] <= b) {
                q.offer(new int[]{buildings[i][1], buildings[i][2]});
                ++i;
            }
            while (!q.isEmpty() && q.peek()[0] <= b)
                q.poll();
            int h = q.isEmpty() ? 0 : q.peek()[1];
            if (ans.isEmpty() || h != prevh)
                ans.add(List.of(b, prevh = h));
        }
        return ans;
    }
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class TimeMap {
    unordered_map<string, vector<pair<int, string>>> m;
public:
    TimeMap() {}
    void set(string key, string value, int timestamp) {
        m[key].emplace_back(timestamp, value);
    }
    string get(string key, int timestamp) {
        auto &v = m[key];
        pair<int, string> p(timestamp, string({127}));
        auto it = upper_bound(v.begin(), v.end(), p);
        return it == v.begin() ? "" : (it - 1)->second;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int i = citations.size() - 1, h = 0;
        while (i >= 0 && citations[i] > h) ++h, --i;
        return h;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), l = 0, r = n;
        auto check = [&](int h) {
            int idx = lower_bound(citations.begin(), citations.end(), h) - citations.begin();
            return n - idx >= h;
        };
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int i = citations.size() - 1, h = 0;
        while (i >= 0 && citations[i] > h) ++h, --i;
        return h;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), c = 0;
        vector<int> cnt(n + 1);
        for (auto &x : citations)
            ++cnt[min(x, n)];
        for (int i = n; i >= 0; i--)
            if ((c += cnt[i]) >= i)
                return i;
        return 0;
    }
};

Posted on Edited on In 
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
class Solution {
public:
    const int MOD = 1000000007;
    int memo[1000][1024];
    int m, n;
    int colorTheGrid(int m, int n) {
        this->m = m, this->n = n;
        return dp(0, 0);
    }
    int dp(int c, int prevColMask) {
        if (c == n) return 1;
        if (memo[c][prevColMask]) return memo[c][prevColMask];
        vector<int> neighbors;
        dfs(0, prevColMask, 0, neighbors);
        int ans = 0;
        for (int nei : neighbors)
            ans = (ans + dp(c + 1, nei)) % MOD;
        return memo[c][prevColMask] = ans;
    }
    void dfs(int r, int prevColMask, int currColMask, vector<int>& ans) {
        if (r == m) {
            ans.emplace_back(currColMask);
            return;
        }
        for (int i = 1; i <= 3; ++i)
            if (getColor(prevColMask, r) != i && (r == 0 || getColor(currColMask, r - 1) != i))
                dfs(r + 1, prevColMask, setColor(currColMask, r, i), ans);
    }
    int getColor(int mask, int pos) {
        return (mask >> (2 * pos)) & 3;
    }
    int setColor(int mask, int pos, int color) {
        return mask |= (color << (2 * pos));
    }
};

Reference: [C++/Python] DP & DFS & Bitmask - Picture explain - Clean & Concise

Posted on Edited on In 
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:
    int countPalindromicSubsequence(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < 26; ++i) {
            int l = 0, r = n - 1, mask = 0, cnt = 0;
            while (l < n && s[l] != 'a' + i) ++l;
            while (r >= l && s[r] != 'a' + i) --r;
            if (r - l <= 1) continue;
            while (++l < r) {
                int idx = s[l] - 'a';
                mask |= (1 << idx);
            }
            for (int i = 0; i < 26; ++i) {
                if (mask >> i & 1)
                    ++cnt;
            }
            ans += cnt;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size(), l[26] = {[0 ... 25] = n}, r[26] = {}, mask, ans = 0;
        for (int i = 0; i < n; ++i) {
            int idx = s[i] - 'a';
            l[idx] = min(l[idx], i);
            r[idx] = i;
        }
        for (int i = 0; i < 26; ++i) {
            mask = 0;
            for (int j = l[i] + 1; j < r[i]; ++j) {
                int idx = s[j] - 'a';
                mask |= (1 << idx);
            }
            ans += __builtin_popcount(mask);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n * 2);
        for (int i = 0; i < n; ++i) {
            ans[i] = nums[i];
            ans[i + n] = nums[i];
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool sumGame(string num) {
        int n = num.size();
        int a = 0, b = 0, ax = 0, bx = 0;
        for (int i = 0; i < n / 2; ++i)
            if (num[i] == '?') ++ax;
            else a += num[i] - '0';
        for (int i = n / 2; i < n; ++i)
            if (num[i] == '?') ++bx;
            else b += num[i] - '0';
        int x = ax + bx;
        if (x & 1) return true;
        int xa = (ax + 1) / 2, xb = x / 2 - xa, ya = ax - xa, yb = bx - xb;
        // [a, ya * 9 + a], [xb * 9 + b, xb * 9 + b + yb * 9]  // Alice focus on minizing a.
        if (ya * 9 + a < xb * 9 + b) return true;
        // [xa * 9 + a, xa * 9 + a + xb * 9], [b, yb * 9 + b] // Alice focus on maxmizing a.
        if (xa * 9 + a > yb * 9 + b) return true;
        return false;
    }
};

Posted on Edited on In 
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 nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int R = maze.size(), C = maze[0].size();
        int r = entrance[0], c = entrance[1];
        int ds[] = {1, 0, -1, 0, 1};
        vector<vector<bool>> vis(R, vector<bool>(C, false));
        queue<pair<int, int>> q;
        q.emplace(r, c);
        vis[r][c] = true;
        int steps = 0;
        while (!q.empty()) {
            ++steps;
            int size = q.size();
            while (size--) {
                auto [cr, cc] = q.front(); q.pop();
                for (int i = 0; i < 4; ++i) {
                    int nr = cr + ds[i], nc = cc + ds[i + 1];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C || maze[nr][nc] == '+' || vis[nr][nc]) continue;
                    if (nr == R - 1 || nc == C - 1 || nr == 0 || nc == 0) return steps;
                    q.emplace(nr, nc);
                    vis[nr][nc] = true;
                }
            }
        }
        return -1;
    }
};
0%