YoungForest's blog

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
165 / 12400 YoungForest 18 1:07:14 0:03:22 🐞1 0:16:01 🐞1 0:27:41 🐞1 0:52:14

提前40min AK。虽然因为粗心大意，前三题每题WA一次，导致15min罚时，但好的一点是这周应该不用每天残酷打卡了。正好全力以赴，准备周三的硕士论文答辩。
三年的硕士生涯全靠周三一天了，毕其功于一役，加油，Forest！

1869. Longer Contiguous Segments of Ones than Zeros

签到题。统计连续字串的长度，更新最长长度即可。

因为更新最长长度的代码写错位置，写到了if的分支里，WA了一次。应该无论如何都要更新，所以要写在外面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool checkZeroOnes(string s) {
        vector<int> longest(2, 0);
        int length = 0;
        char last = '2';
        for (char c : s) {
            if (c != last) {
                last = c;
                length = 1;
            } else {
                ++length;
            }
            longest[c - '0'] = max(longest[c - '0'], length);
        }
        return longest[1] > longest[0];
    }
};

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

1870. Minimum Speed to Arrive on Time

直接暴力二分怼。之前总结的binary search模版很好用。基本只需要改几行代码就行了。

因为浮点数精度WA了一次。10^-5 不够小，建议以后都用10^-9。

阅读全文 »

发表于 更新于 分类于 Disqus：

本周周赛和双周赛都翻车了，开始残酷打卡之旅。

Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
717 / 11572 YoungForest 12 0:23:51 0:05:35 0:17:33 0:23:51 null
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
272 / 11577 YoungForest 18 1:15:29 0:04:46 0:14:19 0:47:06 1:10:29 1

这周五一假期+大论文查重。心情被大论文折麽的十分焦虑，再坚持2周，挺过答辩就好了。
等过了答辩，让我干啥都行。

前几周因为国服自己的rating太高，不敢打了，怕掉分。转战了美服，现在把美服也打到2350了。rating也过高了。之后打算再次转战国服，因为最近新一年的招聘迫近，国服赞助商礼物比较丰厚。虽然去年只有几次排名足够靠前，拿到奖品，但好歹有个奖励，有比较小的期望。

阅读全文 »

发表于 更新于 分类于 Disqus：

Mendeley GB/T 7714-2005

  • 针对英文文献中作者名字使用了全大写
  • 针对英文文献中三个以上人名省略时使用了中文的“等”，而不是et al.

Solution

我配置了自己的参考文献格式，在此分享给大家。特色有：

  • 删除参考文献中的 // 。特别是会议后面多出来的这个分隔符

引用知网参考文献

知网上没有Mendeley支持的Bib参考文献格式，因此，我写了一个网站可以在线进行参考文献的转换: 入口1 入口2

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
150 / 9378 YoungForest 18 0:32:04 0:05:26 0:07:22 0:11:24 0:32:04

手速场。最近手速已大不如从前，最后一题也因为不熟练花费了比较多的时间。
其实，手速场中，所有题目的算法其实都不难，想到正确的解法很快，但迅速实现 + bug free就考验每位程序员的功力了。

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
78 / 10870 YoungForest 18 0:52:57 0:02:22 0:09:37 0:27:13 0:47:57 1

连续3周免打卡了，昨晚双周赛也做的不错手速场。
最近的周赛确实难度有所降低，看来我还是适合做简单题目。Hard+还是不大行。

阅读全文 »

发表于 更新于 分类于 Disqus：

比赛时间是北京的19号上午7点到10点，因为恰好下午2点要交毕设初稿。最近忙着一直在写大论文。因此并未参加Round B. 现如今自己已经过了校招的年纪，打Kick Start纯粹是为了娱乐。
赛后补题。

比赛题目链接

Increasing Substring

签到题。DP，只需要和前一个字符比大小。

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
#include <vector>
#include <string>
#include <iostream>

using namespace std;

void solve() {
    int N ;
    cin >> N;
    string s;
    cin >> s;
    vector<int> dp(N);
    for (int i = 0; i < N; ++i) {
        if (i > 0 && s[i] > s[i-1]) {
            dp[i] = dp[i-1] + 1;
        } else {
            dp[i] = 1;
        }
        cout << dp[i] << " ";
    }
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        cout << "Case #" << i + 1 << ": ";
        solve();
        cout << endl;
    }
    return 0;
}

时间复杂度: O(N),
空间复杂度: O(N) -> O(1). 虽然我的实现是O(N)的，但其实dp数组是没必要存的，只关心前一个的值。

Longest Progression

遇到WA，是因为C++类型的原因。列在这里引以为戒。
因为类型转换的原因，size() 和 -1比较时，-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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <map>

using namespace std;

using ll = int;


template <typename T, class Cmp>
ostream& operator <<(ostream& out, const unordered_set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}


