YoungForest's blog

发表于 更新于 分类于 Disqus：

我字节跳动提前批投了 技术中台 的 后端开发岗位。
计算机基础没复习到位，答得不好。
许愿offer。

一面

我自介绍。

算法题

先给暴力解，再优化。

题目：数组代表股票每天价格，每天只允许买或者卖一次，也可以不买卖，需要先买入才能卖出，在只交易一次（即只买和卖一次）的情况下求最大收益。
输入：[2,1,4,1,5,6,1]
输出： 5

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
#include <iostream>
#include <vector>
using namespace std;

int solution(const vector<int>& prices) {
    // time: N ^ 2
    // space: 1
    int ans = 0;
    for (int buy = 0; buy < prices.size(); ++buy) {
        for (int sell = buy + 1; sell < prices.size(); ++sell) {
            int profit = prices[sell] - prices[buy];
            ans = max(ans, profit);
        }
    }
    return ans;
}

int solution2(const vector<int>& prices) {
    // time: O(N)
    // space: 1
    int ans = 0;
    if (prices.empty()) return 0;
    int minPrices = prices[0];
    for (int sell = 1; sell < prices.size(); ++sell) {
        int profit = prices[sell] - minPrices;
        ans = max(ans, profit);
        minPrices = min(minPrices, prices[sell]);
    }
    return ans;
}

int main() {
    //int a;
    //cin >> a;
    //cout << a << endl;
    vector<int> prices = {2,1,4,1,5,6,1};
    cout << solution2(prices) << endl;
}

计算机基础

操作系统

IPC 种类
信号量

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
448 / 8571 YoungForest 14 1:22:34 0:07:28 0:11:43 null 1:17:34 1

最后一题debug耽误了不少时间，最后发现是range函数的cache写错了，修改了函数的参数。以后切记memo时要把参数写成const的。
第三题，没有想到效率比较高的DP解法，一直TLE。

1475. Final Prices With a Special Discount in a Shop

寻找下一个大于的数。使用单调递增栈解决。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> increasing;
        const int n = prices.size();
        vector<int> ans(n);
        for (int i = n - 1; i >= 0; --i) {
            while (!increasing.empty() && increasing.top() > prices[i]) {
                increasing.pop();
            }
            if (increasing.empty()) {
                ans[i] = prices[i];
            } else {
                ans[i] = prices[i] - increasing.top();
            }
            increasing.push(prices[i]);
        }
        return ans;
    }
};

1476. Subrectangle Queries

burte force.

时间复杂度:

  • updateSubrectangle: O((row2 - row1) * (col2 - col1)),
  • getValue: O(1).
    空间复杂度: O(rows * cols).
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
1854 / 13794 YoungForest 12 1:18:35 0:15:31 0:12:31 1:18:35 null

最近比赛能力有所下降，昨晚的双周赛也是有一道第3题没做出来，现在更是最后一题没做出来。对Q4的树上倍增算法不了解。

1480. Running Sum of 1d Array

签到题，一遍presum求和。
也可以使用STL 中的partial_sum，达到相同的效果。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> presum;
        presum.reserve(nums.size() + 1);
        presum.push_back(0);
        for (int i : nums) {
            presum.push_back(presum.back() + i);
        }
        presum.erase(presum.begin());
        return presum;
    }
};

1481. Least Number of Unique Integers after K Removals

贪心。
按照频数从小到大排序，先删除小的。

时间复杂度: O(N + N log N + K),
空间复杂度: 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
class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> count;
        for (int i : arr) {
            ++count[i];
        }
        vector<int> frequence;
        frequence.reserve(count.size());
        for (const auto& p : count) {
            frequence.push_back(p.second);
        }
        sort(frequence.begin(), frequence.end());
        int i = 0;
        const int n = frequence.size();
        if (i == k) return n;
        for (int j = 0; j < frequence.size(); ++j) {
            i += frequence[j];
            if (i == k) {
                return n - j - 1;
            } else if (i > k) {
                return n - j;
            }
        }
        return 0;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
