本文源自于个人github仓库：https://github.com/forthespada/InterviewGuide
github仓库内有PDF版本笔记下载方式，欢迎各位star、fork~
立志收录计算机校招、社招面试最全面试，无内鬼来点八股文~
八股文：一般指的就是面试中常问问题，固定回答的问题，比如常见的进程线程区别、TCP三次握手四次挥手等

5、快排排序

void quickSort(vector<int>& data, int low, int high) {
    //for_each(data.begin(), data.end(), [](const auto a) {cout << a << " "; });
    //cout << endl;
    if (low >= high) return;
    int key = data[low], begin = low, end = high;
    while (begin < end) {
        while (begin<end && data[end]>key) {
            end--;
        }
        if (begin < end) data[begin++] = data[end];

        while (begin<end && data[begin]<= key) {
            begin++;
        }
        if (begin < end) data[end--] = data[begin];


    }

    data[begin] = key;
    quickSort(data, low, begin - 1);
    quickSort(data, begin + 1,high);
}

6、归并排序

void mergeSort(vector<int>& data, vector<int>& copy, int begin, int end) {
    if (begin >= end) return;
    int mid = begin + (end - begin) / 2;
    int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end, index = begin;
    mergeSort(copy, data, low1, high1);
    mergeSort(copy, data, low2, high2);
    while (low1 <= high1 && low2 <= high2) {

        copy[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
    }
    while (low1 <= high1) {
        copy[index++] = data[low1++];
    }

    while (low2 <= high2) {
        copy[index++] = data[low2++];
    }
}

void mergeTest() {
    vector<int> nums = { -5,-10,6,5,12,96,1,2,3 };
    vector<int> copy(nums);
    mergeSort(nums, copy, 0, nums.size() - 1);
    nums.assign(copy.begin(), copy.end());
    for_each(nums.begin(), nums.end(), [](const auto& a) {cout << a << " "; });
}

7、设计LRU缓存

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

链接：https://leetcode-cn.com/problems/lru-cache-lcci

struct DoubleList {
    int key, val;
    DoubleList* pre, * next;
    DoubleList(int _key,int _val):key(_key),val(_val),pre(nullptr),next(nullptr){ }
};

class LRU {
private:
    int capacity;
    DoubleList* head, * tail;
    unordered_map<int, DoubleList*> memory;
public:
    LRU(int _capacity) {
        this->capacity = _capacity;
        head = new DoubleList(-1, -1);
        tail = new DoubleList(-1, -1);
        head->next = tail;
        tail->pre = head;
    }
    ~LRU(){
        if (head != nullptr) {
            delete head;
            head = nullptr;
        }
        if (tail != nullptr) {
            delete tail;
            tail = nullptr;
        }
        for (auto& a : memory) {
            if (a.second != nullptr) {
                delete a.second;
                a.second = nullptr;
            }
        }
    }
    void set(int _key, int _val) {
        if (memory.find(_key) != memory.end()) {
            DoubleList* node = memory[_key];
            removeNode(node);
            node->val = _val;
            pushNode(node);
            return ;
        }
        if (memory.size() == this->capacity) {// 这里很重要，也很爱错，千万记得更新memory
            int topKey = head->next->key;//取得key值，方便在后面删除