YoungForest's blog

LeetCode weekly contest 225

发表于 2021-01-24 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
299 / 11282	YoungForest	18	1:16:19	0:05:09	0:18:06	0:29:04	1:11:19 1

1736. Latest Time by Replacing Hidden Digits

贪心。分析每位的情况，if-else解决。

class Solution {
public:
    string maximumTime(string time) {
        if (time[4] == '?') {
            time[4] = '9';
        }
        if (time[3] == '?') {
            time[3] = '5';
        }
        if (time[1] == '?') {
            if (time[0] == '?') {
                time[0] = '2';
                time[1] = '3';
            } else if (time[0] == '2') {
                time[1] = '3';
            } else {
                time[1] = '9';
            }
        } else {
            if (time[0] == '?') {
                if (time[1] < '4') {
                    time[0] = '2';
                } else {
                    time[0] = '1';
                }
            }
        }
        return time;
    }
};

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

1737. Change Minimum Characters to Satisfy One of Three Conditions

计算每种目标情况。
1，2: 枚举分割点，变换超过分割点的不合适字符。
3: 找到众数即可。

class Solution {
public:
    int minCharacters(string a, string b) {
        int ans = a.size() + b.size();
        auto calculatePresum = [&](const string& x) -> vector<int> {
            vector<int> ans(26, 0);
            for (char c : x) {
                ++ans[c - 'a'];
            }
            for (int i = 1; i < 26; ++i) {
                ans[i] += ans[i - 1];
            }
            return ans;
        };
        auto op12 = [&](const string& a, const string& b) -> void {
            // 26 * (a.size() + b.size())
            auto presumA = calculatePresum(a);
            auto presumB = calculatePresum(b);
            // b >= splitPoint, a < splitPoint
            for (int splitPoint = 1; splitPoint < 26; ++splitPoint) {
                int need = 0;
                // a need
                need += a.size() - presumA[splitPoint - 1];
                // b need
                need += presumB[splitPoint - 1];
                ans = min(ans, need);
            }
        };
        // 1, 2
        op12(a, b);
        op12(b, a);
        
        // 3
        // size 和 - 众数
        {
            unordered_map<char, int> cnt;
            for (char c : a) {
                ++cnt[c];
            }
            for (char c : b) {
                ++cnt[c];
            }
            int maxCnt = 0;
            for (auto p : cnt) {
                maxCnt = max(maxCnt, p.second);
            }
            ans = min(ans, static_cast<int>(a.size() + b.size()) - maxCnt);
        }
        return ans;
    }
};

时间复杂度: O(n + 26),
空间复杂度: O(26).

1738. Find Kth Largest XOR Coordinate Value

阅读全文 »

LeetCode weekly contest 222

发表于 2021-01-03 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
331 / 9692	YoungForest	18	2:02:29	0:05:32	0:13:55 2	0:54:53 2	1:17:29 5

5641. Maximum Units on a Truck

贪心。按盒子容量从大到小排序后先用大的盒子。

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        // greedy, put larger boxes first
        sort(boxTypes.begin(), boxTypes.end(), [](const auto& a, const auto& b) -> bool {
            if (a[1] != b[1]) return a[1] > b[1];
            else return a[0] > b[0];
        });
        int ans = 0;
        int i = 0;
        while (truckSize > 0 && i < boxTypes.size()) {
            const int put = min(truckSize, boxTypes[i][0]);
            truckSize -= put;
            ans += boxTypes[i][1] * put;
            ++i;
        }
        return ans;
    }
};

时间复杂度: O(n log n), n = boxTypes.size()
空间复杂度: O(log n). 快排内部的递归消耗。

5642. Count Good Meals

类似two-sum。使用hashtable维护之前见过的数，只是target数目编程了22.
从2^0 到最大的2^21.