template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const unordered_map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}

int solve() {
    int N ;
    cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    if (N <= 3) return N;
    vector<int> diff(N);
    diff[0] = 0;
    for (int i = 1; i < N; ++i) {
        diff[i] = nums[i] - nums[i-1];
    }
    int hi = N + 1;
    int lo = 4;
    auto binary = [&](ll lo, ll hi, function<bool(const ll)> predicate) -> int {
        // return first true
        while (lo < hi) {
            ll mid = lo + (hi - lo) / 2;
            if (predicate(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    };
    auto pred = [&](const ll x) -> bool {
        unordered_map<int, unordered_set<int>> cnt;
        map<int, unordered_set<int>, greater<int>> reverseCnt; // cnt->value, cnt->count
        auto addCnt = [&](const int i) -> void {
            cnt[diff[i]].insert(i);
            reverseCnt[cnt[diff[i]].size()].insert(diff[i]);
            reverseCnt[cnt[diff[i]].size() - 1].erase(diff[i]);
            if (reverseCnt[cnt[diff[i]].size() - 1].empty()) {
                reverseCnt.erase(cnt[diff[i]].size() - 1);
            }
        };
        auto eraseCnt = [&](const int i) -> void {
            auto& first = cnt[diff[i]];
            first.erase(first.find(i));
            reverseCnt[cnt[diff[i]].size() + 1].erase(diff[i]);
            if (reverseCnt[cnt[diff[i]].size() + 1].empty()) {
                reverseCnt.erase(cnt[diff[i]].size() + 1);
            }
            if (first.empty()) {
                cnt.erase(diff[i]);
            }
            reverseCnt[cnt[diff[i]].size()].insert(diff[i]);
        };

        for (int i = 1; i < x; ++i) {
            addCnt(i);
        }
        auto check = [&](const int lastIdx) -> bool {
            // cout << lastIdx << " ... " << cnt << " " << maxDiffIndex << " " << maxDiffValue << endl;
            auto it = reverseCnt.begin();
            const int maxDiffValue = it->first;
            const int maxDiffIndex = *(it->second.begin());
            if (maxDiffValue == x - 1) return true;
            else if (maxDiffValue == x - 2 || maxDiffValue == x - 3) {
                vector<int> index;
                index.reserve(2);
                for (const auto& p : cnt) {
                    if (p.first != maxDiffIndex) {
                        for (const auto& idx : p.second) {
                            index.push_back(idx);
                        }
                    }
                }
                if (maxDiffValue == x - 2) {
                    if (index[0] == lastIdx || index[0] == lastIdx - x + 2) return true;
                    else return false;
                } else if (maxDiffValue == x - 3) {
                    if (index[1] < index[0]) {
                        swap(index[0], index[1]);
                    }
                    if (index[0] + 1 != index[1]) return false;
                    if (nums[index[1]] - nums[index[0] - 1] == maxDiffIndex * 2) return true;
                    else return false;
                } else return false;
            } else return false;
        };
        // cout << "Debug: " << maxDiffValue << endl;
        if (check(x-1)) return false;
        // if check
        for (int i = x; i < N; ++i) {
            // cout << "before: " << cnt ;
            eraseCnt(i - x + 1);
            addCnt(i);
            // cout << "after: " << cnt << " !!! ";
            if (check(i)) return false;
        }
        return true;
    };
    // for (int i = 4; i < hi; ++i) {
    //     cout << i << ":" << pred(i) << " ";
    // }
    return binary(lo, hi, pred) - 1;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        cout << "Case #" << i + 1 << ": ";
        cout << solve();
        cout << endl;
    }
    return 0;
}

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

阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
345 / 11446 YoungForest 18 0:40:04 0:03:21 0:05:10 0:25:30 0:35:04 1

久违的四题并进入前500名。终于可以免打卡了。
已经连续打卡7周了，快要遭不住了呀。最近LeetCode难度提升不小，大佬入场也很多。要同时达到4题和前500属实不易。
今天手速也算正常发挥.

1832. Check if the Sentence Is Pangram

签到题。
统计每个单词出现的次数，判断是否都大于0.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool checkIfPangram(string sentence) {
        vector<int> cnt(26, 0);
        for (char c : sentence) {
            ++cnt[c - 'a'];
        }
        for (int i : cnt) {
            if (i == 0) return false;
        }
        return true;
    }
};

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

1833. Maximum Ice Cream Bars

贪心。优先买便宜的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(begin(costs), end(costs));
        int ans = 0;
        for (int i : costs) {
            if (coins >= i) {
                ++ans;
                coins -= i;
            } else break;
        }
        return ans;
    }
};

时间复杂度: O(costs.length * log cost.length),
空间复杂度: O(log cost.length).

阅读全文 »
0%