380. Insert Delete GetRandom O(1)
Analysis
这个好像在每日一题做过...
题目要求实现一个叫随机集合的类，同时要求每个函数的时间复杂度都是$O(1)$。
Code
constructor
先思考一下实现这个类的底层数据结构是什么。
因为题目要求插入、删除都是$O(1)$，所以必须要借助哈希表，那存储数据用 vector 就可以了。
同时，因为题目还要求能以等概率取到所有的数，所以在构造函数内，需要生成一下随机数种子。1
2
3
4
5
6
7
8
9class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
private:
vector<int> nums;
unordered_map<int, int> indices;
};
insert
哈希表直接保存元素的在 vector 中的下标，如果哈希表内已经存在这个元素，就不再进行插入操作了。1
2
3
4
5
6
7bool insert(int val) {
if(indices.count(val)) return false;
int index = nums.size();
nums.push_back(val);
indices[val] = index;
return true;
}
remove
为了避免删除 vector 中的元素后要移动元素，每次删除元素前，先将最末尾的元素移动到要删除的元素位置，然后再删除这个元素。当然，这里说的删除，实际上都不是真正意义上的删除，这点与磁盘的工作原理是类似的。1
2
3
4
5
6
7
8
9
10bool remove(int val) {
if(!indices.count(val)) return false;
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
getRandom
构造函数内已经生成了随机数种子，这里直接用就可以了。1
2
3
4int getRandom() {
int randomindex = rand() % nums.size();
return nums[randomindex];
}
Summary
1 | class RandomizedSet { |
622. Design Circular Queue
Analysis
又是一堆题目说明，实际上就是设计循环队列，只是在一些地方与普通队列有所差别。
Code
constructor
类似普通队列，底层数据结构用 vector 就可以了，同时需要有两个指针 front 和 rear，分别指向队首和队尾元素。在构造函数里面，初始化这两个指针，顺便设置数组的容量为k + 1。1
2
3
4
5
6
7
8
9
10
11class MyCircularQueue {
public:
MyCircularQueue(int k) {
maxsize = k + 1;
data.resize(maxsize);
front = rear = -1;
}
private:
vector<int> data;
int front, rear, maxsize;
};
isEmpty
考虑其他函数之前，先思考如何判断队列为空和满。很容易想到的是，当首尾指针相等时，队列就为空了。1
2
3bool isEmpty() {
return front == rear;
}
isFull
与判空一样，当首尾指针相等时，也会出现队列满的情况。所以为了区分这两种情况，就需要 vector 内空一个位置当作标志位，来判断是否队满。1
2
3bool isFull() {
return (rear + 1) % maxsize == front;
}
enQueue
入队时，移动队尾指针，先判断队列是否为满，然后放入元素或者返回false。1
2
3
4
5
6bool enQueue(int value) {
if(isFull()) return false;
rear = (rear + 1) % maxsize;
data[rear] = value;
return true;
}
注意，这里是先移动指针在放入元素。
deQueue
出队时，移动队首指针，先判断队列是否为空，然后移动队首指针即可。1
2
3
4
5bool deQueue() {
if(isEmpty()) return false;
front = (front + 1) % maxsize;
return true;
}
Front
先判空，然后取元素。由于入队时，是先移动指针，所以这里也取的是front指针的下一个位置。1
2
3
4int Front() {
if(isEmpty()) return -1;
return data[(front + 1) % maxsize];
}
Rear
先判断空，然后取元素。由于入队时已经移动过指针了，所以rear指向的就是队尾的元素，直接返回即可。1
2
3
4int Rear() {
if(isEmpty()) return -1;
else return data[rear];
}
在这里可以看出，如果入队时先放入元素，在移动指针，可能会无法直接通过rear来找到队尾元素。
按照先放入元素在移动指针的思路，当rear为 0、front不为 0 时，队尾元素在数组的末尾，好像没办法直接通过取余来得到队尾元素的指针...解决方法就是特判一下，然后用front来寻找队尾元素，所以不如直接先移动指针，在放入元素，再移动指针。
Summary
1 | class MyCircularQueue { |
729. My Calendar I
Analysis
感觉这是一个跟区间相关的题目...
Code
method 1
底层就用 vector，日期是一对一对出现的，所以直接用 pair 即可。1
2
3
4
5
6
7
8class MyCalendar {
public:
MyCalendar() {
}
private:
vector<pair<int, int>> calendar;
};
不造成重复预订的条件是开始日期和结束日期都不会被占用，所以可以直接判断。1
2
3
4
5
6
7bool book(int start, int end) {
for(auto &[s, e]: calendar) {
if(!(start >= e || end <= s)) return false;
}
calendar.push_back(make_pair(start, end));
return true;
}
做一下逻辑运算，化简一下判断条件，就是：1
2
3
4
5
6
7bool book(int start, int end) {
for(auto &[s, e]: calendar) {
if(start < e && end > s) return false;
}
calendar.push_back(make_pair(start, end));
return true;
}
最后合并到一起：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class MyCalendar {
public:
MyCalendar() {
}
bool book(int start, int end) {
for(auto &[s, e]: calendar) {
if(start < e && end > s) return false;
}
calendar.push_back(make_pair(start, end));
return true;
}
private:
vector<pair<int, int>> calendar;
};
method 2
注意到，如果预订的日期是按照时间顺序来排序的话，再插入下一个日期时，就可以用二分查找，来寻找合理的插入位置了。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
36class MyCalendar {
public:
MyCalendar() {
}
bool book(int start, int end) {
if(calendar.size() == 0) {
calendar.insert(make_pair(start, end));
return true;
} else {
auto pos = calendar.lower_bound(make_pair(start, 0));
if(pos == calendar.end()) {
pos--;
if(pos->second <= start) {
calendar.insert(make_pair(start, end));
return true;
} else return false;
} else if(pos == calendar.begin()) {
if(pos->first >= end) {
calendar.insert(make_pair(start, end));
return true;
} else return false;
} else {
if(pos->first >= end) {
pos--;
if(pos->second <= start) {
calendar.insert(make_pair(start, end));
return true;
} else return false;
} else return false;
}
}
}
private:
set<pair<int, int>> calendar;
};
简化一下：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
36class MyCalendar {
public:
MyCalendar() {
}
bool book(int start, int end) {
if(calendar.size() == 0) {
calendar.insert({start, end});
return true;
} else {
auto pos = calendar.lower_bound({start, 0});
if(pos == calendar.end()) {
pos--;
if(pos->second <= start) {
calendar.insert({start, end});
return true;
} else return false;
} else if(pos == calendar.begin()) {
if(pos->first >= end) {
calendar.insert({start, end});
return true;
} else return false;
} else {
if(pos->first >= end) {
pos--;
if(pos->second <= start) {
calendar.insert({start, end});
return true;
} else return false;
} else return false;
}
}
}
private:
set<pair<int, int>> calendar;
};
不过这样写二分实在是不太美观...
实际上，要考虑的情况也不需要这么多...
换用 map 来保存，用 end 来进行二分查找，找到的元素的 start 一定大于等于 end 的。此时，要判断的是，这个元素之前的 end 是否小于等于要插入的元素的 start，满足，那就直接插入即可。因为 map 是有序（以 key 为排序依据，这里就是每个元素的 start）的，所以这个元素就可以被插入在这里。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class MyCalendar {
public:
MyCalendar() {
calendar[-1] = -1;
}
bool book(int start, int end) {
auto pos = calendar.lower_bound(end);
if((--pos)->second <= start) {
calendar[start] = end;
return true;
}
return false;
}
private:
map<int, int> calendar;
};
Summary
设计的题目，感觉做起来有点无聊...
哈，这个学习计划完成了，倒是个让人觉得轻松的事情。
不过，不是很熟悉二分的应用，需要练习一下。
