编码熟练度类型

1. 动物收容所

a) 考点：双队列，pair，return返回return

b) 思路

维护两个队列 queue> queCat;
维护一个自增数 int count = 0;
设计入队的函数，注意push的时候，是push({count, animal[0]})，然后count编号自增。
设计出队的函数；
设计出Dog的函数，注意边界判断，是否queDog为空，如果有Dog，则先进先出，即temp = queDog.front().first;是要返回的，然后pop，return{temp, 1};
同理设计Cat的函数，注意是返回return{temp, 0};，因为0代表猫。

class AnimalShelf {
    queue<pair<int,int>> queCat; //猫队列
    queue<pair<int,int>> queDog; //狗队列
    int cout = 0; //设置自增数
public:
    AnimalShelf() {
    }

    void enqueue(vector<int> animal) {
        if(animal[1]) queDog.push({cout,animal[0]});  //种类为狗
        else queCat.push({cout,animal[0]});   //种类为猫
        cout ++; //编号自增
    }
    
    vector<int> dequeueAny() {
        if(queDog.empty() && queCat.empty()) return {-1, -1};  //猫狗都为空
        else if(queCat.empty() && queDog.size()) return dequeueDog(); //有狗无猫
        else if(queDog.empty() && queCat.size()) return dequeueCat(); //有猫无狗
        else if(queDog.front() < queCat.front()) return dequeueDog(); //有猫有狗，狗编号小
        else return dequeueCat(); //有猫有狗，猫编号小
    }
    
    vector<int> dequeueDog() {
        if(queDog.empty()) return {-1, -1}; //无狗
        int temp = queDog.front().first; //有狗，先进先出
        queDog.pop();
        return {temp, 1};
    }
    
    vector<int> dequeueCat() {
        if(queCat.empty()) return {-1, -1}; //无猫
        int temp = queCat.front().first; //有猫先进先出
        queCat.pop();
        return {temp, 0};
    }
};
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

2. 顶端迭代器

a) 考点：迭代器的基本认识

b) 思路

c++中PeekingIterator继承父类Iterator，Iterator已经实现方法next和hasNext。使用flag标记迭代器是否还有剩余元素，使用nextElement存储迭代器的下一个元素

• next：首先用ret存储nextElement表示返回值，flag保存Iterator调用hasNext方法的返回结果，然后将nextElement向后移动一位，返回ret；
• hasNext：返回flag；
• peek：peek操作不改变指针，返回nextElement。

class PeekingIterator : public Iterator {
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
    }
    
    int peek() {
        return nextElement;
    }
    
    int next() {
        int ret = nextElement;
        flag = Iterator::hasNext();
        if (flag) {
            nextElement = Iterator::next();
        }
        return ret;
    }
    
    bool hasNext() const {
        return flag;
    }
private:
    int nextElement;
    bool flag;
};
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

复杂度分析：

时间复杂度：每一项操作的时间复杂度都是 O(1)。
空间复杂度：O(1)。

3. 扁平化嵌套列表迭代器

一个嵌套的整数列表nestedList。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

a) 考点：深度优先搜索DFS

b) 思路

先遍历整个嵌套列表，将所有整数存入一个数组，然后遍历该数组从而实现next和hasNext方法。
难点：next返回的是嵌套列表的下一个整数，cur是迭代器，cur就是取迭代器所指向的位置的元素值，而cur是vals向量列表的begin，所以需要cur++。这是个容易疏忽的点！（下一个）

class NestedIterator {
private:
    vector<int> vals;
    vector<int>::iterator cur;

    void dfs(const vector<NestedInteger> &nestedList) {
        for (auto &nest : nestedList) {
            if (nest.isInteger()) {
                vals.push_back(nest.getInteger());
            } else {
                dfs(nest.getList());
            }
        }
    }

public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
        cur = vals.begin();
    }

    int next() {
        return *cur++;
    }

    bool hasNext() {
        return cur != vals.end();
    }
};
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

复杂度分析

• 时间复杂度：初始化为 O(n)，next和hasNext 为 O(1)。其中 n 是嵌套的整型列表中的元素个数。
• 空间复杂度：O(n)。需要一个数组存储嵌套的整型列表中的所有元素。

4. 座位预约管理系统

设计一个管理n个座位预约的系统，座位编号从1到n。
实现SeatManager类。

• SeatManager(int a)初始化一个SeatManager对象，它管理从1到n编号的n个座位。所有座位初始都是可预约的。
• int reserve() 返回可以预约座位的最小编号，此座位变为不可预约。
• void unreserve(int seatNumber)将给定编号seatNumber对应的座位变成可以预约。

a) 考点：最小堆（优先队列）

b) 思路

对于reserve方法，需要弹出并返回available中的最小元素；
对于unreserve方法，需要将seatNumber添加至available中。
使用二叉堆实现的优先队列作为available。对于一个最小堆，可以在O(log n)的时间复杂度内完成单词添加元素和弹出最小值的操作。

class SeatManager {
public:
    vector<int> available;

