YoungForest's blog

发表于 更新于 分类于 Disqus：

官方题解

codeforces上题目一般高于平时的面试题。如果是为了面试的话，只刷LeetCode就可以了。不过如果是对算法和竞赛感兴趣，强烈鼓励试一试。题目的数量和质量都远超LeetCode。而且为不同水平的同学有不同的赛道，题目难度也不同。对于高水平玩家来说，竞赛体验会好的多。

我目前共参加过2场Div.2，rating 1480。没错，初始值是1500，我反而掉下来了。

A. Filling Diamonds

可以用动态规划的方式思考这个问题。对于长度为n的belt来说，共有2种状态：


/

和
1.
/
\

状态转移方程有:
dp[n][0] = dp[n-1][1] + dp[n-1][0],
dp[n][1] = dp[n-1][1].

对于初始值有:
dp[0][1] = 1,
dp[0][0] = 0.

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (6) Q4 (7)
589 / 9816 YoungForest 19 0:55:30 0:07:04 0:15:05 0:37:18 1 0:50:30

今天又是一轮手速场。Python告诉我们，“人生苦短，我用Python”。我有2题用Python实现，1和4。事实上，对于第3题，直接调用Python Str API更是如鱼得水，不过我当时选择了用Trie+自动机的方式实现，也活该名次掉下来。

1408. String Matching in an Array

签到题。使用Python Str的find函数确定是否是子字符串即可。

时间复杂度: O(words.length ^ 2 * words[i].length),
空间复杂度: O(words.length * words[i].length).

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = set()
        n = len(words)
        for i in range(n):
            for j in range(i + 1, n):
                if words[i].find(words[j]) != -1:
                    ans.add(words[j])
                if words[j].find(words[i]) != -1:
                    ans.add(words[i])
        return [i for i in ans]

1409. Queries on a Permutation With Key

用List模拟Permutation的变化。
寻找位置时使用顺序查找。

时间复杂度: O(m + queries.length * m),
空间复杂度: O(m + queries.length).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        list<int> P;
        for (int i = 1; i <= m; ++i) {
            P.push_back(i);
        }
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); ++i) {
            auto it = P.begin();
            int position = 0;
            while (it != P.end() && *it != queries[i]) {
                ++it;
                ++position;
            }
            ans[i] = position;
            P.push_front(*it);
            P.erase(it);
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
199 / 7026 YoungForest 19 0:40:57 0:08:05 0:11:44 0:33:38 0:40:57

不难，手速场。发现很多手速场的比赛，第三题甚至都比第四题更难。

1399. Count Largest Group

straight forward. 用一个hashmap统计digit_sum -> count, 最后再找出count最大的几组。

时间复杂度: 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
class Solution {
public:
    int countLargestGroup(int n) {
        unordered_map<int, int> seen;
        int largestSize = 0;
        for (int i = 1; i <= n; ++i)  {
            int sumOfDigit = 0;
            int current = i;
            while (current > 0) {
                sumOfDigit += current % 10;
                current /= 10;
            } 
            ++seen[sumOfDigit];
            largestSize = max(largestSize, seen[sumOfDigit]);
        }
        int ans = 0;
        for (auto it = seen.begin(); it != seen.end(); ++it) {
            if (it->second == largestSize)
                ++ans;
        }
        return ans;
    }
};

1400. Construct K Palindrome Strings

统计出现的奇数字符数目，必需小于等于k。并且因为要求回文串非空，所以需要s.size() >= k。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) return false;
        vector<int> count(26, 0);
        for (char c : s) {
            ++count[c - 'a'];
        }
        int single = 0;
        for (int i : count) {
            if (i % 2 == 1)
                ++single;
        }
        return single <= k;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (6) Q4 (7)
91 / 12542 YoungForest 21 0:39:07 0:09:24 0:15:33 0:29:53 0:39:07