374 / 13805 YoungForest 18 0:53:48 0:07:19 0:07:35 0:15:00 0:43:48 2

本周的题目不算难，3456手速场，最后1k人AK。
前3题自己手速还算快，最后一题花了比较长的时间，还因为实现问题TLE了2发。本来觉得自己做的还不错，后来看到排名才发现，大家都很强。还需继续努力呀。争取rating进入世界前500.

1470. Shuffle the Array

使用辅助数组，straight forward.

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

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans(2 * n);
        for (int i = 0; i < n; ++i) {
            ans[i*2] = nums[i];
            ans[i*2 + 1] = nums[n + i];
        }
        return ans;
    }
};

1471. The k Strongest Values in an Array

把stronger作为排序函数，对整个arr进行排序即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        const int n = arr.size();
        int m = arr[((n - 1) / 2)];
        sort(arr.begin(), arr.end(), [&](const auto& a, const auto& b) -> bool {
            if (abs(a - m) == abs(b - m)) {
                return a > b;
            } else {
                return abs(a - m) > abs(b - m);
            }
        });
        arr.erase(arr.begin() + k, arr.end());
        return arr;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
231 / 7926 YoungForest 18 0:42:16 0:04:51 0:10:55 0:22:31 1 0:37:16

质量还可以的手速场。有些问题值得思考，只有发现本质，才能迅速解决。

1460. Make Two Arrays Equal by Reversing Sub-arrays

由于对reverse操作的数目不限，我们可以采用这样的策略构造将2个array转成相同的array。用类似select sort的思想，每次reverse可以将一个位置排好序。所以问题转化为，2个数组排好序后是否相等。
C++中vector的==的作用正是如此。

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

1
2
3
4
5
6
7
8
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        sort(target.begin(), target.end());
        sort(arr.begin(), arr.end());
        return target == arr;
    }
};

1461. Check If a String Contains All Binary Codes of Size K

滑动窗口。窗口大小K，判断所有0 - 2^K - 1的二进制是否出现。

时间复杂度: O(s.size()),
空间复杂度: O(1 << K).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasAllCodes(string s, int k) {
        vector<bool> seen(1 << k, false);
        int current = 0;
        for (int i = 0; i < k && i < s.size(); ++i) {
            current = current * 2 - '0' + s[i];
        }
        seen[current] = true;
        for (int i = k; i < s.size(); ++i) {
            current = (current - (s[i-k]-'0') * (1 << (k-1))) * 2 - '0' + s[i];
            seen[current] = true;
        }
        return all_of(seen.begin(), seen.end(), [](const auto& a) -> bool {
            return a;
        });
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (7)
765 / 13283 YoungForest 12 0:27:19 0:02:16 0:12:53 0:27:19 null

本周最后一题着实比较难，涉及概率和组合数学等知识。恰好触及到我的知识盲区，所以没有做出来。对于数学好的同学应该会好很多。

1464. Maximum Product of Two Elements in an Array

签到题。由于nums.size()比较小，所以暴力即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    const int INF = 0x3f3f3f3f;
public:
    int maxProduct(vector<int>& nums) {
        int ans = -INF;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i+1; j < nums.size(); ++j) {
                ans = max(ans, (nums[i] - 1) * (nums[j] - 1));
            }
        }
        return ans;
    }
};

1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

分别找出最大的horizontal和vertical间隔，相乘即可。需要注意，把边界也当作cut处理。
数据类型最好使用long long，因为会有int32的溢出问题。

