猫头鹰冲击微软

1，序列化和反序列化BST
2，手写LRU
3，腐烂句子
4，遍历二叉树 前序，中序，后续
5，合并区间
6，无重复字符的最长子串
7， 最长连续序列
8，不同岛屿的数量
9，岛屿问题
10，之前总结的代码

翻转字符串 --常规题

给定一个无序链表和一个数字，把比这个数字大的放在后面，比这个数字小的放在前面，要求稳定性。使用partition

对BST进行序列化和反序列化
https://leetcode-cn.com/problems/serialize-and-deserialize-bst/submissions/

岛屿数量–常规题

判断链表是否有环–

快排

二叉树排序

atoi实现

c++类，虚函数实现

new和malloc区别

class大小，包含virtual大小

虚表指针指向哪里？

进程和线程关系

强引用和弱引用

bfs问题，岛屿问题

链表翻转

LC200–岛屿
LC69=

L113，LC1，是否为合法三角形

矩形从左上走到右下

归并排序的推导，还有实现

手写LRU

class LRUCache {
public:
    map mp, vis; // 使用map存储键值 + 版本号机制
    queue> que;
    int cnt, cap, currSize;

    LRUCache(int capacity) {
        cap = capacity; // 容量
        cnt = 0;  // 用来位置版本号 
        currSize = 0; // 当前缓存的个数
    }
    
    int get(int key) {
        // 如果在visited中找不到key, return -1
        if (vis[key] == 0) {
            return -1;
        }

        // 一把更新,cnt用来维持版本号，保证每次版本号都不同
        que.push({key, vis[key] = ++ cnt});

        return mp[key];
    }
    
    void put(int key, int value) {
      // 如果当前的版本号和现在的版本号一样，说明没有被操作过，也就是最久没有被访问过的，需要被pop
        if(!vis[key]){
            while(currSize == cap){
                auto front = que.front();
                que.pop();
                if(vis[front.first] == front.second){
                    // 这里是把它降为0，而不是erase
                    vis[front.first] = 0;
                    --currSize;
                    break;
                }
            }
            ++currSize;
        }

        mp[key]=value;
        que.push({key,vis[key] =++cnt});
    }
};