连续2周成绩还不错，前200。导致美服小号rating都要上2400了，以后打起来会更加需要小心翼翼。

1935. Maximum Number of Words You Can Type

签到题。字符串问题用Python果然没错。光split这一项就值得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        ans = 0
        broken = set()
        for i in brokenLetters:
            broken.add(i)
        def ok(word):
            for c in word:
                if c in broken:
                    return False
            return True
        for word in text.split(' '):
            if ok(word):
                ans += 1
        return ans

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

1936. Add Minimum Number of Rungs

贪心，如果够不到下一级，就在最远的距离上加一个。
需要注意，不能一级一级加，而是用除法一次加完中间缺少的。否则，会TLE（我也因此罚时5min）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) {
        int ans = 0;
        
        int last = 0;
        for (int idx = 0; idx < rungs.size(); ++idx) {
            const int i = rungs[idx];
            if (i - last <= dist) {
                last = i;
            } else {
                ans += (i - last - 1) / dist;
                last = i;
            }
        }
        
        return ans;
    }
};

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

现在双周赛的参赛人数都快赶上周赛了。

1925. Count Square Sum Triples

签到题，暴力枚举所有的组合。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def countTriples(self, n: int) -> int:
        ans = 0
        for c in range(1, n+1):
            for b in range(1, c+1):
                for a in range(1, b+1):
                    if a * a + b * b == c * c:
                        if a == b: ans += 1
                        else: ans += 2
        return ans

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

1926. Nearest Exit from Entrance in Maze

寻找最近的出口。标准的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
27

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        visited = set()
        q = deque()
        start = (entrance[0], entrance[1])
        visited.add(start)
        q.append(start)
        step = 0
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        rows = len(maze)
        cols = len(maze[0])
        def exitCell(cell):
            return (cell[0] == 0 or cell[0] == rows - 1 or cell[1] == 0 or cell[1] == cols - 1) and maze[cell[0]][cell[1]] == '.' and cell != start 
        while q:
            s = len(q)
            for _ in range(s):
                current = q.popleft()
                if exitCell(current): return step
                for di, dj in directions:
                    ni = di + current[0]
                    nj = dj + current[1]
                    if ni >= 0 and ni < rows and nj >= 0 and nj < cols and maze[ni][nj] == '.' and (ni, nj) not in visited:
                        visited.add((ni, nj))
                        q.append((ni,nj))
            step += 1
        
        return -1

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

周赛博客更新一不小心就鸽了3周。因为最近毕业+入职，确实比较忙。中间因为毕业旅行，甚至罕见地鸽了一次周赛和双周赛。
本周算是入职亚马逊之后的第一周，全球排名也惊喜地达到了74名。仔细算算，自己上次周赛进前100名还是243场，也就是大概一个半月前的时间了。
本周后2题都是hard，确实容易拉开距离。

因为我国服rating达到了2460，我担心掉分，因此最近基本都在美服玩耍。美服是个2330的“小号”，基本很难掉分。

1929. Concatenation of Array

签到题。Straight forward。Python竟然可以一行return nums + nums。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(2 * n);
        for (int i = 0; i < n; ++i) {
            ans[i] = ans[i+n] = nums[i];
        }
        return ans;
    }
};

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

1930. Unique Length-3 Palindromic Subsequences

因为回文串的长度比较短，只有3. 因此，最多有26*26种回文串。可以用中间和两侧的字符表示这个回文串。
因为是subsequence，需要用cntLeft和cntRight维护两侧字符是否满足要求。

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

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<vector<bool>> seen(26, vector<bool>(26, false));
        int ans = 0;
        vector<int> cntRight(26, 0);
        for (char c : s) {
            ++cntRight[c - 'a'];
        }
        vector<int> cntLeft(26, 0);
        for (char c : s) {
            --cntRight[c - 'a'];
            for (char i = 'a'; i <= 'z'; ++i) {
                if (cntRight[i - 'a'] > 0 && cntLeft[i - 'a'] > 0) {
                    if (!seen[c - 'a'][i - 'a']) {
                        ++ans;
                        seen[c - 'a'][i - 'a'] = true;
                    }
                }
            }
            ++cntLeft[c - 'a'];
        }
        return ans;
    }
};

本科毕业时，我写了4年的总结：大学4年复盘. 现在转眼之间3年过去了，我已研究生毕业，即将进入职场。

虽然经历了半年延毕，但最后还是有惊无险的成功毕业了。上周完成了去武汉的毕业旅行，周末回到北京搬家和准备入职。带着对未来美好的期望，我踌躇满志。

