YoungForest's blog

本轮是今年的倒数第二轮，也是相对比较简单的一个轮次。
我做出了第3题和1 2题的小数据集。第二题我本身的算法是对的，但是没有正确的评估最大的k的位数，并防止溢出操作，所以字大数据集上WA。第一题其实本身不难，只是我对约数不很敏感，导致错失没有想出更好的解法。总的来说，本轮是我最接近AC的轮次，运气相对不错，也提前1个小时完成了比赛。因为后来实在想不出解法 和 要注意的点了，就放弃了。

Book Reading

暴力法加memo可以直接过。可以我的记忆化写错了，忘记记忆了。导致TLE，损失了不少分数，太可惜 了。
另外，能用long long就不要用int。否则最后的ans会溢出。

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

因为记忆化 的存在，计算的页数最多是1 + 1 / 2 + 1 / 3 + ... + 1 / N = log 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
36
37
38
39
40
41

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
using ll = long long;

int main() {
    ll T;
    cin >> T;
    for (ll iCase = 1; iCase <= T; ++iCase) {
        ll ans = 0;
        ll N, M, Q;
        cin >> N >> M >> Q;
        vector<bool> pages(N + 1, true);
        pages[0] = false;
        for (ll i = 0; i < M; ++i) {
            ll P;
            cin >> P;
            pages[P] = false;
        }
        unordered_map<ll, ll> memo;
        for (ll i = 0; i < Q; ++i) {
            ll R;
            cin >> R;
            ll count = 0;
            if (memo.find(R) != memo.end()) {
                count = memo[R];
            } else {
                for (ll j = 1; j * R <= N; ++j) {
                    if (pages[j * R]) {
                        ++count;
                    }
                }
                memo[R] = count;
            }
            ans += count;
        }
        cout << "Case #" << iCase << ": " << ans << endl;
    }
}

The Equation

本题要注意的点相对比较多，本身算法并不难。

1. long long 常数是1L。否则1默认 是int，会有溢出风险。
2. 我们不能从A中的最高位开始找，因为可能k会是更大的数。而应该从 M的角度考虑k的最大值，这里M是15位的，对应二进制50位。然而，我们同样不能从太高的位开始找，否则 N*( 1<<i )会溢出64位。鉴于N最大是1000，二进制10位。我们可以从50~53位开始找。

因为要最大化k，所以我们可以使用贪心的思路，从高位向低位数，尽量放置1，否则放置0，超过要求回溯。

1221. Split a String in Balanced Strings

理解balanced的定义，发现只需要找到 L 和 R 出现个数相等的位置即可。

Time complexity: O(N),
Space complexity: O(1).

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

impl Solution {
    pub fn balanced_string_split(s: String) -> i32 {
        let mut ans = 0;
        let mut l = 0;
        let mut r = 0;
        for c in s.chars() {
            match c {
                'L' => { l += 1},
                'R' => { r += 1},
                _ => (),
            }
            if l == r {
                ans += 1;
            }
        }
        ans
    }
}

1222. Queens That Can Attack the King

虽然理解题目稍微复杂些，但算法其实很直接，从King往外找，而不是从queue开始找。

时间复杂度: O(queens.len() + chessboard.len()),
空间复杂度: O(queens.len()).

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

pub fn queens_attackthe_king(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
    let mut qs: HashSet<(i32, i32)> = HashSet::new();
    for queen in queens.iter() {
        qs.insert((queen[0], queen[1]));
    }
    let mut ans: Vec<Vec<i32>> = Vec::new();
    let direction = vec![
        (0, 1),
        (1, 1),
        (1, 0),
        (1, -1),
        (0, -1),
        (-1, -1),
        (-1, 0),
        (-1, 1),
    ];
    let k = (king[0], king[1]);
    for (x, y) in direction.iter() {
        let mut target: (i32, i32) = k;
        loop {
            target.0 += x;
            target.1 += y;
            if target.0 >= 0 && target.0 < 8 && target.1 >= 0 && target.1 < 8 {
                if qs.contains(&target) {
                    ans.push(vec![target.0, target.1]);
                    break;
                }
            } else {
                break;
            }
        }
    }
    ans
}

