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();
        }
    }
};