YoungForest's blog

发表于 更新于 分类于 Disqus：

最近经常打kickstart需要include万能头文件bits/stdc++.h，然而，我喜爱的编辑器vs code总是不能正确地找到该头文件，会有红色波浪线表示错误。作为程序员的我完全不能忍受，所以尝试解决该问题。在网络上搜了很多解决方案，大多数并不能直接地解决我的问题。所以，我总结自己的解决方案于此，方便各位取用。

编程环境:
g++ 9.1.0, Mac 10.14.2, vs code 1.45.1

总的思路是:

  1. 寻找gcc编译器头文件的路径,
  2. 更改VS Code设置，让其用上面的路径可以找到bits/stdc++.h
1
gcc-9 -v -E -x c++ -

gcc include path

图中所示，就是编译器默认找的路径顺序。将这些路径全部加到vscode的includePath里。

vscode-include-path

vscode-settings

Done!

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
484 / 13036 YoungForest 19 1:27:45 0:11:20 0:19:20 1 0:08:48 1:22:45

本周的最后一题是一个经典的计算几何问题，并不好写。不过通过率还是很高的，可能是test case比较弱的原因。

在残酷群的排名降到了32名，跌幅达100%。之前感觉自己变强了错觉，是由于3周前的186周赛取得了113的好成绩，所以按照群排名算法，之后3周的排名都比较高。最好的一次成绩过去后，排名就恢复了本来的水平。30左右。并不是自己变强了，而是运气好而已。而且186正好用的python，python确实对手速场有优势。

1450. Number of Students Doing Homework at a Given Time

签到题，One Pass.

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

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int ans = 0;
        for (int i = 0; i < startTime.size(); ++i) {
            if (startTime[i] <= queryTime && queryTime <= endTime[i]) ++ans;
        }
        return ans;
    }
};

1451. Rearrange Words in a Sentence

利用C++ STL提供的排序函数。

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

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
115 / 7795 YoungForest 19 0:33:49 0:03:55 0:08:25 0:11:57 0:28:49 1

上上周是五一假期，鸽了一场双周赛。之后还是会尽量参加的。最近比赛越来越顺手了，无论是每次的排名，还是rating，或是残酷群的排名。比之前都有所上升。尤其要感谢残酷群的每日一题和不定时的讲座，让我对DP和很多Hard的题目有了解决的信心。在此，再次安利一下残酷刷题群.

1446. Consecutive Characters

滑动窗口，维持整个窗口的字母相等。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxPower(string s) {
        const int n = s.size();
        int l = 0, r = 0;
        int ans = 1;
        for (; r < s.size(); ++r) {
            if (s[r] == s[l]) continue;
            else {
                ans = max(ans, r - l);
                l = r;
            }
        }
        ans = max(ans, n - l);
        return ans;
    }
};

1447. Simplified Fractions

枚举所有的分母和分子，并判断是否是最简形式。幸运的是，C++17已经内置提供gcd函数。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for (int down = 2; down <= n; ++down) {
            for (int up = 1; up < down; ++up) {
                if (gcd(up, down) == 1) {
                    ans.push_back(to_string(up) + "/" + to_string(down));
                }
            }
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
445 / 12715 YoungForest 19 1:14:29 0:07:04 0:17:33 0:56:49 1:14:29

Rating 稳定在2200+2周了，虽然本周的rating还没有更新，但根据排名应该是会继续升的。争取早日到达2300+的分数线。最近刷题遇到了瓶颈，很多hard的题目还是不会做，也没有总结出自己刷题的模版和类别。我发现很多大佬之所以很强，是因为看到题目描述，可以很快地发现该题目属于具体的哪类，迅速和之前做过的题目建立联系，才能又快又bug free的AC。

1441. Build an Array With Stack Operations

One pass. 2个下标分别指向target的位置和n中的位置。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        int i = 1;
        int index = 0;
        vector<string> ans;
        for (; i <= n && index < target.size(); ++i) {
            if (target[index] == i) {
                ans.push_back("Push");
                ++index;
            } else {
                ans.push_back("Push");
                ans.push_back("Pop");
            }
        }
        return ans;
    }
};

1442. Count Triplets That Can Form Two Arrays of Equal XOR

本题需要利用 异或 的一个性质。a ^ a = 0, a ^ b = b ^ a, (a ^ b) ^ c = a ^ (b ^ c). 即 自反律，交换律，结合律。
所以可以根据类似 presum 的操作在O(1)的时间里算出整个区间的异或值。
然后枚举 所有三元组，找到符合条件的。

