YoungForest's blog

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
179 / 3745 YoungForest 18 0:41:10 0:02:39 0:10:36 0:12:53 0:36:10 1

回国后第一次参加双周赛，手有些生，状态还在恢复。最近因为新型冠状病毒的瘟疫，一直在家隔离，除了买菜外几乎无法出门。今年的年味也因此没有了。我在家呆的几乎都快产后抑郁了。比赛结果还行。手速场也是我一直不擅长的类型。

1342. Number of Steps to Reduce a Number to Zero

签到题。直接模拟 除2 和 减一 的2中操作即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numberOfSteps (int num) {
        int step = 0;
        while (num > 0) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                --num;
            }
            ++step;
        }
        return step;
    }
};

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

简单的滑动窗口，可以直接套用模版。

时间复杂度: 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
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int ans = 0;
        int s = 0;
        for (int i = 0; i < k; ++i) {
            s += arr[i];
        }
        if (s >= threshold * k) {
            ++ans;
        }
        for (int i = k; i < arr.size(); ++i) {
            s = s + arr[i] - arr[i - k];
            if (s >= threshold * k) {
                ++ans;
            }
        }
        
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

本周由于眼镜坏掉了，不在状态。在家吃饭也晚，所以题目并没有做完。

Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
1378 / 7826 YoungForest 7 0:11:41 0:06:51 0:11:41 null null

1346. Check If N and Its Double Exist

使用一个hashmap存储之前见到过的数即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s;
        for (int i : arr) {
            if (s.find(i * 2) != s.end() || (i % 2 == 0 && s.find(i / 2) != s.end()))
                return true;
            s.insert(i);
        }
        return false;
    }
};

1347. Minimum Number of Steps to Make Two Strings Anagram

根据Anagram的定义，我们统计2个字符串中各个字符出现频数之差就可以了。

时间复杂度: 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
class Solution {
    vector<int> convert(const string& s) {
        vector<int> ans(26);
        for (char c : s) {
            ++ans[c - 'a'];
        }
        return ans;
    }
public:
    int minSteps(string s, string t) {
        auto count_s = convert(s);
        auto count_t = convert(t);
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (count_s[i] > count_t[i]) {
                ans += count_s[i] - count_t[i];
            }            
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
459 / 6997 YoungForest 18 1:04:52 0:15:31 0:21:58 0:41:22 2 0:54:52

终于回到亲爱的祖国啦。可以周日早上起来打LeetCode的比赛了。不得不承认，4个月没打，手生了很多。从比赛名次上就可以看出。
这次比赛是完全的手速场，而手速是很看状态和熟练度的。因此排名掉了我心服口服。也恰好可以督促自己投入更多的精力准备接下来谷歌的面试。

1341. The K Weakest Rows in a Matrix

二分搜索 查找每行的士兵数，排序找到前K个最少的行。

时间复杂度: O(m log m * log n)
空间复杂度: O(m)

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
class Solution {
    bool decide(const vector<int>& row, int x) {
        return row[x] == 1;
    }
    int number(const vector<int>& row) {
        int lo = 0, hi = row.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (decide(row, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int, int>> q;
        for (int i = 0; i < mat.size(); ++i) {
            q.push_back({number(mat[i]), i});
        }
        // for (auto a : q) {
        //     cout << a.first << " " << a.second << endl;
        // }
        sort(q.begin(), q.end(), [](auto a, auto b) -> bool {
            if (a.first == b.first) {
                return a.second < b.second;                
            } else {
                return a.first < b.first;
            }
        });
        // for (auto a : q) {
        //     cout << a.first << " " << a.second << endl;
        // }
        vector<int> ans;
        for (int i = 0; i < k; ++i) {
            ans.push_back(q[i].second);
        }
        return ans;
    }
};

1342. Reduce Array Size to The Half

贪心策略。每次删除出现次数最多的数。

时间复杂度: 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
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int i : arr) {
            ++count[i];
        }
        vector<int> v;
        for (auto p : count) {
            v.push_back(p.second);
        }
        sort(v.begin(), v.end(), greater<int>());
        int ans = 0, target = (arr.size() + 1) / 2, accu = 0;
        while (accu < target) {
            accu += v[ans];
            ++ans;
        }
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于 Disqus：

问题的起因是因为LeetCode上的一个题目1286. Iterator for Combination。最完美的实现是利用 生成器(Generator)，也就是Python中的yield。但是我不会，只实现了一个提前计算，然后存起来的解法。并不优雅，赛后，学习了一个C++中Generator的实现，在此分享下。因为我并未在网上找到很好的中文的关于此的文章。

阅读全文 »

发表于 更新于 分类于 Disqus：

问题的根源是有个同学问了个lucky number的问题Codeforces 280B, Codeforces 281D也是同样的问题。

Find all unique pairs of maximum and second maximum elements over all sub-arrays in O(NlogN)

幸运数的定义为：数组中子数组的最大值和次大值的XOR值。寻找所有幸运数中的最大的。

Brute force 的解法是枚举所有的子数组，时间复杂度为O(N ^ 2).
有没有更优的方法呢？
今天要讨论的就是这个问题。

通用的解法，快速寻找 最大次大值对 算法

寻找子数组中最大值和次大值其实是有快速算法的:
Find all unique pairs of maximum and second maximum elements over all sub-arrays in O(NlogN)

基于这个的观察：数组中的每个数，如果想要成为次大值，就只能和向前的第一个比他大的数 或 向后的第一个比他大的数组成。
我们可以维护一个 单调递减栈，加入新数时，维持单调递增需要弹出所有小于它的数，这时新数就是被弹出来的数后面的第一个比他大的数；栈顶中最大的数 就是 新数 向前的第一个比他大的数。

时间复杂度: 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 <iostream>
#include <stack>
#include <vector>

using namespace std;
using ll = long long;

int solve() {
    ll N;
    cin >> N;
    vector<ll> nums(N);
    for (ll i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    stack<ll> st;
    st.push(nums[0]);
    ll ans = 0;
    for (ll i = 1; i < N; ++i) {
        while (!st.empty() && nums[i] > st.top()) {
            ans = max(ans, nums[i] ^ st.top());
            st.pop();
        }
        if (!st.empty()) {
            ans = max(ans, nums[i] ^ st.top());
        }
        st.push(nums[i]);
    }
    return ans;
}

int main() {
    ll ans = solve();
    cout << ans << endl;
    return 0;
}

我独立思考出的解法

阅读全文 »

发表于 更新于 分类于 Disqus：

这周没有出去玩，恰好遇到双周赛。久违地参加了一场，确实难得。
本次双周赛都是常规题目，不难。我提前50min全部一次AC, 典型的手速场。

Rank Name Score Finish Time Q1 (2) Q2 (4) Q3 (5) Q4 (7)
119 / 2503 YoungForest 18 0:39:28 0:02:18 0:08:49 0:21:07 0:39:28

比赛结束之前的排名是92，参与人数为1900，赛后发现名次掉了。我猜测并验证是，赛后的排名把中国区的人也算进来了。增加的人数和第一名的变化完全符合我的猜测。到leetcode-cn上看了下，那里的排名是分为中国区和全球区的。看来以后比赛时要更加油了，有许多不知道的人在中国区打同样的比赛。

1287. Element Appearing More Than 25% In Sorted Array

One pass统计所有数的出现次数。
时间复杂度: O(N),
空间复杂度: O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        unordered_map<int, int> count;
        const int target = arr.size() / 4;
        for (int i : arr) {
            ++count[i];
            if (count[i] > target)
                return i;
        }
        return -1;
    }
};

这个解法的缺陷在于没有利用题目中给的限制条件，数组是已经排好序的。但本题是签到题，数据规模10^4，此解法方便快速实现。

更优的解法，利用二分搜索，每次可以递增的更快些。
时间复杂度: O(N log N),
空间复杂度: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        auto it = arr.begin();
        while (it != arr.end()) {
            auto it2 = upper_bound(it, arr.end(), *it);
            auto diff = it2 - it;
            if (diff > arr.size() / 4)
                return *it;
            it = it2;
        }
        return -1;
    }
};