本周又是手速场，足足有800人AK。可能是由于疫情的原因，程序员都wfh（work from home），每次周赛的参加人数都稳步上涨，比我刚回国的时候已经增加一个一倍了。rating掉了有一个月了，这周终于涨上来了，2187，恢复到了最高点。

1403. Minimum Subsequence in Non-Increasing Order

贪心。先排序，试图选大的值，直到累计和超过一半。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        int sumAll = accumulate(nums.begin(), nums.end(), 0);
        vector<int> ans;
        int sumCurrent = 0;
        for (int i : nums) {
            ans.push_back(i);
            sumCurrent += i;
            if (sumCurrent > sumAll / 2) {
                return ans;
            }
        }
        return ans;
    }
};

1404. Number of Steps to Reduce a Number in Binary Representation to One

用字符串模拟“加一”操作，直到为1.
这里我用了一个list来存字符，以方便进位操作。

时间复杂度: 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
class Solution {
public:
    int numSteps(string s) {
        list<char> l(s.begin(), s.end());
        int ans = 0;
        while (l.size() > 1) {
            if (l.back() == '1') {
                auto it = l.rbegin();
                for (;it != l.rend(); ++it) {
                    if (*it == '0') {
                        *it = '1';
                        goto endIf;
                    } else {
                        *it = '0';
                    }
                }
                l.push_front('1');
                endIf: ;
            } else {
                l.pop_back();
            }
            ++ans;
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (8)
727 / 11694 YoungForest 12 0:22:50 0:03:13 0:14:04 0:22:50 null

这周一加了一个LeetCode每日打卡和周赛群。每周出排名，末位发红包；每天做道指定题目，连续2天没做发红包，极其惊现刺激。赛事排行榜。
本次比赛是入群以来的第一次，由于第四题太难了，总共也就一百人做出来。群里也只有5个人AC

1394. Find Lucky Integer in an Array

签到题。注意数据范围，统计frequency即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findLucky(vector<int>& arr) {
        vector<int> count(501, 0);
        for (int i : arr) {
            ++count[i];
        }
        for (int i = 500; i >= 1; --i) {
            if (count[i] == i)
                return i;
        }
        return -1;
    }
};

1395. Count Number of Teams

由于数据规模很小，所以即使是枚举所有3元组的N^3的解法也能过。
在这里，我使用了DP, N^2复杂度的解法。如果使用order statistic tree的话，可以近一步降为N log N.

时间复杂度: 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
24
class Solution {
public:
    int numTeams(vector<int>& rating) {
        auto f = [&](function<bool(int,int)> op) -> int {
            const int n = rating.size();
            vector<vector<int>> large(3, vector<int>(n, 1));
            int ans;
            for (int echo = 1; echo <= 2; ++echo) {
                ans = 0;
                for (int i = 0; i < n; ++i) {
                    large[echo][i] = 0;
                    for (int j = 0; j < i; ++j) {
                        if (op(rating[i], rating[j])) {
                            large[echo][i] += large[echo-1][j];
                        }
                    }
                    ans += large[echo][i];
                }
            }
            return ans;
        };
        return f(greater<int>()) + f(less<int>());
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (4) Q2 (4) Q3 (5) Q4 (6)
1357 / 5632 YoungForest 12 1:27:09 0:05:06 0:48:41 1 1:22:09 null

1385. Find the Distance Value Between Two Arrays

先对arr2进行排序，再对arr1中的每一个元素，利用二分搜索，判断arr2中是否有距离在d中的值。

时间复杂度: O(arr2.size() * log arr2.size() + arr1.size() * log arr2.size()),
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int ans = 0;
        sort(arr2.begin(), arr2.end());
        for (int i : arr1) {
            auto it1 = lower_bound(arr2.begin(), arr2.end(), i - d);
            auto it2 = upper_bound(arr2.begin(), arr2.end(), i + d);
            if (it1 == it2)
                ++ans;
        }
        return ans;
    }
};

1386. Cinema Seat Allocation

贪心。每排尝试放2个family，再尝试放一个family。因为一行10个座位，所以可以用bitmap来表示占用情况。对于没reserverd的行，直接放2个。

时间复杂度: O(reservedSeats.size() * log reserveredSeats.size() + max(n, reservedSeats.size())),
空间复杂度: 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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        sort(reservedSeats.begin(), reservedSeats.end(), [](const auto& a, const auto& b) -> bool {
            if (a[0] == b[0]) {
                return a[1] < b[1];
            } else {
                return a[0] < b[0];
            }
        });
        int ans = 0;
        for (int index = 0, row = 1; row <= n;) {
            unsigned int current_row = 0;
            for (; index < reservedSeats.size() && reservedSeats[index][0] == row; ++ index) {
                current_row |= 1 << (reservedSeats[index][1] - 1);
            }
            current_row = ~current_row;
            if ((current_row & 0b0111111110) == 0b0111111110)
                ans += 2;
            else if ((current_row & 0b0001111000) == 0b0001111000)
                ++ans;
            else if((current_row & 0b0000011110) == 0b0000011110)
                ++ans;
            else if ((current_row & 0b0111100000) == 0b0111100000)
                ++ans;
            if (index < reservedSeats.size()) {
                ans += (reservedSeats[index][0] - row - 1) * 2;
                row = reservedSeats[index][0];
            }
            else {
                ans += (n + 1 - row - 1) * 2;
                row = n + 1;
            }
        }
        return ans;
    }
};

