算法

//归并排序
void helper(vector<int> &nums, int start, int mid , int end) {
    int i = start, j = mid + 1;
    vector<int> temp;
    while (i <= mid && j <= end) {
        if (nums[i] > nums[j]) {
            temp.push_back(nums[j]);
            j++;
        }
        else {
            temp.push_back(nums[i]);
            i++;
        }
    }
    while (i <= mid) {
        temp.push_back(nums[i]);
        i++;
    }
    while (j <= end) {
        temp.push_back(nums[j]);
        j++;
    }
    for(int k = start; k <= end; k++)
        nums[k] = temp[k - start];
}

void mergeSort(vector<int> &nums, int i, int j) {
    if (i < j) {
        int mid = (i + j) / 2;
        mergeSort(nums, i, mid);
        mergeSort(nums, mid + 1, j);
        helper(nums, i, mid, j);
    }
}

//快速排序
int partition(vector<int> &nums, int start, int end) {
    int i = start, j = end;
    int pivot = nums[start];
    while (i < j) {
        while (i < j && nums[j] >= pivot)
            j--;
        nums[i] = nums[j];
        while (i < j && nums[i] <= pivot)
            i++;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    return i;
}
void quickSort(vector<int> &nums, int start, int end) {
    if (start <= end) {
        int pos = partition(nums, start, end);
        quickSort(nums, start, pos - 1);
        quickSort(nums, pos + 1, end);
    }
}

//因为下标从0开始，不是从1开始，所以不是2x 和 2x + 1;
#define left(x) 2*x+1;//获得左节点在数组中的下标
#define right(x) 2 * (x + 1);//获得右节点在数组中的下标
//假定对某一个节点i其左，右子树都是都是最大堆，但是对于节点i和它的左右子节点则可能破坏最大堆的性质，我们来写一个函数对这
//情况下的堆来进行维护使整体的堆满足最大堆性质
void MaxHeapify(vector<int> &a, int i, int low, int high)//输入为要被排序的数组和根节点，数组a当中被维护的那一部分的下标low，high
{
    int l = left(i);//计算下标为i的节点的左子节点
    int r = right(i);//计算下标为i的节点的右子节点
    int largest;//保存i,l,r(即i和它的左右子节点)之间的最大数的下标
    int temp;//交互数组中的数所使用的临时变量
    //找到三个数当中最大的那个数，将最大的那个数和i进行互换
    if (l <= high && a[l] > a[i])
    {
        largest = l;
    }
    else {
        largest = i;
    }

    if (r <= high && a[r] > a[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        MaxHeapify(a, largest, low, high);//交换有可能破坏子树的最大堆性质，所以对所交换的那个子节点进行一次维护，而未交换的那个子节点，根据我们的假设，是保持着最大堆性质的。
    }
}
//将数组建立为一个最大堆
//调整数组当中数的位置将其处理为一个最大堆
void BuildMaxHeap(vector<int> &a)
{
    int length = a.size();
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        MaxHeapify(a, i, 0, length - 1);
    }
}
//堆排序函数
void HeapSort(vector<int> &a)
{
    int length = a.size();
    BuildMaxHeap(a);
    for (int i = length - 1; i >= 1; i--)
    {
        //交换根节点和数组的最后一个节点
        swap(a[0], a[i]);
        MaxHeapify(a, 0, 0, i - 1);//维护从下标为i-1到0的子数组
    }
}

LRU:

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;    
    }
    
    int get(int key) {
        if(valueHash.count(key) == 0)
            return -1;
        update(key);
        return valueHash[key];
    }
    
    void put(int key, int value) {
        if(valueHash.count(key) == 0 && valueHash.size() == size)
            del(key);
        update(key);
        valueHash[key] = value;
    }
    void update(int key){
        if(valueHash.count(key))
            lru.erase(posHash[key]);
        lru.push_front(key);
        posHash[key] = lru.begin();
    }
    void del(int key){
        valueHash.erase(lru.back());
        posHash.erase(lru.back());
        lru.pop_back();
    }
private:
    int size;
    list<int> lru;
    unordered_map<int, list<int>::iterator> posHash;
    unordered_map<int, int> valueHash;
};

注意要点:

• 递归对于vector容器：

//错误写法
void helper(vector<int> &temp){
    temp.push_back(1);
    helper(temp);
}
//正确写法
void helper(vector<int> temp){
    temp.push_back(1);
    helper(temp);
    temp.pop_back();
}