1288. Remove Covered Intervals

阅读全文 »

发表于 更新于 分类于 Disqus：

本学期有幸来比利时交换一学期，在“钱”上遇到很多困难，在同学的帮助下逐步克服。在此感谢帮助过我的一系列好友，并将自己的经验分享给大家，让更多的人收益。

在全球化的今天，来到欧洲，如何方便的花钱，省钱，是每个留学生关心的事情。在欧洲花钱基本可以分为2类：现金、刷卡。2者是相辅相成的关系，并不像在国内，一部手机走天下。
我的经历是：在国内换了700欧的现金带过来，还带了一张招商银行的Visa全币种信用卡。因为办签证需要经济证明，我还提前转了3000多欧给学校的账户，学校之后每个月给我的账户返还666欧，作为生活费。来了之后，我分别办了 ING的Green Account，网上银行 Revult, Curve, Bunq, Monese; 配置了Google Pay 和 PayPal。并经过到欧洲到处自由行，结合不同的花钱方式，达到最便利和最省钱。

接下来，我分别介绍各种方式的办理方法和优缺点。

现金 和 刷卡

在刚来比利时的时候，从国内带足够的现金是必要的，心里也有底。我带了700欧，事实证明，在有信用卡夹持的情况下，这些绰绰有余。比利时作为欧洲最发达的地区之一，刷卡几乎可以覆盖大多数消费场景。甚至一些大额的消费，如交房租，必须刷卡。幸好我信用卡的额度足够，在第一次交房租时，我还需要替同行的2个同学帮付。这时候就体现出国带信用卡的好处了。

现金

5Euro 纸币

在欧洲，身上带少量现金是必要的。尤其是50分的硬币，因为这里很多公共卫生间都是收费的，大多数是50分, 这可是救命钱。我建议多带些5欧的钱，面额越大，用处越小，越不方便。在某些消费场合，比如集市、地摊，也只能用现金。在欧洲某些相对欠发达地区，如希腊、意大利，不能刷卡的场合也比较多。西欧和北欧相对好很多，丹麦甚至上厕所都能刷卡。

