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;
}
};
|
答案写得非常简洁，真厉害
我和答案的差距:
- sort可以用默认的
- 不用临时的 pair 数组，因为参数没有加 const ，所以可以修改
- 答案对 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
|