1387. Sort Integers by The Power Value

阅读全文 »

发表于 更新于 分类于 Disqus：

自从LeetCode rating算法更新后，我的rating到达了顶峰，之后就一直向下掉。不过也是因为自己菜，每次都打的大好几百名，偶尔还上千。

Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
839 / 10930 YoungForest 18 1:31:13 0:04:53 0:14:43 1 0:45:27 1 1:16:13 1

1389. Create Target Array in the Given Order

签到题。使用vector的insert接口，缺点是效率有问题，不过对于签到题足够了。

时间复杂度: O(n ^ 2), 最坏情况是 每次都插到首位。
空间复杂度: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> ans;
        const int n = nums.size();
        for (int i = 0; i < n ; ++ i) {
            if (index[i] < ans.size()) 
                ans.insert(ans.begin() + index[i], nums[i]);
            else
                ans.push_back(nums[i]);
        }
        return ans;
    }
};

1390. Four Divisors

Brute force. 计算每个数的因数。

时间复杂度: O(sqrt(nums[i]) * nums.length),
空间复杂的: O(nums.length) -> O(1) without memo.

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
class Solution {
    unordered_map<int, int> memo;
    unordered_map<int, int> sumDivisors;
    int divisors(int x) {
        if (x == 1)
            return 1;
        else {
            if (memo.find(x) == memo.end()) {
                int ans = 2;
                int sum = 1 + x;
                for (int i = 2; i * i <= x; ++i) {
                    if (x % i == 0) {
                        ans += (i * i == x) ? 1 : 2;
                        sum += (i * i == x) ? i : i + x / i;
                    }
                    if (ans > 4)
                        break;
                }
                if (ans == 4) {
                    sumDivisors[x] = sum;
                }
                return memo[x] = ans;
            } else {
                return memo[x];
            }
        }
    }
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int i : nums) {
            if (divisors(i) == 4)
                ans += sumDivisors[i];
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

新一年的kick start有了些许变化：

  1. 所有测试结果正确与否立即返回。之前是大的数据集的测试结果赛后才能看到。相当于是降低了难度，减少了参赛者失误的代价。之前发生一点失误的话，大数据集的分数就没了。现在相当于是增加了一次罚时。
  2. 题目从3到变成了4道，时间不变，增加了一道送分题。

Rank 570. 因为大家都是100分，所以最后比拼的都是时间。因为比赛是12:00~15:00, 所以我中间花了半个小时去吃饭。另外每个题目都不是一遍做对，都通过printf进行调试，花了不少时间。最快的大佬们都是20min就做完了。

下个月约起来round B呀！4月19号早上7点。

round A 题目地址

Allocation

刚开始以为是一道简单的背包问题，后来发现是更简单的贪心问题。因为是要求购买房子数目的最大值，而不是价值的最大值，或者说 房子的价值都为1. 所以贪心即可。简而言之，送分的签到题。
把房子按照售价从小到大排序，先买便宜的房子。

时间复杂度: O(N log 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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> A(100005);

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

    for (int iCase = 1; iCase <= T; ++iCase) {
        int N, B;
        cin >> N >> B;
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        sort(A.begin(), A.begin() + N);
        int ans = 0;
        int index = 0;
        while (index < N && B >= A[index]) {
            B -= A[index];
            ++ans;
            ++index;
        }
        cout << "Case #" << iCase << ": " << ans <<endl;
    }

    return 0;
}

因为贪心的时候忘记检查index < n了，导致一次WA罚时。

阅读全文 »

发表于 更新于 分类于 Disqus：

一面

time: 2020-03-20 16:29:48

上周五参加了在牛客网上的笔试。题目不难，分为计算机基础、算法 和 系统设计。
计算机基础靠着本科的认真学习，没啥问题。算法也属于LeetCode medium难度，很快AC了。
系统设计倒是难倒我了，并不擅长，也没有准备。需要设计一个 MOBA游戏的匹配机制，包括单人和组队。之前完全没想过，瞎写了一通。
昨天收到电话，说我通过了笔试，约了今天下午2:30的电话面试。

本科有个可爱的大佬舍友最后去米哈游了。我虽然对游戏不感冒，但本着多面试，多总结的态度，也报名了其春招内推。

面试预计30min, 实际40min。

自我介绍 + 项目经历 + 计算机基础。

计算机基础又分为：

  • C++
  • 操作系统
  • 数据库
  • 计算机网络
  • 设计模式

我不会的有：

  • TCP 3次挥手，最后的time_wait的作用
  • C++ 父类析构函数为什么必需是虚函数
  • MySQL
    • 事务 及 ACID
    • Block 和 Tag 区别
    • BiLog是什么
    • timestamp, datetime的区别
  • 说出常用的设计模式，我讲了几个，但面试官好像并不满意
阅读全文 »

发表于 更新于 分类于 Disqus：

自从LeetCode更新了周赛rating算法后，结果下我一跳。Rating直接涨到2171，全球排名608/81184, 完成比赛53场。记得上周我还在期望可以近几周突破2000分的，已经1990+了。更新后的算法显示去年8月份就已经2000了。

本周日会村里看望奶奶，由于疫情原因，之前一家人一直未能团聚。今天好不容易，几乎所有人都到场了。周赛也是回老家参加的。由于环境不适合思考，所以结果也差强人意。

Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (4) Q4 (6)
1300 / 10047 YoungForest 11 0:29:31 0:12:20 0:18:26 0:29:31 null

1380. Lucky Numbers in a Matrix

统计每行的最小值所在的列数和每列最大值所在的行数，判断是否有相等的。

时间复杂度: O(m * n),
空间复杂度: O(m + 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:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        const int m =  matrix.size();
        if (m == 0) return {};
        const  int n = matrix[0].size();
        vector<int> row_min_index(m, -1);
        vector<int> col_max_index(n, -1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (row_min_index[i] == -1 || matrix[i][row_min_index[i]] > matrix[i][j]) {
                    row_min_index[i] = j;
                }
                if (col_max_index[j] == -1 || matrix[col_max_index[j]][j] < matrix[i][j]) {
                    col_max_index[j] = i;
                }
            }
        }
        vector<int> ans;
        for (int row = 0; row < m; ++row) {
            if (col_max_index[row_min_index[row]] == row) {
                ans.push_back(matrix[row][row_min_index[row]]);
            }
        }
        return ans;
    }
};

1381. Design a Stack With Increment Operation

用数组实现栈即可。

时间复杂度:

阅读全文 »
0%