刷题笔记3-设计数据结构

1 LRU

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU 缓存
 *
 * 该数据结构需要满足满足的要求:
 * 1、get方法需要根据key值快速获取到value => 哈希表
 * 2、数据结构中 key-value 需要按照是使用时间排序 =>
 * 这样可以在需要逐出最久没使用的关键字时直接移除最头部或最尾部元素
 * 3、get或者put的 key 后，需要改变其位置，因为其是最近被使用的关键字
 *
 * 哈希 + shua链表
 */

// @lc code=start

// 链表结点类
class Node {
   public:
    int key{-1};
    int value{-1};
    Node* next{nullptr};
    Node* prev{nullptr};

    Node(int key, int value) {
        this->key = key;
        this->value = value;
    }
    Node() {}
};

// 双向链表类
class DoubleLinkedList {
   private:
    Node *head, *tail;
    int size;

   public:
    DoubleLinkedList() {
        size = 0;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    void remove(Node* n) {  // 从链表中删除一个结点
        n->prev->next = n->next;
        n->next->prev = n->prev;
        n->next = nullptr;
        n->prev = nullptr;
        size--;
    }

    void addInLast(Node* n) {  // 把一个结点插在尾部
        tail->prev->next = n;
        n->prev = tail->prev;
        tail->prev = n;
        n->next = tail;
        size++;
    }

    // 判断是否在某个容量内
    bool isWithinCap(int capacity) { return size < capacity; }

    // 返回第一个元素
    Node* first() {
        if (size > 0) {
            return head->next;
        }
        return nullptr;
    }
};

// LRUcache类
class LRUCache {
   private:
    unordered_map<int, Node*> um;  // 哈希表
    DoubleLinkedList list;         // 双向链表
    int _cap;

    void makeRecently(int key) {  // 把某个关键字变成最近使用
        Node* p = um[key];
        list.remove(p);
        list.addInLast(p);
    }

    void removeLeastRecentlyUsed() {  // 逐出最不常使用的关键字
        Node* p = list.first();
        list.remove(p);
        um.erase(p->key);
        delete p;
    }

   public:
    LRUCache(int capacity) { _cap = capacity; }

    int get(int key) {
        if (!um.count(key)) {
            return -1;
        }
        makeRecently(key);
        return um[key]->value;
    }