时间复杂度: O(horizontalCuts.size() * log + verticalCuts.size() * log),
空间复杂度: 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
class Solution {
    using ll = long long;
    const ll MOD = 1e9 + 7;
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        horizontalCuts.insert(horizontalCuts.begin(), 0);
        horizontalCuts.push_back(h);
        verticalCuts.insert(verticalCuts.begin(), 0);
        verticalCuts.push_back(w);
        sort (begin(horizontalCuts), end(horizontalCuts));
        sort (begin(verticalCuts), end(verticalCuts));
        int maxH = 0, maxW = 0;
        for (int i = 1; i < horizontalCuts.size(); ++i) {
            maxH = max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        for (int j = 1; j < verticalCuts.size(); ++j) {
            maxW = max(maxW, verticalCuts[j] - verticalCuts[j-1]);
        }
        ll mxh = maxH;
        ll mxw = maxW;
        return (mxh * mxw) % MOD;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

Reference: C++ Standard Library: A tutorial and reference, Second version Chapter 7.9.2: Creating and Controlling unordered Container

All solutions I found in Google use XOR to generate hashcode of pair, which is totally bad. see why-is-xor-the-default-way-to-combine-hashes. However, the book has given us the best solution, using hash_combine, which is taken from Boost. The solution is much better than XOR when I tested it in Online Judge(Atcoder). I organized the code as a template as follow. You can copy and paste it as much as you can. And it is convenient to change it to fit any custom struct/class.

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
#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    unordered_map<pair<ll, ll>, ll, pair_hash> slopeCount;
    unordered_set<pair<ll, ll>, pair_hash> seen;
    return 0;
}

There is a hash implementation for Tuple. I updated the answer inStackOverflow。Please go there if you need hash tuple.

阅读全文 »

发表于 更新于 分类于 Disqus：

今天在做一道AtCoder的题目，有个test case一直TLE。研究这个测试用例和其他用例的区别，苦思不得其解。后来把unordered_map换成map就过了。虽然在小数据集上hashmap和treemap区别不大，但数据量大的话，hashmap还是好些。所以最佳实践是，在不需要排序特性时，就用hashmap。
而且之前也从来没有遇到过hashmap比treemap效果差这么多的原因。最后花了一上午时间，才定位到是我的 pair 的hash函数实现太糟糕了。因为C++ STL中并没有pair的hash特化，所以如果想把pair当作键用在unordered_map中的话，就需要自己实现hash函数。我直接从网上抄了一个实现, 直接将 std::hash<T>()(pair.first) ^ std::hash<U>()(pair.second)。为了避免误人子弟，我就不贴代码了。正是抄的这个实现害苦我了，hash函数碰撞严重，导致效率低下。令人惊讶的是，这种错误的实现遍布全网，无论是中文的还是英文的。我从犄角旮旯（stackoverflow问题的评论区中）里才找到问题所在和正确的实现。所以特意总结此博文，避免更多的同学踩坑。

std::hash()(x.first) ^ std::hash()(x.second); - that’s a spectacularly collision-prone way to hash a pair, as every pair with two identical value hashes to 0, and every pair {a, b} hashes the same as {b, a}. For vaguely demanding use, much better to find a hash_combine function and employ that.

惊讶的是，一看到这个评论，我就像中电一样。忽然记起，多年前，当我还是一只小白时，读《C++ 标准库（第二版）》时，作者就已经给出了绝佳的解决方案。我匆忙翻出珍藏的《C++ 标准库（第二版）》的unordered_map对应章节，“7.9.2 Creating and Controlling Unordered Container"，把任意结构hash化的代码搬出来，模版如下：

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
#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    unordered_map<pair<ll, ll>, ll, pair_hash> slopeCount;
    unordered_set<pair<ll, ll>, pair_hash> seen;
    return 0;
}

也有Tuple版本的hash实现，我更新回答在了StackOverflow。有需要的同学可以自取+点赞。

修改了hash_pair的实现后，我如愿地AC了。一个hash函数的错误，我花了一上午时间解决。并由此从多年前的学习经验中获益。当时我苦读《C++标准库》时，并没有对这段代码特别注意。由此可见，多读书总是没坏处的。

平时因为Google搜索很方便，遇到问题总是倾向于简单地 复制粘贴。通常情况下，问题就解决了。这样固然可以更快地完成任务，效果也不错。但这种不求甚解的思想对自己的成长是十分不利的。所以需要遇到问题深入钻研（当然是在时间足够的情况下），多读一些经典的书。很多问题和解决方案，经典的书本都已给出了。读书也更能启发自己思考和成长。本次的pair的 unordered_map实践就是最好的证明。