class Solution {
    using ll = int;
    const int maxBit = 22;
    const int MOD = 1e9 + 7;
public:
    int countPairs(vector<int>& deliciousness) {
        vector<ll> target(maxBit);
        target[0] = 1;
        for (int i = 1; i < maxBit; ++i) {
            target[i] = target[i-1] * 2;
        }
        unordered_map<ll, int> count;
        int ans = 0;
        for (ll i : deliciousness) {
            for (int j = 0; j < maxBit; ++j) {
                auto it = count.find(target[j] - i);
                if (it != count.end()) {
                    ans = (ans + it->second) % MOD;
                }
            }
            ++count[i];
        }
        return ans;
    }
};

时间复杂度: O(22n),
空间复杂度: O(n).

比赛过程中，由于错误估计了最大的幂数。2^20 + 2^20 = 2^21, 错估计成了2^40。导致2次超时罚时。

阅读全文 »

LeetCode biweekly contest 42

发表于 2020-12-27 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
573 / 6631	YoungForest	12	0:51:14	0:19:42	0:24:42 1	0:46:14	差一分钟debug出来，好气呀！

1700. Number of Students Unable to Eat Lunch

模拟题目中描述的吃饭的过程。事实上因为判断结束条件的原因，实现起来还不是那么直接了当。

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        const int n = students.size();
        int ans = 0;
        queue<int> stu;
        for (int i : students) {
            stu.push(i);
        }
        stack<int> sand;
        for (int i = sandwiches.size() - 1; i >= 0; --i) {
            sand.push(sandwiches[i]);
        }
        while (!stu.empty()) {
            int current = stu.size();
            while (!stu.empty()) {
                int s = stu.front();
                stu.pop();
                if (s == sand.top()) {
                    sand.pop();
                    ++ans;
                    break;
                } else {
                    --current;
                    stu.push(s);
                    if (current == 0) {
                        return n - ans;
                    }
                }
            }
        }
        return 0;
    }
};

时间复杂度: O(students.size() * sandwiches.size()),
空间复杂度: O(students.size() + sandwiches.size()).

其实我的实现想复杂了。因为要有遍历学生的操作，所以学生的顺序其实是无所谓的。统计学生喜欢的种类，然后不断判断sandwiches栈顶元素是否满足条件。

1701. Average Waiting Time

模拟做饭的过程。对于每一个顾客，判断他来时是否可以直接开始做饭。

class Solution {
    using ll = long long;
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        ll wait = 0;
        ll current = 0;
        for (const auto& v : customers) {
            if (current <= v[0]) {
                current = v[0] + v[1];
                wait += v[1];
            } else {
                wait += (current + v[1] - v[0]);
                current += v[1];
            }
        }
        double n = customers.size();
        return wait / n;
    }
};

时间复杂度: O(customers.size()),
空间复杂度: O(1).

阅读全文 »

LeetCode weekly contest 221

发表于 2020-12-27 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
231 / 8838	YoungForest	18	1:24:39	0:03:55	0:21:00	0:30:16	1:09:39 3

5637. Determine if String Halves Are Alike

签到题。使用set记录元音，然后挨个统计即可。

class Solution {
public:
    bool halvesAreAlike(string s) {
        unordered_set<char> yuan = {'a', 'e', 'i', 'o', 'u',
                                    'A', 'E', 'I', 'O', 'U'};
        const int n = s.size();
        int first = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (yuan.find(s[i]) != yuan.end()) ++first;
        }
        int last = 0;
        for (int i = n / 2; i < n; ++i) {
            if (yuan.find(s[i]) != yuan.end()) ++last;
        }
        return first == last;
    }
};

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

5638. Maximum Number of Eaten Apples

贪心。先吃快过期的苹果。
使用TreeMap维护过期时间，二分搜索寻找过期时间最近的苹果。

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        const int n = apples.size();
        int maxDay = n;
        for (int i = 0; i < n; ++i) {
            maxDay = max(maxDay, i + days[i]);
        }
        map<int, int> rust;
        int ans = 0;
        // cout << "maxDay: " << maxDay << endl;
        for (int i = 0; i < maxDay; ++i) {
            if (i < n && apples[i] > 0) {
                rust[i + days[i] - 1] += apples[i];
            }
            auto it = rust.lower_bound(i);
            if (it != rust.end()) {
                // cout << i << endl;
                ++ans;
                --it->second;
                if (it->second == 0) {
                    rust.erase(it);
                }
            }
        }
        return ans;
    }
};

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