1223. Dice Roll Simulation

有memoization的dfs。

赛后补题。

1207. Unique Number of Occurrences

Record the number of occurrences of each value by unordered_map.
Check the unique using unordered_set.

Time complexity: O(N),
Space complexity: O(N).

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

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_set<int> count;
        unordered_map<int, int> seen;
        for (int i : arr) {
            ++seen[i];
        }
        for (const auto& p : seen) {
            if (count.find(p.second) != count.end()) {
                return false;
            } else {
                count.insert(p.second);
            }
        }
        return true;
    }
};

1208. Get Equal Substrings Within Budget

Sliding window.
Use a sliding window to represent the available substring.

Time complexity: O(N),
space complexity: O(1).

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

class Solution {
public:
    int equalSubstring(string s, string t, const int maxCost) {
        int left = 0, right = 0;
        // window: [left, right), length = right - left
        int cost = 0;
        int ans = 0;
        while (left < s.size()) {
            while (right < s.size() && cost + std::abs(s[right] - t[right]) <= maxCost) {
                cost += std::abs(s[right] - t[right]);
                ++right;
                ans = max(ans, right - left);
            }
            cost -= std::abs(s[left] - t[left]);
            ++left;
        }
        return ans;
    }
};

1209. Remove All Adjacent Duplicates in String II

上周五赶上了9月27日比利时的法语区节日，学校放假，连上周末，我们恰好有3天的假期。在上上周从阿姆斯特丹回来的火车上，我们就定下了本次的去巴黎之旅。本次旅行的成员有：我、zfn、lsd、wyd。

总的感受是：我太喜欢巴黎了，我爱巴黎.
在这里，我深刻地感受到法国的文化自信。

来到欧洲安顿下来的第一周，我们去了美丽的荷兰-阿姆斯特丹和周围的2座村庄。
由于是第一次出来玩，许多行程安排的有问题，花费也相对不菲。人均大概450欧。相比之下，一周之后的巴黎之旅只花了300欧，并且体验也更棒。
我认为荷兰绝对是欣赏北欧乡村风光的最佳地点。

本次成行人员：zfn, lxf, lsd, zjz（张导）和 我。

第一天 落脚羊角村

第一天大多数 时间 都 花在路上了。因为张导住在鲁汶，所以我们选择在布鲁塞尔集合。因为是第一次出行，中间误了一趟车，并且开启了本次旅行的首次奔跑，为了帮张导赶车，在站台上3个人提着行李狂奔。鉴于之后的为了赶行程狂奔，本次狂奔只能算是前菜。
吸取 的教训是，安排行程要量力而为，不要对自己和队友太过自信。
由于 中途大量 时间浪费在火车站和等人上，我们晚上11点 才到达羊角村预定的民宿。最后的民宿离镇上有10min的车程，我们有5个人，打车不方便，最后打了一辆7座的车。开车的司机脾气也比较火爆，对我们换车貌似有些不满，开的比较猛，大家纷纷晕车。虽然路途颠簸，但到达 民宿后，感觉一切都是值得的。

首先，house的女主人超级nice。到达 鸟不拉屎的住处后，我先下车，和女主人聊了起来。因为她下腹比较胖，我很友善地问她是不是pregnant了？本想着和女主人套套近乎。没成想，女主人回复 不不，她已经有3个男孩子了。瞬间气氛变得很尴尬。不过女主人并不放在心上，继续很愉快的招待起我们。

