YoungForest's blog

LeetCode weekly contest 140

发表于 2019-06-09 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
313 / 4046	YoungForest	16	1:03:21	0:21:32 (1)	0:36:08	0:53:21 (1)	null

本次比赛难度适中，由于评测程序的问题，很多人被第三题坑了。赛后test case修改正确了。这已经不是LeetCode第一次出现事故了。

5083. Occurrences After Bigram

思路：
签到题，直接做。用一个状态机来记录当前的状态。

时间复杂度: O(text.size()),
空间复杂度: O(1). 我的实现中，为了方便将token存在一个vector中，其实是没必要的。

class Solution {
    enum class State {
        other,
        first,
        second
    };
public:
    vector<string> findOcurrences(string text, string first, string second) {
        vector<string> ret;
        istringstream iss(text);
        vector<string> tokens{istream_iterator<string>{iss}, {}};
        State state = State::other;
        for (const auto & token : tokens) {
            if (state == State::second) {
                ret.push_back(token);
                state = State::other;
            }
            if (token == first) {
                state = State::first;
            } else if (token == second && state == State::first) {
                state = State::second;
            } else {
                state = State::other;
            }
        }
        return ret;
    }
};

5087. Letter Tile Possibilities

由于数据规模比较小，tiles.length <= 7, 所以直接暴力枚举所有的可能即可。
时间复杂度: O(N!),
空间复杂度: O(N!).

class Solution {
    set<string> ret;
    void backtracking(map<char, int>& count, int size, int step, string& current) {
        if (step == size) {
            ret.insert(current);
            return;
        }
        for (auto& p : count) {
            char c = p.first;
            if (count[c] > 0) {
                --count[c];
                current.push_back(c);
                backtracking(count, size, step + 1, current);
                current.pop_back();
                ++count[c];
            }
        } 
    }
public:
    int numTilePossibilities(string tiles) {
        map<char, int> count;
        for (char tile : tiles) {
            ++count[tile];
        }
        int s = tiles.size();
        for (int len = 1; len <= s; ++len) {
            string current;
            backtracking(count, len, 0, current);
        }
        // for (auto& s : ret) {
        //     cout << s << " ";
        // }
        return ret.size();
    }
};

5084. Insufficient Nodes in Root to Leaf Paths

阅读全文 »

LeetCode biweekly contest 1

发表于 2019-06-03 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
241 / 983	YoungForest	7	0:18:23	0:09:56	0:18:23	null	null

LeetCode开放了首届的双周赛，每周六晚上10:30~12:30。目的可能是方便欧洲的同学参赛（平时的单周赛欧洲那边都是凌晨），可以出更难的题目。因为时长扩展到2个小时了。

由于19:00~21:30已经参加了Byte dance 的summer camp笔试。该笔试题也很难，3道编程题只有第二题过了30%。所以稍后的biweekly contest也翻车了，完成的并不理想。只作出了2道Easy的题目。

1055. Fixed Point

Intuition:
Straight forward. One pass.

时间复杂度: O(N)
空间复杂度: O(1)

class Solution {
public:
    int fixedPoint(vector<int>& A) {
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == i) {
                return i;
            }
        }
        return -1;
    }
};

由于数组A是升序的，所以还可以用二分搜索的算法，实现O(log N).

class Solution {
public:
    int fixedPoint(vector<int>& A) {
        int lo = 0, hi = A.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] < mid) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return A[lo] == lo ? lo : -1;
    }
};

1056. Index Pairs of a String

阅读全文 »

LeetCode weekly contest 139

发表于 2019-06-03 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
855 / 3985	YoungForest	10	1:03:50	0:53:00	1:03:50	赛后做出来	null

周日起来的时候已经11点多了，算是迟到40min才参加的比赛。顺利作出了前2题，第3题开始走了些弯路，赛后才做出来。如果时间够的话，第3题作出应该没意思。

1071. Greatest Common Divisor of Strings

Intuition:
此题相当于是找2个数的最大公约数。
Greatest Common Divisor的长度一定等于最大公约数或0.
简单的证明如下：
设答案的长度为x, str1由x组成，所以x一定是str1.length的约数. 同样，也是str2.length。
假设x不是最大公约数，可以组成str1和str2。那么最大公约数也一定可以组成str1和str2。