1706. Where Will the Ball Fall

阅读全文 »

LeetCode weekly contest 218

发表于 2020-12-06 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
71 / 9827	YoungForest	18	0:48:21	0:03:32	0:05:23	0:12:14	0:43:21 1

1678. Goal Parser Interpretation

签到题。字符串解释，通用的做法是先做词法分析得到token，然后在依次翻译。由于本题的token比较少，设定也简单，所以可以一次遍历，向前看以确定token。

class Solution {
public:
    string interpret(string command) {
        string ans;
        for (int i = 0; i < command.size(); ++i) {
            if (command[i] == 'G') {
                ans.push_back('G');
            } else {
                if (command[i + 1] == ')') {
                    ans.push_back('o');
                    ++i;
                } else {
                    ans.push_back('a');
                    ans.push_back('l');
                    i += 3;
                }
            }
        }
        return ans;
    }
};

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

据说Python 选手都是一行代码搞定。

1679. Max Number of K-Sum Pairs

贪心。对于每个数，找到它对应的数，然后remove掉即可。使用一个哈希表存储之前见到的数，然后找的花费就是O(1)了。

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        unordered_map<int, int> count;
        for (int i : nums) {
            if (count[k - i] > 0) {
                ++ans;
                --count[k - i];
            } else {
                ++count[i];
            }
        }
        return ans;
    }
};

时间复杂度: O(N), 代码中的排序其实是不需要的，比赛时没注意就先排序了。
空间复杂度: O(N).

阅读全文 »

LeetCode weekly contest 217

发表于 2020-11-29 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (6)	Q4 (7)
356 / 9462	YoungForest	13	1:24:07	0:03:55	0:20:14	1:09:07 3	null

1672. Richest Customer Wealth

签到题。数组求和, C++ accumulate 一行搞定。

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int ans = 0;
        for (const auto & v : accounts) {
            ans = max(ans, accumulate(v.begin(), v.end(), 0));
        }
        return ans;
    }
};

1673. Find the Most Competitive Subsequence

类似 402. Remove K Digits，采用贪心的思路，尽量删除大的数。标准做法是使用单调栈。

比赛时我采用的是优先队列维护要删除的最大数。

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        using pii = pair<int, int>;
        auto cmp = [](pii a, pii b) -> bool {
            if (a.first != b.first) {
                return a.first > b.first;
            } else {
                return a.second > b.second;
            }
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> m(cmp);
        
        for (int i = 0; i + k - 1 < nums.size(); ++i) {
            m.push({nums[i], i});
        }
        int begin = 0;
        vector<int> ans;
        while (k > 0) {
            auto p = m.top();
            m.pop();
            while (p.second < begin && !m.empty()) {
                p = m.top();
                m.pop();
            }
            begin = p.second;
            ans.push_back(p.first);
            --k;
            if (k == 0) break;
            m.push({nums[nums.size() - k], nums.size() - k});
        }
        return ans;
    }
};

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

1674. Minimum Moves to Make Array Complementary

阅读全文 »

2020年终总结与 2021新年展望

发表于 2020-11-25 更新于 2026-04-28 分类于 dairy Disqus：

转发自我的博客

今年也年终总结有些早，还没有步入12月份。不过因为今天刚交了大论文查重，虽然很多事儿要做，但完全没有工作的心情。不如就利用这种烦躁的心情写个年终总结的初稿，不知道会不会受影响。

2020年从一开始就是注定不平凡的一年，之前我只预见到因为我要毕业，只是对我而言，没想到一场席卷全球的疫情使得它成为了对所有人都很有挑战的年份。

2020年工作回顾

首先，我对照我去年写的展望，回顾一下完成度。