在这里，我看到了多年未见的银河，甚至 有幸看到流星。也足见这里的偏僻程度。我们开心地就像一群孩子一样，在后院里看了一个多小时银河。银河真是太美了，我们这样的星空震撼的哇哇叫。自从大概 上小学后，我就再也没能亲眼看到银河了。足以原谅我的激动。天空真的是分外清澈，银河和各个星座清晰可见。随着我们在外面呆的时间越长，眼睛对光线越发适应，看到的星空越美。洁白的月亮也出现在地平线上，并不与银河争光，所以银河就像一道牛奶的带子一样清晰可见。难怪叫做milky way. 因为照片拍不出银河的效果，只有肉眼可见，才能感受到震撼和美。

第二天 阿姆斯特丹

高空秋千。
游船。
集市。
啤酒博物馆。
逛街。
海鲜大餐。
红灯区。

第三天 风车村

风车村
梵高博物馆

上周末在比利时，比赛时间是凌晨的4点半到6点，时间不合适，所以就没有参加。发现只有双周赛的时间是周六的下午4点半到6点，稍微合适些。ranking 2000的目标今年怕是要鸽了。最好的情况下，参与比赛的数目也只有国内的1/3.

1189. Maximum Number of Balloons

统计每个字母的频数即可。需要注意的是，l和o 需要2次才能组成一个ballon。

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

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

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        const string once = "ban";
        const string twice = "lo";
        vector<int> count(26, 0);
        for (char c : text) {
            ++count[c - 'a'];
        }
        int ans = numeric_limits<int>::max();
        for (char c : once) {
            ans = min(ans, count[c - 'a']);
        }
        for (char c : twice) {
            ans = min(ans, count[c - 'a'] / 2);
        }
        return ans;
    }
};

1190. Reverse Substrings Between Each Pair of Parentheses

因为字符串的最大长度为2000，使用暴力法即可。用一个栈来进行括号匹配。

时间复杂度: O(N ^ 2),
空间负责度: 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

class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); ++i) {
            auto& c = s[i];
            if (c == ')') {
                int begin = st.top();
                st.pop();
                reverse(s.begin() + begin, s.begin() + i);
            } else if (c == '(') {
                st.push(i);
            }
        }
        string ans;
        for (char c : s) {
            if (c != ')' && c != '(') {
                ans.push_back(c);
            }
        }
        return ans;
    }
};

看过discuss之后，发现时间复杂度为O(N)的Solution。
第一遍找到所有匹配的括号，第二遍构造结果字符串。每一个括号像一道传送门一样，改变前进方向的同时，跳到对应的括号那里。

今年的下半年，有幸有机会来比利时交换一学期，大概5个月时间。
这是我首次出国这么长时间。之前也是参加学校的项目，去英国游学了半个月，详情可以看我3年前写的英伦游学所见所思。
接下来，我从城市、生活、学习和旅行四个方面总结我的交换项目。

城市

列日处于比利时的东南部，也是列日省的省会所在，与卢森堡、荷兰和德国接壤，也是比利时法语区第三大城市。很多前往欧洲上学的同学十分担心当地的治安和自身的安全。然而，列日就是一个十分安全的城市。在欧洲，往往越是小城市，越安全。像巴黎和布鲁塞尔相较之下可能遇到危险的概率就更大。我曾经就在布鲁塞尔差点被偷了包。在列日这样的小城市，街上的汽车都会主动为行人让路。有时候，一车公交的人等我过马路，我还有些不好意思，加快了脚下的步伐。虽然欧洲老龄化十分严重，但是列日作为一个大学城，这样的感觉并不明显，年轻人依然很多，整个城市充满活力。

生活

西欧的生活节奏十分慢。一方面因为纬度高的原因，列日很早就天黑；另一方面，欧洲人生活压力小，十分讲究工作和生活的平衡。大多数商店都是6点关门，公共服务设施基本上5点关门，超市8点关门。从国内996的生活状态刚过来时会又些不适应，回来之后也是。