时间复杂度: O(log N)
空间复杂度: O(N)

class Solution {
    int gcd(int a, int b) {
        if (b > a) {
            swap(a, b);
        }
        while (b > 0) {
            auto temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
public:
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        auto common_len = gcd(len1, len2);
        auto t1 = str1.substr(0, common_len);
        auto t2 = str2.substr(0, common_len);
        return t1 == t2 ? t1 : "";
    }
};

1072. Flip Columns For Maximum Number of Equal Rows

Intuition:
寻找互补的行的最大数量。

时间复杂度: O(matrix.length * matrix[0].length)
空间复杂度: O(matrix.length * matrix[0].length)

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> count;
        int ret = 0;
        for (const auto& row : matrix) {
            string right, complete;
            for (int item : row) {
                right.push_back(item + '0');
                complete.push_back(((~item) & 1) + '0');
            }
            ++count[right];
            ++count[complete];
            ret = max({ret, count[right], count[complete]});
        }
        return ret;
    }
};

阅读全文 »

LeetCode weekly conteset 138

发表于 2019-05-26 更新于 2026-04-28 分类于 LeetCode Disqus：

本周比赛虽然题目质量还不错，但难度不高，是一场比拼速度的题目。
因为第二题题目比较长，所以我做题的顺序是 1->3->4->2。

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
247 / 4143	YoungForest	20	0:57:43	0:11:19	0:52:43 (1)	0:27:35	0:36:44

1051. Height Checker

Intuition:
简单的排序，然后遍历比较一遍。
时间复杂度: O(N log N)
空间复杂度: O(N)

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        auto copy = heights;
        sort(copy.begin(), copy.end());
        int ret = 0;
        for (int i = 0; i < heights.size(); ++i) {
            if (copy[i] != heights[i])
                ++ret;
        }
        return ret;
    }
};

1052. Grumpy Bookstore Owner

本题是最后做的，花费了不少时间。本次进不了前200的原因，首先是第一题读懂题目花了过长的时间，其次就是本题有些着急做，直接写代码，写错了思路，后来才改的。然后是本题还有一次罚时，是因为第一次忘记更新max_wanhui了。事实上，我刚开始是记得要更新的，但是写的时候就忘了。
教训就是，先把题的算法想好，确定可行在写代码；另外，需要先写test case，尤其是corner case，再想算法，再下笔。这样可以有效验证算法和代码的正确性。

Intuition:
滑动窗口。不断更新最大的挽回损失的值。

时间复杂度: O(N).
空间复杂度: O(1).

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int n = customers.size();
        const int total_customers = accumulate(customers.cbegin(), customers.cend(), 0);
        int sunshi = 0;
        for (int i = 0; i < n; ++i) {
            if (grumpy[i] == 1)
                sunshi += customers[i];
        }
        int max_wanhui = 0;
        int wanhui = 0;
        for (int i = 0; i < X; ++i) {
            if (grumpy[i] == 1)
                wanhui += customers[i];
        }
        max_wanhui = max(max_wanhui, wanhui);
        
        for (int i = X; i < n; ++i) {
            if (grumpy[i] == 1)
                wanhui += customers[i];
            if (grumpy[i - X] == 1)
                wanhui -= customers[i - X];
            max_wanhui = max(max_wanhui, wanhui);
        }
        // cout << total_customers << " " << sunshi << " " << max_wanhui << endl;
        return total_customers - sunshi + max_wanhui;
    }
};

阅读全文 »

LeetCode weekly contest 137

发表于 2019-05-19 更新于 2026-04-28 分类于 LeetCode Disqus：

本周的题目要比以往的难，也可以说恰好考到我的知识盲区，DP问题。老实的说，我对DP问题没有过深入的研究。这次DP题目尤其多，尤其是第4题，更是可以可以用经典的背包问题求解。

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
576 / 4091	YoungForest	13	0:45:56	0:09:24	0:14:20	0:35:56 2	null

1046. Last Stone Weight