    SeatManager(int n) {
        for (int i = 1; i <= n; ++i){
            available.push_back(i);
        }
    }
    
    int reserve() {
        pop_heap(available.begin(), available.end(), greater<int>());
        int tmp = available.back();
        available.pop_back();
        return tmp;
    }
    
    void unreserve(int seatNumber) {
        available.push_back(seatNumber);
        push_heap(available.begin(), available.end(), greater<int>());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

• 时间复杂度：O(n + (q1 + q2)*log n)，其中 n 为座位的数量，q1 为reserve 操作的次数，q2为unreserve 的次数。初始化的时间复杂度为 O(n)，二叉堆实现的优先队列单次添加元素与弹出最小值操作的复杂度均为 O(\log n)。
• 空间复杂度：O(n)O(n)，二叉堆的空间开销。

5. 设计浏览器历史记录

考点：stack

思路

当成stack题目，利用双栈分别存储，再保存一个当前的链接，对应操作

class BrowserHistory {
private:
    stack<string> backHis;
    stack<string> forwardHis;
    string presentUrl;
public:
    BrowserHistory(string homepage) {
        presentUrl = homepage;
    }
    
    void visit(string url) {
        backHis.push(presentUrl);
        presentUrl = url;
        while(!forwardHis.empty())  forwardHis.pop();
    }
    
    string back(int steps) {
        while(steps-- > 0 && !backHis.empty()){
            forwardHis.push(presentUrl);
            presentUrl = backHis.top();
            backHis.pop();
        }
        return presentUrl;
    }
    
    string forward(int steps) {
        while(steps-- > 0 && !forwardHis.empty()){
            backHis.push(presentUrl);
            presentUrl = forwardHis.top();
            forwardHis.pop();
        }
        return presentUrl;
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */
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

6. 设计一个验证系统

考点：哈希表

思路

使用unordered_map存储id与初始化的时间的映射。
generate操作就更新到map里面，renew操作先判断有没有和是否超时，再进行更新，countUnexpiredTokens操作就遍历一遍哈希表，寻找未超时的id个数。

7. LRU缓存

考点：哈希表，双向链表

8. 栈排序

考点：

9. 设计循环双端队列

考点：

10. 设计前中后队列

考点：

11. 每隔n个顾客打折

考点：

12. 找出和为指定值的下标对

考点：

13. 皇位继承顺序

考点：

14. O(1)时间插入、删除和获取随机元素

考点：

15. 设计地铁系统

考点：

16. 设计推特

考点：

17. 堆盘子

考点：

算法熟练度类型

1. 至少有K个重复字符的最长子串

一个字符串s和一个整数k，找出s中的最长子串，要求该子串中的每一个字符出现次数都不少于k。返回这一子串的长度。

考点：分治、滑动窗口

思路

对于字符串 ss，如果存在某个字符 \textit{ch}ch，它的出现次数大于 00 且小于 kk，则任何包含 \textit{ch}ch 的子串都不可能满足要求。也就是说，我们将字符串按照 \textit{ch}ch 切分成若干段，则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越一个或多个段。因此，可以考虑分治的方式求解本题。
分治法：

class Solution {
public:
    int dfs(const string& s, int l, int r, int k) {
        vector<int> cnt(26, 0);
        for (int i = l; i <= r; i++) {
            cnt[s[i] - 'a']++;
        }

        char split = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0 && cnt[i] < k) {
                split = i + 'a';
                break;
            }
        }
        if (split == 0) {
            return r - l + 1;
        }

        int i = l;
        int ret = 0;
        while (i <= r) {
            while (i <= r && s[i] == split) {
                i++;
            }
            if (i > r) {
                break;
            }
            int start = i;
            while (i <= r && s[i] != split) {
                i++;
            }

            int length = dfs(s, start, i - 1, k);
            ret = max(ret, length);
        }
        return ret;
    }

    int longestSubstring(string s, int k) {
        int n = s.length();
        return dfs(s, 0, n - 1, k);
    }
};

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

滑动窗口

class Solution {
public:
    int longestSubstring(string s, int k) {
        int ret = 0;
        int n = s.length();
        for (int t = 1; t <= 26; t++) {
            int l = 0, r = 0;
            vector<int> cnt(26, 0);
            int tot = 0;
            int less = 0;
            while (r < n) {
                cnt[s[r] - 'a']++;
                if (cnt[s[r] - 'a'] == 1) {
                    tot++;
                    less++;
                }
                if (cnt[s[r] - 'a'] == k) {
                    less--;
                }

                while (tot > t) {
                    cnt[s[l] - 'a']--;
                    if (cnt[s[l] - 'a'] == k - 1) {
                        less++;
                    }
                    if (cnt[s[l] - 'a'] == 0) {
                        tot--;
                        less--;
                    }
                    l++;
                }
                if (less == 0) {
                    ret = max(ret, r - l + 1);
                }
                r++;
            }
        }
        return ret;
    }
};

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

2. 至少有K个重复字符的最长子串

考点：

3. 将数组分成三个子数组的方案数

考点：

4. 大样本统计

考点：

5. 最小区间

考点：