09数据结构设计
# 09 数据结构设计
考察多个数据结构的灵活组合使用
# 232 用栈实现队列 (opens new window)
尝试使用栈(stack)来实现队列(queue)。
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否则,返回 false
解析:
本题可以使用两个方向相反的栈实现一个队列如下图所示,其中箭头表示元素 pop 方向
使用两个栈的目的是:为了达到先入先出的效果,需要有一个栈用来翻转输入到栈中数组元素的顺序。这个翻转过程既可以在插入时完成,也可以在取值时完成。
在输入时进行反转:当所有元素都压栈进入 in 栈之后,将所有元素先入后出地压入 out 栈翻转数组。
在取值时进行反转:每次取值时,如果out非空则直接取栈顶;如果 out 栈为空,先将 in 栈中的元素全部先入后出压入 out 栈中,再从 out 栈中出栈元素。
class MyQueue {
private:
// < out | in <
stack<int> out;
stack<int> in;
public:
MyQueue() {}
void push(int x) {
in.push(x);
}
void connectOutIn(){
if(out.empty()){
while(!in.empty()){
int tail = in.top();
in.pop();
out.push(tail);
}
}
}
int pop() {
connectOutIn();
int tail = out.top();
out.pop();
return tail;
}
int peek() {
connectOutIn();
return out.top();
}
bool empty() {
return out.empty()&&in.empty();
}
};
# 225 用队列实现栈 (opens new window)
尝试使用队列(queue)来实现栈(stack)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
解析:
本题可以使用两个队列,主队列 q1 和辅助队列 q2,q1 保存当前所有元素,q2 用来在压入新元素时将该元素 q1 中已存在的元素之前。核心思想就是将新元素放到就元素之前形成先入后出。
主要考虑压入新元素的过程:
- 有新元素要入栈,现将该元素压入辅助队列 q2
- 将 q1 中的所有元素依次压入已经压入新元素的 q2 中,翻转出队列顺序
- 将 q2 中的所有元素按次序压入到 q1 中,这一过程也可以直接使用 swap 交换
- 完成新元素压入操作
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
MyStack() {
}
void push(int x) {
q2.push(x);
while(!q1.empty()){
q2.push(q1.front());
q1.pop();
}
// swap(q1,q2);
while(!q2.empty()){
q1.push(q2.front());
q2.pop();
}
}
int pop() {
int val = q1.front();
q1.pop();
return val;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};
# 155 最小栈 (opens new window)
设计一个最小栈,除了需要支持常规栈的操作外,还需要支持在 O(1) 时间内查询栈内最小值的功能。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
解析:
一种简单的思路是建立一个记录栈内当前最小值的辅助栈:每次插入原栈时,都向辅助栈插入一次原栈里当前所有值的最小值,即为辅助栈栈顶和待插入值中较小的那一个;每次从原栈里取出数字时,同样取出新栈的栈顶。
class MinStack {
private:
stack<int> s, min_s;
public:
MinStack() {
min_s.push(INT_MAX);
}
void push(int val) {
min_s.push(min(min_s.top(),val));
s.push(val);
}
void pop() {
min_s.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return min_s.top();
}
};
采用上述策略简化了判断,但是每次都要插入和取出,提高了时间复杂度。可以增加判断条件,减少辅助栈插入取出的操作:每当在原栈里插入一个数字时,若该数字小于等于辅助栈栈顶,则表示这个数字在原栈里是最小值,我们将其同时插入辅助栈内。每当从原栈里取出一个数字时,若该数字等于辅助栈栈顶,则表示这个数是原栈里的最小值之一,同时取出辅助栈栈顶的值。
# 380 O(1) 时间插入、删除和获取随机元素 (opens new window)
设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构:
insert(val):当元素 val 不存在时返回 true ,并向集合中插入该项,否则返回 false 。 remove(val):当元素 val 存在时返回 true ,并从集合中移除该项,否则返回 false 。 getRandom:随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
解析:
class RandomizedSet {
unordered_map<int,int> hash;
vector<int> vec;
public:
RandomizedSet() {
}
bool insert(int val) {
if(hash.find(val)!=hash.end()){
return false;
}
hash[val] = vec.size();
vec.push_back(val);
return true;
}
bool remove(int val) {
if(hash.find(val)==hash.end()){
return false;
}
int pos = hash[val];
hash[vec.back()] = pos;
hash.erase(val);
swap(vec[pos],vec[vec.size()-1]);
vec.pop_back();
return true;
}
int getRandom() {
return vec[rand()%vec.size()];
}
};
# 146 LRU 缓存 (opens new window)
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
解析:
首先要想好用哪几个数据结构。这里我们采用3个数据类型 :int 记录最大容量、list<pair<int,int>>双向链表记录<键,值>,unordered_map<int, list<pair<int,int>>::iterator> 记录每个键对应的<键,值>在双向链表中的位置。
我们在获取数据时,首先使用unordered_map判断有没有该数据。其次,通过unordered_map的值,获取链表位置,获得键对应的值。最后,更新该<键,值>到list的头部,因为只要使用了,就得更新到最近的位置。
在插入的时候,首先unordered_map判断有没有该数据,有则更新键值,并且更新<键,值>在list中的位置。若没有,则使用 int 判断链表容量是不是满了,若果满了,则删除链表最后一个元素,还要删除unordered_map中的索引。再更新list和unordered_map。
class LRUCache {
int cap;
// list<int,int> lruList;
// unordered_map<int, pair<int,int>::iterator> hash;
list<pair<int,int>> lruList;
unordered_map<int, list<pair<int,int>>::iterator> hash;
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
if(hash.find(key)!=hash.end()){
// auto *node = hash[key];
auto node = *hash[key]; // *iterator 方位迭代器指向的元素
// lruList.erase(node);
lruList.erase(hash[key]); // erase输入参数是迭代器不是值
lruList.push_front(node);
hash[key] = lruList.begin();
return node.second;
}
return -1;
}
void put(int key, int value) {
if(hash.find(key)!=hash.end()){
// auto *node = hash[key];
auto node = *hash[key]; // *iterator 方位迭代器指向的元素
// lruList.erase(node);
lruList.erase(hash[key]); // erase输入参数是迭代器不是值
node.second = value;
lruList.push_front(node);
hash[key] = lruList.begin();
}else{
if(lruList.size() >= cap){
hash.erase(lruList.back().first);
lruList.pop_back();
}
lruList.push_front(make_pair(key,value));
hash[key] = lruList.begin();
}
}
};