Intuition：
本题解法不难。我首先想到了最暴力的模拟整个smash的过程的解法。因为是签到题，暴力解也够了。
时间复杂度: O(n^2 log n)
空间复杂度: O(1)

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // 模拟smash
        // sort
        // pick two heaviest
        // smash
        // n^2 log n
        while (stones.size() > 1) {
            sort(stones.begin(), stones.end());
            int n = stones.size();
            stones[n - 2] = stones[n - 1] - stones[n - 2];
            stones.pop_back();
        }
        return stones[0];
    }
};

但事实上，同样是模拟smash的过程，找到最大的2个石头。我用的办法是sort，该操作的时间复杂度为O(n log n). 大佬们就能想到优先队列(Priority Queue), 找石头的时间复杂度为O(log n). 而且我的解法并没有专门处理x == y的情况，虽然不会出什么问题，但确实不符合模拟过程的初衷。

Priority queue 版本

时间复杂度：O(N log N)
空间复杂度: O(1)

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(), stones.end());
        while (pq.size() > 1) {
            int y = pq.top();
            pq.pop();
            int x = pq.top();
            pq.pop();
            if (y > x)
                pq.push(y - x);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

1047. Remove All Adjacent Duplicates In String

阅读全文 »

LeetCode weekly contest 136

发表于 2019-05-12 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
220 / 4109	YoungForest	15	0:59:43	0:17:07	0:29:36	0:54:43 (1)	null

最近比赛的质量都还可以。即使是最简单的签到题，也是需要认真思考的。考察DP的题也是每次都有，DP算是那种你做很多，遇到新的题目还是可能写不出来的类型。
本次恢复了原先的水平，跌到了200+。
这次大概需要55分钟前3题，才能进入前200。我一是做题比较慢，二是第3题DP有个下标问题搞错了，导致了一次罚时。所以遗憾地没有进入前200.

1041. Robot Bounded In Circle

Intuition:
执行instruction直到再此面朝北。因为只有4个方向，所以最多执行4次，也可能是2次或1次。
如果此时不在原点，则继续走下去一定越走越远。否则就是一个circle.
时间复杂度: O(instructions.length),
空间复杂度: O(1)

class Solution {
    enum class Direction {
        north,
        south,
        west,
        east
    };
public:
    bool isRobotBounded(string instructions) {
        // 只要执行完一次instructions, 面朝北，同时不在原点，就没有圈。否则有圈
        Direction direction = Direction::north;
        int x = 0, y = 0;
        do {
            for (char c : instructions) {
                if (c == 'G') {
                    switch (direction) {
                        case Direction::north:
                            ++y;
                            break;
                        case Direction::south:
                            --y;
                            break;
                        case Direction::west:
                            --x;
                            break;
                        case Direction::east:
                            ++x;
                            break;
                    }
                } else if (c == 'L') {
                    switch (direction) {
                        case Direction::north:
                            direction = Direction::west;
                            break;
                        case Direction::south:
                            direction = Direction::east;
                            break;
                        case Direction::west:
                            direction = Direction::south;
                            break;
                        case Direction::east:
                            direction = Direction::north;
                            break;
                    }
                } else if (c == 'R') {
                    switch (direction) {
                        case Direction::north:
                            direction = Direction::east;
                            break;
                        case Direction::south:
                            direction = Direction::west;
                            break;
                        case Direction::west:
                            direction = Direction::north;
                            break;
                        case Direction::east:
                            direction = Direction::south;
                            break;
                    }
                }
                // cout << x << " " << y << " " << static_cast<int>(direction) << endl;
            }
        } while (direction != Direction::north);
        return x == 0 && y == 0;
    }
};

1042. Flower Planting With No Adjacent

Intuition:
染色问题。因为一定存在解，所以可以基于贪心的思路。每次取可取颜色中的任意一个。

时间复杂度: O(N),
空间复杂度: O(N).
有二维数组和2层循环，难道不是N^2嘛？事实上由于出入度 <= 3, 颜色个数为4. 第二维的复杂度其实是个常数。

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> ret(N, 0);
        vector<vector<int>> edges(N + 1);
        vector<set<int>> remain_color(N + 1, {1, 2, 3, 4});
        for (const auto path : paths) {
            edges[path[0]].push_back(path[1]);
            edges[path[1]].push_back(path[0]);
        }
        for (int i = 1; i <= N; ++i) {
            if (remain_color[i].begin() != remain_color[i].end()) {
                auto color = *(remain_color[i].begin());
                ret[i - 1] = color;
                for (auto j : edges[i]) {
                    remain_color[j].erase(color);
                }
            }
        }
        return ret;
    }
};