硕士3年

3年前，因为本科成绩优异。我最后走上了保研这条看似光鲜亮丽的路。
虽然经历了诸多坎坷和焦虑，但我并不后悔这样的选择。
对于我这样的小镇做题家，这样的结果和发展道路属实更加稳妥，风险更低，收益也相对可观。

回顾研究生这3年，我有很多事情没有干成功。

研一上被老板派去文远知行实习，工作还算辛苦和圆满，但最后不欢而散。其实一开始就不愿意去，迫于牛老板的淫威。见我的吐槽。短期挣到了每月3k的工资，长期浪费了时间。
研一下转做水科院项目，因为甲方扯皮和技术储备不足，最后成了一个深坑，不了了之了。
研一除了帮牛老板干活外，还需要上课。把毕业需要的学分都修完。因为时间精力分散和重要程度降低的原因，我成绩并没本科好。不过也没人在乎这个成绩。
研二下+研三，一直在写小论文和大论文。小论文修改数十次，投稿3次，2次被拒，一次被老板嫌弃会议级别而撤稿，均以失败告终。大论文被老板多次贬低，吓的毕不了业。然而答辩时，和其他同学一对比，发现自己的工作做的其实很不错。

也干成了自己想干的一些事儿。

研二上去比利时交换，体验了一下留学生活，并且把欧洲几乎玩了一个遍。事后证明，这确实是很幸运的。因为第二年，就爆发了全球性的新冠疫情。旅游变成了一项不可能的活动，尤其是出国旅行。
在交换的过程中，与npy相识、相知、最后相恋。也算是一段美妙的姻缘。
研二暑假通过亚马逊的远程实习，之后顺利拿到了亚马逊的offer。也算是稍稍弥补了因为突如其来的疫情而不能去谷歌的遗憾。

未来憧憬

马上就要进入职场，成为一名光荣的打工人了。
给自己职业规划的几点忠告：

终于毕业了，筹划了许久的毕业旅行也正式提上议程。因为要等npy考完试，而且入职前要回来，最好还有几天休息和置办家具。我和npy只有1周时间旅行。共去了3个地方，山西临汾->湖北武汉->湖北随州。
目的大概是见我的家长，看望npy十年没见的奶奶。

6/24 Day 0

这天领毕业证，收拾宿舍并退宿，送走了舍友，晚上等npy考完试，然后去十里堡看房。回学校取旅行行李，然后去火车站附近的酒店。洗漱完就已经1点多了，亲热好久才睡觉。毕竟距上次开房已经2个半月了，还是npy生日出去的。

6/25 Day 1

中午睡到11点。打车去北京西站，虽然离得很近，但还是开车前10分钟才上了车。
坐D2003到达襄汾西站。爸爸和小爸来接，一起去风情街的油粉饭馆吃了饭，妈妈和姐姐也来了。

6/26 Day 2

第二天早上在家吃饭，随后2辆车带npy去龙树峪玩。爬山，走了玻璃桥和石头滑梯。
中午回村里接上奶奶，再回城里尉村拉面馆吃大餐。
下午回家休息了2个小时，开车带npy去市里的商场玩。吃了美食城的麻辣拌。

6/27 Day 3

上午在家做饭吃。本来打算做焖面，但因为我买错了豆角。最后做了西红柿鸡蛋手擀面吃。

吃完饭稍事休息，爸爸开车送我们去机场。
乘坐飞机傍晚到达武汉天河机场，坐地铁到汉口站，在附近的宾馆留宿。

继续保持好成绩，尤其是最后一题，还是挺难的。刚开始没有思路甚至想放弃，但最后还是靠自己的思考解决了难题。

1893. Check if All the Integers in a Range Are Covered

签到题。对于[right, right]中每一个数，判断是否被ranges中的某个区间包含。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        auto cover = [&](const int i) -> bool {
            for (const auto& range : ranges) {
                const int l = range[0], r = range[1];
                if (l <= i && i <= r) return true;
            }
            return false;
        };
        for (int i = left; i <= right; ++i) {
            if (!cover(i)) return false;
        }
        return true;
    }
};

时间复杂度: O((right - left) * ranges.length),
空间复杂度: O(1).

1894. Find the Student that Will Replace the Chalk

先求前缀和，把k和和取余数，可以定位到最后一轮的遍历。然后用二分搜索寻找恰好大于k的位置，即为需要更换粉笔的学生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    using ll = long long;
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        const int n = chalk.size();
        vector<ll> presum(n + 1);
        presum[0] = 0;
        for (int i = 0; i < n; ++i) {
            presum[i+1] = presum[i] + chalk[i];
        }
        if (k >= presum.back()) {
            k = k % presum.back();
        }
        // the first index, presum[i] > k
        auto it = upper_bound(presum.begin(), presum.end(), k);
        return distance(presum.begin(), it) - 1;
    }
};