每天刷题算是如愿完成，尤其是加入残酷打卡群后，刷题还可以领红包真开心。在群里还可以认识一堆大佬，个个都是人才，说话又好听。研究生2年半刷题1k+，LeetCode周赛参加近100场，世界排名一度进入前500，rating稳定在2200+，rating排名稳定在前1000，周赛一半以上可以完成4题，保证3题，排名经常前500，最高前100，国服也3次拿礼物，虽然不值钱，但很开心。残酷群排名最高11名，稳定前40，偶尔稳定前20。这些成绩还是让我小骄傲的。虽然别人可能并不会很看重这些，但我自己乐在其中，取得了成就感，形成了刷题的正反馈。
但之后我不会投入更多的时间刷题了，如今已经过了刷题高峰，暂时没有找工作的压力，而且刷题的水平已经到了一定高度，刷题的收益没之前那么大了。之后计划每日做一两题保证手感，周末争取每周打周赛，继续在残酷群当镰刀。更多时间会被投入到其他技能上，如工作技能、系统设计、英语口语等。

外企大厂也如愿完成。虽然由于疫情原因，第一志愿Google全面取消了今年的暑期实习项目，本来一面都过了。甚至之后的秋招也直接没了。不过如愿到第二志愿亚马逊参加了6个月的远程实习。虽然不是一开始报的后端岗位，而是iOS客户端岗位，但是好在亚麻SDE都是全栈的，工作中也有不少涉及后端的工作；自己这几个月的实习体验也还不错；之后也有不少转组和transfer的机会。
之后如果不出意外的话还是会转正留任。

今年求职主要分2个部分，春季的实习面试和秋招。
因为目标明确再加上准备充分（4段实习经历+1k道leetcode+科班背书），虽然上半年疫情半年呆在家，不少公司都缩招了，尤其是外企，我仍然拿到不少不错的offer。最后综合考虑（也是一直以来的规划导致）选择在亚马逊这样的外企大厂实习和留任，放弃了国内互联网企业和高薪的独角兽。总体求职和面试过程加结果都比较顺利和满意。

科研和毕设这块也十分满意。虽然上半年花了不少功夫写了篇小论文投了3m，但惨被拒，但完成小论文过程中的实验和经历很好的帮助我按时写完了大论文，今天刚递交查重，不出意外可以按时毕业不需要延毕。最近一年也是研究生涯中最投入科研的一年，虽然没啥成果，但也尽力了。自己真的不是做学术这块料。还是好好做个软件开发工程师实在。

12月更新。按时毕业的期望还是出了意外。由于去年下半年在外交换，和导师商量下学期开学再开题。然而，到了下学期竟然直接半年没开，也是醉了。导师一直拖到8月份才给我开了题。到12月答辩时不足6个月，不符合学校规定，无法参加答辩。只能改为明年6月的第二批答辩。
随之带来一系列影响，最大的还是只能7月份才能正式入职公司。
原来以为马上就要脱离苦海了，没想到又要多呆半年。学院也是最后一步才卡你。早些告知我不能按时答辩，我之前也不用为了12月的答辩那么赶了。学院领导也是不顾学生的死活和疫情的事实，只关心自己的乌纱帽。我就差从学院跳楼了。导师也找学院领导求情了也是不行。

阅读全文 »

LeetCode weekly contest 216

发表于 2020-11-22 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
862 / 9573	YoungForest	18	0:58:34	0:12:47	0:23:33	0:33:14	0:58:34

之前连续5周免残酷群打卡，着实爽了一个月。上周虽然在前500，但只做出3题。本周虽然做出了4题，但出了前500. 又要打一周卡了。残酷群排名也降到了38名，不再15名的巅峰时光了。
自从秋招结束后，再加上实习/大论文特别忙，就没时间刷题了。甚至之前交大论文形式审查最忙的时候，一道题都不刷。11月份以来，恢复了刷国服/美服每日一题的习惯。主要是这2题一般比较简单，花的时间少。另外是想打卡赚积分，争取毕业前可以换2套衣服。
3道打卡题的难度基本上是 残酷 > 国服 >= 美服。

1662. Check If Two String Arrays are Equivalent

签到题。把列表字符串拼接起来然后再比较即可。

class Solution {
    string concat(vector<string>& w) {
        string ans;
        for (auto& s : w) {
            ans += move(s);
        }
        return ans;
    }
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        return concat(word1) == concat(word2);
    }
};