1043. Partition Array for Maximum Sum

阅读全文 »

Effective Modern C++

发表于 2019-05-05 更新于 2026-04-28 分类于书评 Disqus：

我的书评

阅读全文 »

LeetCode weekly contest 135

发表于 2019-05-05 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (5)	Q4 (5)
70 / 3635	YoungForest	15	1:34:07	0:07:28	0:16:45	null	1:29:07 (1)

本周日是国内的工作日，参加LeetCode weekly contest的人直接少了1千，可见国内参与此比赛的热情。而且国人的实力一般也是排在世界前列的。所以我此次排名为70，首次进入前200，除了争分夺秒在结束前AC掉最后一题的功劳外，还有参赛大佬减少的原因。

5051. Valid Boomerang

Intuition:
分为判断distinct和not in a straight line两部分。
3点共线可以用斜率直接判断。
时间复杂度: O(1)
空间复杂度: O(1)

class Solution {
    bool isSame(vector<int>& x, vector<int>& y) {
        return x[0] == y[0] && x[1] == y[1];
    }
public:
    bool isBoomerang(vector<vector<int>>& points) {
        return !isSame(points[0], points[1]) && !isSame(points[1], points[2]) && !isSame(points[2], points[0]) && static_cast<double>(points[2][1] - points[1][1]) / static_cast<double>(points[2][0] - points[1][0]) != static_cast<double>(points[1][1] - points[0][1]) / static_cast<double>(points[1][0] - points[0][0]);
    }
};

discuss内发现的技巧：

可以直接用面积是否为0同时判断 distinct和贡献，面积的公式用叉乘计算。
判断斜率时，把除法转换成乘法会更好。此时也不需要提前判断distinct。

我的解法会有除0的问题，
但仍然能通过[[1,2],[1,1],[2,1]]这样的测试用例。
仔细想想C++的浮点数除法，根据IEEE 754 标准，结果为+infinite。自然有不相等的结果。

1038. Binary Search Tree to Greater Sum Tree