阅读全文 »

发表于 更新于 分类于 Disqus：

昨晚老爸帮我掏耳朵，一不小心掏出了血。今天一大早就去地区医院检查，还好并无大碍，只损伤了外耳道，休息一周，自然痊愈就好了。只要不感染，就没问题。开了些阿姆西林吃了。
所以鸽了周赛，赛后补题。

1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

C++没有自带的切割字符串的方法，不过可以用自己的模版。通过stringstream实现分割，O(N)的复杂度.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    vector<string> splitSentence(const string& text) {
        string tmp;
        vector<string> stk;
        stringstream ss(text);
        while(getline(ss,tmp,' ')) {
            stk.push_back(tmp);
        }
        return stk;
    }
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        auto words = splitSentence(sentence);
        for (int i = 0; i < words.size(); ++i) {
            if (words[i].find(searchWord) == 0) return i + 1;
        }
        return -1;
    }
};

1456. Maximum Number of Vowels in a Substring of Given Length

滑动窗口。窗口大小为k，统计窗口内的vowels。

时间复杂度: O(N),
空间复杂度: 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 {
public:
    int maxVowels(string s, int k) {
        int count = 0;
        unordered_set<int> vowels = {
            'a', 'e', 'i', 'o', 'u'
        };
        for (int i = 0; i < k; ++i) {
            if (vowels.find(s[i]) != vowels.end()) {
                ++count;
            }
        }
        int ans = count;
        for (int i = k; i < s.size(); ++i) {
            if (vowels.find(s[i]) != vowels.end()) {
                ++count;
            }
            if (vowels.find(s[i-k]) != vowels.end()) {
                --count;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

1457. Pseudo-Palindromic Paths in a Binary Tree

阅读全文 »

发表于 更新于 分类于 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

上个月因为Round B结果还不错，收到了Google CN HR的Congraduation邮件。本月再接再厉，为了进入Google的梦想而努力。

A. Countdown

One pass. 寻找countdown的模式。由于开始数字一定为K，所以countdown的过程中如果失败了的话，可以直接从失败的位置继续寻找。

时间复杂度: 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 <bits/stdc++.h>

using namespace std;

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

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

    return 0;
}

B. Stable Wall

题目本身比较难懂。但实质就是一个拓扑排序的问题，下面的必须先放。
这里需要注意一个corner case：只有一行的情况。
因为我第一版的代码，更新seen是在判断上下层关系时更新的。如果只有一行的话，就会忽略第一行的字母。
把seen单独拿出来更新就可以了。

时间复杂度: O(R * C * 26),
空间复杂度: O(R * C + 26).

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

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

    for (int iCase = 1; iCase <= T; ++iCase) {
        int R, C;
        cin >> R >> C;
        vector<string> rows(R);
        for (int i = 0; i < R; ++i) {
            cin >> rows[i];
        }
        string ans;
        // 拓扑排序
        unordered_map<char, unordered_set<char>> out;
        unordered_map<char, unordered_set<char>> in;
        unordered_set<char> seen;
        queue<char> zeroIn;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                seen.insert(rows[i][j]);
            }
        }
        for (int i = 0; i + 1 < R; ++i) {
            for (int j = 0; j < C; ++j) {
                char down = rows[i + 1][j];
                char up = rows[i][j];
                if (down == up)
                    continue;
                out[down].insert(up);
                in[up].insert(down);
            }
        }
        for (char c : seen) {
            if (in[c].empty()) {
                zeroIn.push(c);
            }
        }
        while (!zeroIn.empty()) {
            char base = zeroIn.front();
            zeroIn.pop();
            ans.push_back(base);
            for (char up : out[base]) {
                in[up].erase(base);
                if (in[up].empty()) {
                    zeroIn.push(up);
                }
            }
        }
        cout << "Case #" << iCase << ": "
             << (ans.size() == seen.size() ? ans : "-1") << endl;
    }

    return 0;
}
阅读全文 »
0%