信用卡

招商银行全币种Visa信用卡

阅读全文 »

发表于 更新于 分类于 Disqus：

由于欧洲这边夏令时的原因，处于UTC +1.00，所以本次比赛我是特意早上6点起来打的。打完后休息了一个小时，又和小伙伴去根特玩了一天。晚上回来的时候，才想起来Machine Learning的assignment 2当天截止，又疯狂地赶起了Deadline。事实证明，没有认真学习还是搞不定作业的。马马虎虎交上去了，总比不交好些。空白的题目，大方地告诉助教我就是不会。

本次比赛是Kick start 2019的最后一个轮次，我还是很想参加的。今年我共参加了6轮kick start。虽然A轮就拿到了面试的邀请，但仍然不可马虎。各次的排名如下所示:

轮次 A D E F G H
Rank 600 765 1566 1341 462 330
Score 35 27 22 11 42 41

除了F轮，我当时在巴黎玩，趁晚上在青旅的功夫瞎做的外。其他轮次还是可以说是全力以赴的。
总的名次是先下降后上升，并不能体现实力的变化，更多的是心态的改变。因为D轮次比较重要，当时也有同学一起竞争，不忍心与他比赛时交流。E轮次时，当时是在字节跳动的夏令营，和一个妹子一起做的。本身还是很想打好的，但由于并查集没有实现find的折叠，导致 超时。这也是之前没有注意到的盲点。其他3次结果相对好的轮次反而是没有包袱，更放松的时候。

最近还意外地收获了Google北京 A day with Google的邀请。无奈我不再北京，只能拒绝了。另外，我还通过邮件向Google反映了Google所有招聘相关的Form中My University中都没有 Beihang University的选项（我猜测这可能是因为北航在美国商务部的黑名单上的原因）。Google很快解决了，我航以后再也不是野鸡大学了。

本次做出签到题和第3题的小测试集1，算是正常发挥吧。

A. H-index

第一次做误解了题意，以为是求最后的H-index就可以了。简单地写了个二分查找用判定问题求最大值的解法。
后来才发现是需要求每次论文的结果，之后又因编写了几个bug的问题影响了耗时。

Intuition：
随着论文的发表，H-index是单调递增的。利用这一特性，每次发表论文后，尝试去增加H-index.
这里我利用里C++ STL set中有序的特点和基于节点的container再插入新节点后iterator的不变性，高效地实现了尝试增加H-index的操作。

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

阅读全文 »

发表于 更新于 分类于 Disqus：

使用Mac系统确实存在一些不方便的地方，比如 写入 NTFS的硬盘或U盘。默认情况下，MAC 只支持读取NTFS。不过只要你有勇气折腾，解决方案还是很简单的。

最推荐方法

Mounty for NTFS

优点：免费，小巧
缺点：不hack，其实就是命令行的包装。有些同学可能更喜欢命令行的方式。

最hack的方法

1
2
sudo umount "/Volumes/Seagate Expansion Drive"
sudo mount -t ntfs -o rw,auto,nobrowse /dev/disk3s1 ~/ntfs-volume

reference: mounty

经过一段时间的斗争，我还是采用了安装第三方应用的推荐方法。因为命令行确实经常忘记或是输错，每次都要重新Google，与我使用Mac系统想要的优雅方便不符。

阅读全文 »

发表于 更新于 分类于 Disqus：

1232. Check If It Is a Straight Line

依次检查3个点是否共线。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    bool right(const vector<int>& p1, const vector<int>& p2, const vector<int>& p3) {
        return (p1[0] - p2[0]) * (p2[1] -  p3[1]) == (p1[1] - p2[1]) * (p2[0] - p3[0]);
    }
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        for (int i =   0; i + 2 < coordinates.size(); ++i) {
            if (!right(coordinates[i], coordinates[i + 1], coordinates[i + 2])) {
                return  false;
            }
        }
        return true;
    }
};

1233. Remove Sub-Folders from the Filesystem

用一个HashSet记录出现过的路径，再遍历所有路径，依次分解每层的父目录，判断是否再记录中即可。

时间复杂度: O(folder.size() * string.size()),
空间复杂度: O(folder.size() * string.size()).

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
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        unordered_set<string> memo;
        for (auto& f : folder) {
            memo.insert(f);
        }
        vector<string> ans;
        for (auto& f : folder) {
            int i = f.size() - 1;
            bool appear = false;
            while (i >= 0) {
                while (i >= 0 && f[i] != '/') {
                    --i;
                }
                auto head = f.substr(0, i);
                if (memo.find(head) != memo.end()) {
                    appear = true;
                    break;
                }
                --i;
            }
            if (!appear) {
                ans.push_back(f);
            }
        }
        return ans;
    }
};

1234. Replace the Substring for Balanced String

滑动窗口。
记录所有多的字母，然后设置一个窗口使得多的字母出现字数多于多的次数。然后移动该窗口，保持窗口的特性(多的字母出现字数多于多的次数)不变。记录 窗口的最小长度。

阅读全文 »
0%