Contents

ARST打卡第225周[225/521]

Algorithm

lc56_合并区间

之前某鹏面试就出过类似题…

思路: 通过左边界先排序,然后右边界再排序,最终遍历一一获取边界

WA了一波,然后成绩也很差,看看题解

时间 36ms 击败 54.00%使用 C++ 的用户 内存 19.68MB 击败 11.01%使用 C++ 的用户

 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
class Solution {
public:
    // 出错1: 这里得static
    static bool sort_func(pair<int, int> a, pair<int, int> b) {
        return a.first != b.first ?  a.first < b.first : a.second < b.second;
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> sort_intervals;
        for (auto& x : intervals) {
            sort_intervals.push_back({x[0], x[1]});
        }
        sort(sort_intervals.begin(), sort_intervals.end(), sort_func);
        int sz = sort_intervals.size();
        vector<vector<int>> ans;
        pair<int, int> l = sort_intervals[0];
        pair<int, int> r;
        // bool pass_to_left = false;
        for (int i = 1; i < sz; i++) {
            // if (pass_to_left) {
            //     l = sort_intervals[i];
            //     pass_to_left = false;
            //     continue;
            // }
            r = sort_intervals[i];
            if (l.second >= r.first) {
                // 出错4: intervals = [[1,4],[2,3]]
                // l.second = r.second;
                l.second = max(l.second, r.second);
            } else {
                vector<int> tmp_item(0, 2);
                tmp_item.emplace_back(l.first);
                tmp_item.emplace_back(l.second);
                ans.emplace_back(tmp_item);
                // pass_to_left = true;
                // 出错2: 这里有一个值可以传给左值。
                l = r;
            }
        }
        // 出错3: 最后会剩下一个
        vector<int> tmp_item(0, 2);
        tmp_item.emplace_back(l.first);
        tmp_item.emplace_back(l.second);
        ans.emplace_back(tmp_item);
        return ans;
    }
};

答案写得非常简洁,真厉害

我和答案的差距:

  1. sort可以用默认的
  2. 不用临时的 pair 数组,因为参数没有加 const ,所以可以修改
  3. 答案对 L,R 理解更加简洁
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

Review

【TED演讲】视力的保护原理

重要的不是我们能活多久,重要的是我们能高质量地活多久,所以保护眼睛很重要

Tips

LevelDB/RocksDB 特性分析

Share-vim粘贴交换内容原理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 9. There's been a mixup in the battle plans and our goblin formation is made of orcs,
//    and our orcs formation is made out of goblins. We need to fix this mixup and also
//    make sure we send the goblins to battle first.
//    Tip: Try using y and p and see what happens

//   start here
//     /
//   /
// v  /orcs<ENTER>yiwkviwpjviwpnviwp => oh no! It's orcs, that's the problem I was trying to illustrate! :)
class Orc {}
class Goblin {}
const goblins = [new Orc(), new Orc(), new Orc()];
const orcs = [new Goblin(), new Goblin(), new Goblin()];
// We'd like to send the goblins first to battle, because they're cannon fodder
// that will tire the enemy before the real warriors arrive.
sendArmiesToBattle(orcs);
1
2
3
4
1. (at the start)      => unnamed register: empty
2. `yiw` over orcs     => unnamed register: orcs
3. `viwp` over goblins => unnamed register: goblins   AAaah?!
4. `viwp` over orcs    => unnamed register: orcs