时间复杂度: O(N ^ 3),
空间复杂度: O(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
25
26
27
28
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        // Time: O(n ^ 3)
        vector<int> prexor(arr.size() + 1);
        prexor[0] = 0;
        // prexor[i]: arr[0] ^ ... ^ arr[i-1]
        for (int i = 0; i < arr.size(); ++i) {
            prexor[i+1] = prexor[i] ^ arr[i]; 
        }
        // [i, j)
        auto xorquick = [&](int i, int j) -> int {
            return prexor[j] ^ prexor[i];
        };
        int ans = 0;
        for (int i = 0; i < arr.size(); ++i) {
            for (int j = i + 1; j < arr.size(); ++j) {
                for (int k = j; k < arr.size(); ++k) {
                    if (xorquick(i, j) == xorquick(j, k + 1)) {
                        ++ans;
                        // cout << "(" << i <a< "," << j << "," << k << ")" << endl;
                    }
                }
            }
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
301 / 12353 YoungForest 19 1:03:24 0:06:34 0:03:07 0:17:30 1:03:24

1436. Destination City

遍历每条边，统计各个点的出度。

时间复杂度: O(path.length * city[i].length),
空间复杂度: O(city.length * city[i].length).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, int> outgoing;
        unordered_set<string> seen;
        for (const auto& v : paths) {
            ++outgoing[v[0]];
            seen.insert(v[0]);
            seen.insert(v[1]);
        }
        for (const auto& s : seen) {
            if (outgoing[s] == 0)
                return s;
        }
        return "";
    }
};

1437. Check If All 1’s Are at Least Length K Places Away

One pass. 记录上一个1出现的位置。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    const int INF = 0x3f3f3f3f;
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int last_one = -INF;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) {
                if (i - last_one - 1 >= k) {
                    last_one = i;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

阅读全文 »

发表于 更新于 分类于 Disqus：

从在牛客网发暑期实习的第一篇面经开始，到现在已经过去近2个月了。中间陆陆续续参加了8个厂的招聘。岗位均为后端/服务器开发。base地点为北京。

失败

字节跳动

一面就凉。字节跳动还是一家和我很有缘分，我也很喜欢的一家公司。去年参加过一次广告系统的暑期实习面试，经历残酷四面。面到lead力哲。最后因为实习时间不合适没去。去年暑假还参加了ByteDance 的夏令营。由于是长久以来的第一次面试，准备不足、发挥也不是很好。算法题 编辑距离 没做出来，遂一面即凉。

微软

找了之前在微软工作的一位师兄，托他又联系到正在微软工作的一位同事，做了内推。18年时曾面过一次苏州微软, 当时水平有限，无奈地凉了。今年踌躇满志，想要一雪前耻。没想到同样翻船了。不过吸取了很重要的经验，不要吹牛打过比赛。
一面面试官问我打过什么比赛吗？我当时作死回答说，打过一些LeetCode、kickstart、codeforces、atcoder。实际上，只有LeetCode我是经常参加周赛，kickstart参加每月的轮次（如果时间合适的话）。其他平台的赛事加起来也只有几场。面试官因此误解了我的实力，认为是cf水平的（实际上，我cf的rating都不到1500）。只问了我系统设计的问题，没有手撕代码，我尽管在LeetCode上刷了900题，也没发发挥。
二面面试官上来就问了2道很难的算法题，感觉是准备给ACM选手的。都怪我一面时吹了牛，二面被安排了。

结束

谷歌

通过了电话一面，但无奈因为疫情的原因，Google中国取消了暑期实习项目。我的面试进程也止于一面了。

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (6) Q4 (7)
113 / 11684 YoungForest 18 0:34:17 0:04:32 0:10:54 0:18:49 0:34:17

手速场。换成Python后，手速场很轻松。真的是人生苦短，我用Python。不过在用Python刷题的过程中，我也发现了一些问题。

  • API不熟悉。比如sorted会返回一个排好序的list，而不是in-place sort.
  • 数据结构不全。如没有treemap，priority_queue只能用heap，代替。最小堆需要把所有数*-1，使用这种丑陋的实现方式。
  • runtime error。在一些手误情况下，会有错误的提交。这时候很考验你的测试用例了，是否覆盖所有的情况和边界条件。

1422. Maximum Score After Splitting a String

brute-force. 2 <= s.length <= 500.

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

另外，如果采取Presum的方式的话，时间复杂度可以降为O(N)。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxScore(self, s: str) -> int:
        def count(s, c):
            ans = 0
            for i in s:
                if i == c:
                    ans += 1
            return ans
        return max(count(s[:x], '0') + count(s[x:], '1') for x in range(1,len(s)))

1423. Maximum Points You Can Obtain from Cards

问题可以转化为：从头取x个，从尾取k-x个 和最大。

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (6) Q4 (7)
703 / 9206 YoungForest 12 0:36:35 0:10:24 0:22:03 0:31:35 1 null

1417. Reformat The String

分别统计数字和字母的个数。如果相差个数不大于1，则可以reformat。
先选多的那类。

时间复杂度: O(N),
空间复杂度: O(N). 可以用双指针的方法，节省存储数字和字母的string的空间。

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 Solution {
    string compose(const string& a, const string& b) {
        string ans;
        int ai = 0, bi = 0;
        if (a.size() > b.size())
            ans.push_back(a[ai++]);
        while (ai < a.size()) {
            ans.push_back(b[bi++]);
            ans.push_back(a[ai++]);
        }
        return ans;
    }
public:
    string reformat(string s) {
        string digit, alpha;
        for (char c : s) {
            if (c >= '0' && c <= '9') {
                digit.push_back(c);
            } else {
                alpha.push_back(c);
            }
        }
        if (digit.size() == alpha.size() || digit.size() + 1 == alpha.size() || alpha.size() + 1 == digit.size()) {
            if (digit.size() >= alpha.size()) {
                return compose(digit, alpha);
            } else {
                return compose(alpha, digit);
            }
        } else {
            return "";
        }
    }
};

1418. Display Table of Food Orders in a Restaurant

考察数据结构的使用。遍历orders，将其转换成dish->table的hashmap，同时用set存储table编号。

时间复杂度: O(orders.length * orders[i].length),
空间复杂度: O(tables.length * dishes.length).

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:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        set<int> tables;
        map<string, unordered_map<int, int>> count;
        for (const auto& p : orders) {
            const int table_number = stoi(p[1]);
            const auto& dish = p[2];
            ++count[dish][table_number];
            tables.insert(table_number);
        }
        vector<vector<string>> ans;
        vector<string> first_row = {"Table"};
        for (const auto& p : count) {
            first_row.push_back(p.first);
        }
        ans.push_back(move(first_row));
        for (int i : tables) {
            vector<string> row;
            row.push_back(to_string(i));
            for (auto& p : count) {
                row.push_back(to_string(p.second[i]));
            }
            ans.push_back(move(row));
        }
        return ans;
    }
};