/**
 * 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 {
    int current = 0;
    void recurse(TreeNode* root) {
        if (!root) return;
        recurse(root->right);
        current += root->val;
        root->val = current;
        recurse(root->left);
    }
public:
    TreeNode* bstToGst(TreeNode* root) {
        recurse(root);
        return root;
    }
};

阅读全文 »

LeetCode weekly contest 134

发表于 2019-04-28 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (5)	Q4 (5)
220 / 4136	YoungForest	17	1:45:10	0:14:52 (1)	0:33:50(1)	null	1:25:10 (2)

本次比赛质量在上周的基础上继续提高。尤其是corner case，导致我有4次incorrect attempts, 也就是20min的罚时。不过我看leader board上，大家的战况也都差不多，错误尝试很多。
本次比赛的重点在于作出所有的题目。恰好需要4道题，才能进入前200. 因为第三题的思路问题，即使再给我半个小时，我也难以做出来。所以我输的还算心服口服。

1033. Moving Stones Until Consecutive

Intuition:
最小移动步数只有3种情况：
0: 3个坐标紧挨，
1: 2个紧挨或 2个中间空一个
2: x, y y, z之间的间隔都大于1.
最大移动步数一定是 z - x - 2, 此时每次移动都只向中间移一步。

时间复杂度: O(1)
空间复杂度: O(1)

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        // greedy
        int minimum_moves = 0, maximum_moves;
        int x = min({a, b, c});
        int z = max({a, b, c});
        int y = a + b + c - x - z;

        if (y - x == 1 && z - y == 1)
            minimum_moves = 0;
        else if (y - x == 1 || z - y == 1 || y - x == 2 || z - y == 2)
            minimum_moves = 1;
        else
            minimum_moves = 2;
        maximum_moves = z - y - 1 + y - x - 1;
        return {minimum_moves, maximum_moves};
    }
};

1034. Coloring A Border

Intuition:
dfs 染色。需要注意如何标注已经访问的节点，在这里我使用了负数来表示。
时间复杂度: O(n*m),
空间复杂度: O(1), in place.

class Solution {
    bool border(vector<vector<int>>& grid, int r, int c) {
        vector<int> di = {1, 0, -1, 0};
        vector<int> dj = {0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int ni = r + di[k];
            int nj = c + dj[k];
            if (ni < 0 || ni >= grid.size() || nj < 0 || nj >= grid[0].size() || abs(grid[ni][nj]) != abs(grid[r][c]))
                return true;
        }
        return false;
    }
    void dfs(vector<vector<int>> &grid, int r, int c) {
        grid[r][c] = -grid[r][c];
        vector<int> di = {1, 0, -1, 0};
        vector<int> dj = {0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int ni = r + di[k];
            int nj = c + dj[k];
            if (ni >= 0 && ni < grid.size() && nj >= 0 && nj < grid[0].size() && grid[ni][nj] == abs(grid[r][c]))
                dfs(grid, ni, nj);
        }
        if (!border(grid, r, c))
            grid[r][c] = -grid[r][c];
    }
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
        // dfs
        if (grid[r0][c0] == color) return grid;
        int origin_color = grid[r0][c0];
        dfs(grid, r0, c0);
        for (auto& r : grid) {
            for (auto & item : r) {
                if (item < 0)
                    item = color;
            }
        }
        return grid;
    }
};

1035. Uncrossed Lines

阅读全文 »

LeetCode weekly contest 133

发表于 2019-04-21 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (5)	Q4 (5)
864 / 4860	YoungForest	14	1:10:35	0:42:32	0:54:38	1:10:35	null

本周的题目相比前几周质量有了不少提升，水题减少，考察的算法知识也更多。即使是前2题是easy题，也考察了足够的编程能力。本次比赛由于一开始肚子疼耽误了半个小时，所以开始的比较晚。最后一题其实差一点是可以AC的。总的方向是对的，即使用Trie单词树。但最后10min时提交后，TLE，也没时间改了。单词树的构造方向走反了，对于匹配问题，我们可以从前向后，也可以从后向前。这道题从后向前不仅实现起来更简单，时间上也会更好些(即使最坏情况的时间复杂度是一样的)。

1030. Matrix Cells in Distance Order

Intuition:
根据距离对所有格子进行排序。
这里我是用了treemap，可以插入后保持有序。你也可以构造一个vector，然后再排序。
时间复杂度：O(R * C * log (R*C)).
空间复杂度：O(R * C).

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        multimap<int, pair<int, int>> distance;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                distance.insert({abs(r0 - i) + abs(c0 - j), {i, j}});
            }
        }
        vector<vector<int>> ret;
        for (const auto& item : distance) {
            ret.push_back(vector<int> { item.second.first, item.second.second});
        }

        return ret;
    }
};

刚开始试图直接构造出结果，但发现不是很好写。果断放弃，不过还是耽误了些时间。
看了discuss后，发现主流的解法还是从构造出发的。不过用了标准的BFS，会好写的多。

1029. Two City Scheduling

Intuition:
贪心。
因为每个人肯定要被派到一个城市，而且结果是求最小花费和。
所以以每个人的不同城市的花费之差为标准进行排序，前一半去A，后一半去B即可。

时间复杂度: O(N log N),
空间复杂度: O(1).

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& lhs, const vector<int>& rhs) -> bool {
            return lhs[1] - lhs[0] > rhs[1] - rhs[0];
        });
        int N = costs.size() / 2;
        
        int ret = 0;
        for (int i = 0; i < N; ++i) {
            ret += costs[i][0];
        }
        for (int i = N; i < 2*N; ++i) {
            ret += costs[i][1];
        }
        return ret;
    }
};

阅读全文 »