比利时的生活成本在欧洲还是比较高的。欧洲是越靠北、越靠西的地区，越富有生活成本越高。维持最低生活水平的话，大概需要每月700欧元。如果想过的好些，再出去玩一玩，每个月大概需要1000欧元。

西欧的天气在冬天以阴雨连绵为主，经常半个月见不到太阳，真的会影响心情。

学习

本次比赛是我在国内的最后一场了。由于比利时这边时差的原因，每周的周赛是周日的早上4点半到6点。所以我并没有条件参加，只能每周日早上起来补题了。

1184. Distance Between Bus Stops

Two pass。正着走一遍，总共走一遍，然后总的路程减去正的路程就是反的路程。
这里要注意start必须在destination之前，否则要换一下位置。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int total = accumulate(distance.begin(), distance.end(), 0);
        if (start > destination)
            swap(start, destination);
        int clockwise = accumulate(distance.begin() + start, distance.begin() + destination, 0);
        int counterclockwise = total - clockwise;
        return min(clockwise, counterclockwise);
    }
};

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

1185. Day of the Week

经典的日历问题。需要注意的点是 闰年 的处理。

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

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 {
    bool isLeap(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> v = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        vector<int> monthes = {0, 31, 28, 31, 30, 31,30, 31, 31, 30,31,30,31};
        int count = 4;
        for (int i = 1971; i < year; ++i) {
            if (isLeap(i)) {
                count += 366;
            } else {
                count += 365;
            }
        }
        if (isLeap(year)) {
            monthes[2] += 1;
        }
        count += accumulate(monthes.begin(), monthes.begin() + month, 0);
        count += day;
        count %= 7;
        return v[count];
    }
};

总的体验是很开心，收获很大。

很幸运可以参加今年的Byte Camp，我认为这一周的活动是我今年参加过的最有意义的活动了。今年的夏令营共分为3个赛道：工程、算法、和 产品。我参加的是工程赛道。

工程和算法赛道进入夏令营的选拔都是通过笔试和面试完成的。笔试的题目也都一样，就是通过牛客网的平台在线完成。笔试有2次机会，都参加的话取分高的。笔试题目分为基础题（操作系统、计算机组成原理、计算机网络）和编程题。编程题有4题，难度依次递增。我参加的是第一场，AC了前3道，难度大约等于是LeetCode medium，最后一题的难度直接飙升到 ICPC world final的难度，要用费用流的知识。我也没打过ACM，第一次听说费用流，就没做出来。由于笔试答的还行，面试我没参加，直接拿到入营资格了。不过听参加面试的同学反映，面试也挺水的，难度很低。

然后就是夏令营的正式活动了。活动虽然只有一周，但是日程安排的十分紧凑，基本是9 10 6。开幕式是有 AI-lab的主管 李航老师 主持。以前只在网上和书上久闻大名，这次竟然可以见到真人了，还有一起合影的机会。学机器学习的同学应该都听说过他，他的《统计学习方法》也是入门算法岗工作的维几之选。我们每人还获赠他签名的《统计学习方法》一书（工程赛道的同学可能对此不是很感冒，哈哈）。

之后的日程主要分为2天的听课和3天的做项目。课程安排和项目都可以在官网上看到，每天要上7节课之多。课上也是干货满满，每个主题都是字节跳动内部负责相关技术的资深工程师负责讲解，从基础设施架构到前后端，覆盖工程的同学可能感兴趣和从事的所有内容。
算法那边除了请公司内部的大牛之外，还有像 Yoshua Bengio、Oren Etzioni 这样的外部嘉宾参与。因为这2个人实在是太牛了（我也是后来才知道的，毕竟不搞算法），我们工程的也被要求参加他们的课程。课程内容倒是一般，比较入门和浅显（难道是为了照顾我们工程的孩子？），实质内容反而不多。