    void put(int key, int value) {
        // 已经存在
        if (um.count(key)) {
            um[key]->value = value;  // 更新值
            makeRecently(key);
            return;
        }
        // 不存在，需要插入
        if (!list.isWithinCap(_cap)) {  // 满了
            removeLeastRecentlyUsed();
        }
        // 加在尾部
        Node* n = new Node(key, value);
        list.addInLast(n);
        um[key] = n;  // 加在map中
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end

2 LFU

lfu 算法的难度更大，其要求如下：

1、使用get函数根据key得到value，时间复杂度为O(1)

2、put函数（需要O(1)时间复杂度）

​ 2.1、如果key已经存在，那么修改对应的value

​ 2.2、如果容量够，那么插入一个key-value，且其使用频率（freq）为1

​ 2.3、如果容量不够，那么逐出使用频率最少的一个key-value，如果存在多个使用频率最少的key-value，那么逐出最近最不常使用的那一个

3、所有key-value在被访问后其使用频率freq都应该加一

分析：

很明显，需要O(1)的时间复杂度，肯定还是离不开【哈希表】和【链表】

对上面的要求来逐个分析

1和3、建立一个 key 到 value 和 freq 的哈希映射 （建立key到Node的哈希映射）

2.1、建立和哈希映射之后可以很好解决

2.2、建立一个新的key-Node映射即可

2.3、存在两层的排序 【使用频率】和【使用时间】。其中【使用时间】其实就是lru算法中的排序，使用双向链表即可解决。但是注意，是先根据使用【频率排序】，当使用【频率相同】的情况下再根据【使用时间】排序，所以应该是一个freq值对应这一个双向链表，这个双向链表记录【使用时间】的远近，所以再建立一个freq到双向链表的映射，就可以很好解决这个问题。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// 双向链表的结点类
class Node {
   public:
    int key{-1};
    int val{-1};
    int freq{-1};
    Node* next{nullptr};
    Node* prev{nullptr};

    Node(int k, int v, int f) {
        key = k;
        val = v;
        freq = f;
    }

    Node() {}
};

class DoubleLinkedList {
   public:
    Node *head, *tail;
    int size;
    DoubleLinkedList() {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    void remove(Node* n) {  // 从链表中删除一个结点
        n->prev->next = n->next;
        n->next->prev = n->prev;
        n->next = nullptr;
        n->prev = nullptr;
        size--;
    }

    void addInLast(Node* n) {  // 把一个结点插在尾部
        tail->prev->next = n;
        n->prev = tail->prev;
        tail->prev = n;
        n->next = tail;
        size++;
    }

    Node* first() {  // 返回第一个结点
        if (size > 0) {
            return head->next;
        }
        return nullptr;
    }

    bool empty() { return size == 0; } // 判断是否为空
};

class LFUCache {
   private:
    // 建立key->Node的映射，因为Node中包含了value和freq等信息，这样可以直接通过key获取到
    // Node也是DoubleLinkedList的结点，这样建立映射就可以使得两个map之间关联起来了
    unordered_map<int, Node*> keyTonode;
    unordered_map<int, DoubleLinkedList> freqTokeys;
    int _cap;
    int minFreq; // 记录最小的freq

    void remove(int key) {  // 将key对应的Node从相应freq对应的双向链表中移除
        Node* n = keyTonode[key];
        freqTokeys[n->freq].remove(n);
        // 判断更新minFreq
        if (n->freq == minFreq && freqTokeys[n->freq].empty()) {
            minFreq++;
        }
    }

    void increaseFreq(int key) {  // 增加key对应的freq，并且将其插入到对应的双向链表中
        Node* n = keyTonode[key];
        n->freq++;
        int freq = n->freq;
        if (freqTokeys.count(freq) == 0) {
            DoubleLinkedList dl;
            freqTokeys[freq] = dl;
        }
        freqTokeys[freq].addInLast(n);
    }

   public:
    LFUCache(int capacity) { _cap = capacity; }

    int get(int key) {
        if (keyTonode.count(key) == 0) {
            return -1;
        }
        remove(key);
        increaseFreq(key);
        return keyTonode[key]->val;
    }

    void put(int key, int value) {
        // 存在key
        if (keyTonode.count(key)) {
            keyTonode[key]->val = value;
            remove(key);
            increaseFreq(key);
            return;
        }
        if (_cap == 0) return;
        // 不存在key
        if (keyTonode.size() == _cap) {  // 容量不足
            Node* node = freqTokeys[minFreq].first();
            keyTonode.erase(node->key);
            freqTokeys[minFreq].remove(node);
            delete node;
        }
        Node* n = new Node(key, value, 0);
        keyTonode[key] = n;
        increaseFreq(key);
        minFreq = 1;
    }
};

3 常数时间查找/删除数组元素

常数时间插入、删除和获取随机元素 380

黑名单中的随机数 710

【要求】

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

分析：

1、需要判断val是否存在，肯定要用到哈希表

2、getRandom函数：生成一个随机数，返回该随机数为下标的数组元素

3、remove函数的实现需要一些技巧：将需要remove的元素和最后一个元素换位置

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
47
48
49
50
51
52
53
class RandomizedSet {
    vector<int> arr;
    unordered_map<int, int> valToidx;

   public:
    RandomizedSet() {}

    bool insert(int val) {
        if (valToidx.count(val) == 0) {
            arr.push_back(val);
            valToidx[val] = arr.size() - 1;
            return true;
        }
        return false;
    }
    /*
    存在的问题是：直接从数组中间earse掉的话，会影响后面元素的下标，即map中对应的下标就失效了
        bool remove1(int val) {
            if (valToidx.count(val) == 1) {
                int idx = valToidx[val];
                arr.erase(arr.begin() + idx);
                valToidx.erase(val);
                return true;
            }
            return false;
        }
    */
    // 将需要pop的元素和数组末尾的元素换个位置就可以很好解决了
    bool remove(int val) {
        if (valToidx.count(val) == 1) {
            int idx = valToidx[val];
            int lastIdx = arr.size() - 1;
            int lastVal = arr[lastIdx];
            // swap
            arr[idx] = lastVal;
            arr[lastIdx] = val;
            // update map
            valToidx[val] = lastIdx;
            valToidx[lastVal] = idx;

            arr.pop_back();
            valToidx.erase(val);
            return true;
        }

        return false;
    }

    int getRandom() {
        int idx = rand() % arr.size();
        return arr[idx];
    }
};

【要求】

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

  • Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
  • int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

【分析】

1、如果使用一般的思路，将[0,n-1]中的元素除去blacklist中的放到数组里，然后再生成随机数返回。这样会出现超时（时间复杂度为O(n)，而n比较大）

2、可以把[0,n-1]想象成一个下标和值对应的数组（实际不存在），我们将所有blacklist中的元素全部移到数组末尾，然后再根据实际的长度生成随机数返回即可。

3、难点在于：如何正确地将所有blacklist元素移到数组末尾（注意数组并不真实存在）

​ 3.1、已经在数组末尾的元素不用移动

​ 3.2、blacklist中的一个元素映射到另一个元素时怎么处理

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
class Solution {
    unordered_map<int, int> mapping; // 处理"移动": tong'g将blacklist中的元素映射到相应位置
    int sz;

   public:
    Solution(int n, vector<int>& blacklist) {
        sz = n - blacklist.size();
        int last = n - 1;
		// 先将所有blacklist中的值加入到哈希表中，方便后续的判断
        for (int i : blacklist) {
            mapping[i] = 1;
        }

        for (int i = 0; i < blacklist.size(); i++) {
            if (blacklist[i] >= sz) continue; // 元素本身就在数组末尾
            while (mapping.count(last)) { // blacklist中的元素映射到了另一个元素，last就要变小
                last--;
            }
            mapping[blacklist[i]] = last;
            last--;
        }
    }

    int pick() {
        int idx = rand() % sz;
        if (mapping.count(idx)) {
            return mapping[idx];
        }
        return idx;
    }
};

4 求中位数

数据流的中位数 295

【要求】

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

使用两个优先队列：一个大顶堆、一个小顶堆

相当于将一个数组在中间分成两部分，这样通过两个堆的堆顶元素就可以求出中位数

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
class MedianFinder {
    priority_queue<int, vector<int>> small;                // 大顶堆
    priority_queue<int, vector<int>, greater<int>> large;  // 小顶堆

   public:
    MedianFinder() {}

    /*
        满足两个条件
        1、small和large的大小最多相差一
        2、small.top() <= large.top()
    */
    void addNum(int num) {
        if (small.size() >= large.size()) {
            // 插入large
            small.push(num);
            large.push(small.top());
            small.pop();
        } else {
            // 插入samll
            large.push(num);
            small.push(large.top());
            large.pop();
        }
    }

    double findMedian() {
        if (small.size() == large.size()) {
            return (small.top() + large.top()) / 2.0;
        } else if (small.size() > large.size()) {
            return small.top();
        } else {
            return large.top();
        }
    }
};
leetcode刷题笔记
#leetcode
刷题笔记3-设计数据结构
http://example.com/2022/09/07/leetcode/刷题笔记3（设计）/
作者
zhc
发布于
2022年9月7日
许可协议