时间复杂度: O(sum(word1[i].length) + sum(word2[i].length)),
空间复杂度: O(sum(word1[i].length) + sum(word2[i].length)).

1663. Smallest String With A Given Numeric Value

贪心。每次都尽量增加最后一位数。

class Solution {
public:
    string getSmallestString(int n, int k) {
        string ans(n, 'a');
        k -= n;
        for (int i = n - 1; i >= 0 && k > 0; --i) {
            const int thisDigit = min(k, 25);
            ans[i] += thisDigit;
            k -= thisDigit;
        }
        return ans;
    }
};

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

阅读全文 »

LeetCode weekly contest 215

发表于 2020-11-15 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
362 / 9683	YoungForest	12	0:35:02	0:04:21	0:13:42	0:30:02 1	null

5601. Design an Ordered Stream

签到题。按照题目要求，用一个数组和指针实现接口。

class OrderedStream {
    vector<string> data;
    int ptr;
    int n;
public:
    OrderedStream(int _n) {
        data.resize(_n);
        ptr = 1;
        n = _n;
    }
    
    vector<string> insert(int id, string value) {
        data[id-1] = move(value);
        vector<string> ans;
        while (ptr <= n && !data[ptr-1].empty()) {
            ans.push_back(data[ptr-1]);
            ++ptr;
        }
        return ans;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(id,value);
 */

时间复杂度: O(n),
空间复杂度: O(n).

5603. Determine if Two Strings Are Close

观察2个字符串接近的操作，发现其充分必要条件为：
组成字符相同，字符的个数排列相同。

class Solution {
    vector<int> cnt(const string &a) {
        vector<int> ans(26, 0);
        for (char c : a) {
            ++ans[c - 'a'];
        }
        return ans;
    }
    string appear(const vector<int>& a) {
        string ans;
        for (int i = 0; i < 26; ++i) {
            if (a[i] != 0) ans.push_back('a' + i);
        }
        return ans;
    }
    vector<int> frequency(const vector<int>& a) {
        vector<int> ans;
        for (int i = 0; i < 26; ++i) {
            if (a[i] != 0) ans.push_back(a[i]);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
public:
    bool closeStrings(string word1, string word2) {
        if (word1.size() != word2.size()) return false;
        auto cnt1 = cnt(word1);
        auto cnt2 = cnt(word2);
        return appear(cnt1) == appear(cnt2) && frequency(cnt1) == frequency(cnt2);
    }
};

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

5602. Minimum Operations to Reduce X to Zero

阅读全文 »

LeetCode biweekly contest 39

发表于 2020-11-15 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
688 / 6047	YoungForest	7	0:16:02	0:03:44	0:11:02 1	null	0:41:26

本周双周赛难度还是很大的，虽然是3456，但三四题我觉得不止5/6分。当然我也只做出前2题。三四题只试图用暴力解法做，但事实证明虽然很接近正确答案了，但还是全部TLE了。

5550. Defuse the Bomb

签到题。使用辅助数组，按照题目要求填充即可。

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        const int n = code.size();
        vector<int> ans(n, 0);
        if (k == 0) {
            return ans;
        } else if (k > 0) {
            for (int i = 0; i < n; ++i) {
                for (int j = 1; j <= k; ++j) {
                    ans[i] += code[(i + j) % n];
                }
            }
            return ans;
        } else {
            k = -k;
            for (int i = 0; i < n; ++i) {
                for (int j = 1; j <= k; ++j) {
                    ans[i] += code[(i - j + n) % n];
                }
            }
            return ans;
        }
    }
};

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

5551. Minimum Deletions to Make String Balanced

枚举每个分割点，删除分割点前所有的b，和分割点后所有的a。找到最小删除数。

class Solution {
public:
    int minimumDeletions(string s) {
        const int n = s.size();
        int ans = n;
        const int totalA = count_if(s.begin(), s.end(), [](char c) -> bool {
            return c == 'a';
        });
        int a = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            ans = min(ans, b + totalA - a);
            if (s[i] == 'a') ++a;
            else ++b;
        }
        ans = min(ans, b + totalA - a);
        return ans;
    }
};

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

阅读全文 »