我选择的项目是“服务治理：基于共享内存的高性能通信中间件”。说实话，我对共享内存和进程间通信不是特别熟，但是当时选题目的时候只有这个题目能看懂，其他的题目更是一头雾水，所以选择了“中间件”这一看起来比较靠谱的项目。（后来证明，这样的项目反而不如小游戏这样的项目容易拿奖，也更难完成）。项目的具体细节就不便透露了。我和交大的一位大佬一起完成，3天的时间里，完成了设计、实现、测试、性能测试、PPT和展示。别的组都是4～5人，我们组因为有2个队友提前退营了，只有2人。这3天的代码不是我写的最难的，但算是我这一年来写的最开心的了。白天写一天代码，晚上10点回到酒店里接着肝到一两点。（有五星级酒店住，也是我学校在北京，但仍和大家一起住酒店的原因。标间一晚九百多，很舒服）。我俩甚至把项目开源了：Yellow-Pay/MakeTheAmericanGreatAgain。在GitHub上可以搜到很多shm-ipc的库，我们的目的更多的是为了用git协同工作。

上周五下午刚刚结束夏令营，回学校正式开工，才发现字节跳动的总部中航广场离学校如此之近。本来想坐地铁回来，可是走到知春里的时候发现，学校竟然只有半站路，就直接走回宿舍了。期待以后有机会可以和字节跳动有更多的接触，这么近的距离，偷偷出来实习一定很方便。

题目描述

本题是我2月份Google实习生电话面试遇到的一道题目。我当时做的很混乱，一面直接挂了。今天看到同学发的讲解，决定重新尝试一下这道题目。毕竟自己这半年来刷了有500+道题目，算法实力有一定的增长。我只看到了讲解的题目，并没有看内容，算是自己半年后可以独立解决这个问题了吧。AC后，我竟然都哭了，为当时实力不济而伤心。不知道之后还有那么好的机会吗？
这半年也参加了3次Kick start，除了第一次的A轮收到简历通知外，D轮和E轮都挂了。
就像我之前反复讲的，我很想去Google，微软这样的外企，自己也为之付出了半年的努力。希望努力会有回报吧！如果可以拿到明年暑期的Google或微软的暑期实习，我就奖励自己一次端午节假期去韩国的自由行。有青梅竹马在那里，可以去找她。

本题的思路是这样的:

首先暴力的O(N^2)解法很简单.
枚举所有的起点，从起点出发模拟循环的过程。
可以用2个前缀和数组gas_prefix和cost_prefix追踪油量和花费，保证油量永远大于等于花费。

然后尝试进一步的优化，思考不同起点之间的信息是否可以互相利用。
观察有, 如果在第i个加油站油量小于花费了，则从起点到i（包含）的加油站都不必作为起点尝试了。因为如果起点 < j <= i，则j作为起点，到i时的gas_prefix = 旧起点的gas_prefix - 旧起点到j的gas_prefix, 同理cost_prefix = 旧起点的cost_prefix- 旧起点到j的cost_prefix. 因为旧起点到j是成功的，所以有旧起点到j的gas_prefix >= 旧起点到j的cost_prefix, 所以gas_prefix还是小于 cost_prefix。j就不用尝试了，可以直接跳过。
所以我们有了在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 canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        const int n = gas.size();
        vector<int> gas_prefix(n);
        vector<int> cost_prefix(n);
        for (int begin_index = 0; begin_index < n; ) {
            int i = 0;
            for (; i < n; ++i) {
                if (i == 0) {
                    gas_prefix[i] = gas[(begin_index + i) % n];
                    cost_prefix[i] = cost[(begin_index + i) % n];
                } else {
                    gas_prefix[i] = gas_prefix[i - 1] + gas[(begin_index + i) % n];
                    cost_prefix[i] = cost_prefix[i - 1] + cost[(begin_index + i) % n];
                }
                if (gas_prefix[i] < cost_prefix[i]) {
                    begin_index += i + 1;
                    break;
                }
            }
            if (i == n) {
                return begin_index;
            }
        }
        return -1;
    }
};