1419. Minimum Number of Frogs Croaking

阅读全文 »

发表于 更新于 分类于 Disqus：
ID score rank Bike Tour Bus Routes Robot Path Coding Wandering Robot Time
YoungForest 74 524 5 + 7 10 + 13 11 + 16 14 + 0 1:35:18

去年一共参加了6轮kickstart，成功拿到Google今年的实习邀请。可惜的是，由于疫情的原因，谷歌中国的暑期实习项目全部取消了。今年为了秋招名额，仍需继续参加kickstart。今天的round B轮次虽然在早上7点，但仍然有很多同学参加。遗憾的是，最后一题的时间复杂度过高，大的Test set TLE了。

Bike Tour

签到题。遍历一遍mountains, 寻找比前后都高的位置即可。

时间复杂度: O(N),
空间复杂度: O(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
25
26
27
28
29
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T;
    cin >> T;

    for (int iCase = 1; iCase <= T; ++iCase) {
        int N;
        cin >> N;
        vector<int> mountains(N);
        for (int i = 0; i < N; ++i) {
            cin >> mountains[i];
        }
        int ans = 0;
        for (int i = 1; i < N - 1; ++i) {
            if (mountains[i] > mountains[i - 1] &&
                mountains[i] > mountains[i + 1]) {
                ++ans;
            }
        }
        cout << "Case #" << iCase << ": " << ans << endl;
    }

    return 0;
}

Bus Routes

贪心。从后向前，选择每趟公交最晚的那班。

时间复杂度：O(N), 我这里使用了尾递归的写法，和迭代一样，不需要额外的空间。
空间复杂度：O(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
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>

using namespace std;

using ll = long long;

vector<ll> schedule(1005);

int main() {
    int T;
    cin >> T;

    for (int iCase = 1; iCase <= T; ++iCase) {
        int N;
        ll D;
        cin >> N >> D;
        for (int i = 0; i < N; ++i) {
            cin >> schedule[i];
        }
        function<ll(int, ll)> f = [&](int index, ll d) -> ll {
            if (index == 0) {
                return (d / schedule[index]) * schedule[index];
            } else {
                return f(index - 1, (d / schedule[index]) * schedule[index]);
            }
        };
        
        cout << "Case #" << iCase << ": " << f(N-1, D) << endl;
    }

    return 0;
}
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
700 / 7729 YoungForest 18 1:17:49 0:04:50 0:10:38 0:17:45 1:02:49 3

最近参加了2场codforces的比赛，cf的rating徘徊在1400+。cf的题目相对leetcode还是难的多的。并没有坚持下来。这也和cf没有很好的discuss区有关，每届比赛结束后，只能看官方的editorial。

1413. Minimum Value to Get Positive Step by Step Sum

统计presum的最负值，需要注意的是startValue必须是正数。

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

1
2
3
4
5
6
7
8
class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        min_sum = 0
        current_sum = 0
        for i in nums:
            current_sum += i
            min_sum = min(current_sum, min_sum)
        return 1 - min_sum if min_sum <= 0 else 1

1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

贪心，永远选用小于等于i的最大的Fibonacci数，然后递归解决剩余的数。

时间复杂度：O((log k)^2),
空间复杂度: O(log k).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        def findLargestFibonacciLessEqualThan(i):
            a = 1
            b = 1
            while a <= i:
                a, b = a + b, a
            return b
        
        def dp(i):
            x = findLargestFibonacciLessEqualThan(i)
            if x == i:
                return 1
            else:
                return 1 + dp(i - x)
        return dp(k)
阅读全文 »
0%