时间复杂度: O(N + log N), N = chalk.length,
空间复杂度: O(chalk.length).

零神大数据：
1897,Redistribute Characters to Make All Strings Equal,redistribute-characters-to-make-all-strings-equal,1309.1422268153
1898,Maximum Number of Removable Characters,maximum-number-of-removable-characters,1912.8440554296
1899,Merge Triplets to Form Target Triplet,merge-triplets-to-form-target-triplet,1635.6879273926
1900,The Earliest and Latest Rounds Where Players Compete,the-earliest-and-latest-rounds-where-players-compete,2454.7653333657

今天的周赛翻车了。第二题一开始算错时间复杂度了，一直妄图找到更优算法。之后看到80人提交才重新审视二分暴力的时间复杂度，竟然是没问题的。实现过程中又遇到1次WA（判断子序列时，相等字符忘记更新s的下标了），2次TLE（标记remove下标不能用unordered_set, 而要用vector。算是被卡常数了)。这周又要残酷打卡了，幸运的是，因为前2周的成绩比较好，本周残酷榜更新后我的排名不降反升。

1897. Redistribute Characters to Make All Strings Equal

签到题。本质是判断所有的字符是否可以平均分配到n个单词中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        const int n = words.size();
        vector<int> cnt(26, 0);
        for (const auto& word : words) {
            for (char c : word) {
                ++cnt[c - 'a'];
            }
        }
        for (int i : cnt) {
            if (i % n != 0) return false;
        }
        return true;
    }
};

时间复杂度: O(sum(words[i].length)),
空间复杂度: O(1).

1898. Maximum Number of Removable Characters

最优化问题转判定问题（双指针判断是否是子序列），二分搜索。

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

class Solution {
    using ll = int;
    vector<bool> mark = vector<bool>(1e5);
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        const int n = removable.size();
        auto binary = [&](ll lo, ll hi, function<bool(const ll)> predicate) -> int {
            while (lo < hi) {
                ll mid = lo + (hi - lo) / 2;
                if (!predicate(mid)) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return lo;
        };
        // cout << s.size() << endl;
        // cout << n << endl;
        return binary(0, n + 1, [&](const ll x) -> bool {
            for (int i = 0; i < s.size(); ++i) {
                mark[i] = false;
            }
            for (int i = 0; i < x; ++i) {
                mark[removable[i]] = true;
            }
            int pi = 0, si = 0;
            while (pi < p.size()) {
                while (si < s.size() && (mark[si] || s[si] != p[pi])) ++si;
                if (si == s.size()) 
                {
                    // cout << x << ":false"  << endl;
                    return false;
                }
                // if (s[si] != p[pi]) cout << "impossible" << endl;
                ++si;
                ++pi;
            }
            // cout << x << ":true "<< si   << endl;
            return true;
        }) - 1;
    }
};

下午约了 残酷东神 吃饭，一个rating 2700+的大佬。他本科浙大，在加拿大读研。这个暑假来北京旷视实习。因此我们有机会线下面基。

零神大数据：
1880,Check if Word Equals Summation of Two Words,check-if-word-equals-summation-of-two-words,1187.1641565458
1881,Maximum Value after Insertion,maximum-value-after-insertion,1381.2168789318
1882,Process Tasks Using Servers,process-tasks-using-servers,1979.1112273597
1883,Minimum Skips to Arrive at Meeting On Time,minimum-skips-to-arrive-at-meeting-on-time,2587.8725248485

因为今天陪npy去参加斯巴达比赛，早上不到6点就起了，在外奔波了一天。
比赛前想着休息一下子，就打算睡20min。没想到太累了，闹铃响了自己给关了。因此迟到了10+min，否则我排名还可以更高些。题目不难，也不简单，属于出的比较好的。

零神大数据
1876,Substrings of Size Three with Distinct Characters,substrings-of-size-three-with-distinct-characters,1248.7224675206
1877,Minimize Maximum Pair Sum in Array,minimize-maximum-pair-sum-in-array,1301.3817574010
1878,Get Biggest Three Rhombus Sums in a Grid,get-biggest-three-rhombus-sums-in-a-grid,1897.5516652727
1879,Minimum XOR Sum of Two Arrays,minimum-xor-sum-of-two-arrays,2145.1839952670