数组

排序

归并排序

合并两有序数组

合并两个升序有序数组

这里借助了赋值空间help数组，是归并排序中使用的手段，因此归并排序的空间复杂度为O（n），此外归并时，可以保证稳定性，主要体现在当元素相等时，直接赋值左边数组元素。

vector<int> mergeTwoArr(vector<int> &nums1, vector<int> &nums2) {int m = nums1.size(), n = nums2.size();vector<int> help(m + n, 0);int i = 0, j = 0, k =  0;while (i < m && j < n) help[k++] = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++];while (i < m) help[k++] = nums1[i++];while (j < n) help[k++] = nums2[j++];nums1.resize(help.size());copy(help.begin(), help.end(), nums1.begin());
}

归并排序

void merge(vector<int> &nums, int left, int mid, int right) {vector<int> help();help.resize(right - left + 1);int p1 = left, p2 = mid + 1, index = 0;while (p1 <= mid && p2 <= right) help[index++] = nums[p2] < nums[p1] ? nums[p2++] : nums[p1++];while (p1 <= mid) help[index++] = nums[p1++];while (p2 <= right) help[index++] = nums[p2++];copy(help.begin(), help.end(), nums.begin() + left);
}void mergeRecur(vector<int> &nums, int left, int right) {if (left < right) {int mid = left + ((right - left) >> 1);mergeRecur(nums, left, mid);mergeRecur(nums, mid + 1, right);merge(nums, left, mid, right);}	
}void mergeSort(vector<int> &nums) {mergeRecur(nums, 0, nums.size() - 1);
}

快速排序

荷兰旗问题

2161. 根据给定数字划分数组

快速排序

堆排序

基数排序

滑动窗口/双指针

N数之和

15三数之和
18四数之和

四数相加

454. 四数相加 II

链表

环形链表

142环形链表
1、快慢指针法， 如果无环一定快指针先到末尾
2、如果有环，快慢指针在某个时刻相等
3、如果相等，将快指针调回头部，快慢指针都一次一步，两者在入口相遇

ListNode* detectCircle(ListNode* head) {ListNode *slow = head, *fast = head;// 如果无环一定快指针先到末尾while (fast && fast->next) {// 快指针一次两步，慢指针一次一步，如果有环，某个时刻，快指针与慢指针相等slow = slow->next;fast = fast->next->next;// 如果相等，将快指针调回头部，快慢指针都一次一步，两者在入口相遇if (slow == fast) {fast = head;while (slow != fast) {slow = slow->next;fast = fast->next;}return slow;}}return nullptr;
}

重排链表

143重排链表
反转后半条链表，然后重排。
注意利用快慢指针获取链表中间靠左的位置。

    ListNode* reverseList(ListNode* head) {ListNode* cur = head, *pre = nullptr;while (cur) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}void reorderList(ListNode* head) {ListNode* slow = head, *fast = head;// 注意：快慢指针遍历，条件为 while(fast && fast->next)，假定节点长为偶数个，最终慢指针停在中间靠右位置// 而条件为 while (fast->next && fast->next->next) 慢指针最终停在中间靠左位置。假设节点长为奇数，都停中间while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}ListNode* l1 = head, *l2 = slow->next;// 前后半条链表断开，返回后半条链表slow->next = nullptr; l2 = reverseList(l2);// 奇数时，前半条比后半条多一个节点，偶数时长度相同// 将l2的节点每间隔一个串到l1上while (l2) {ListNode* next1 = l1->next, *next2 = l2->next;l1->next = l2;l2->next = next1;l1 = next1;l2 = next2;}}

LRU缓存

146LRU缓存
需要构建一种结构，支持随机访问缓存内容，而又便于删除过期缓存和添加新的缓存。
因此构建如下图所示的由双向链表与哈希表组成的特殊数据结构：

编写时的注意点：
1、头尾使用虚拟伪节点，不计入哈希表结构
2、push新的缓存时，假如哈希表中已有key，还需要将key对应的value更新为最新的value，随后再添加到链表头部
3、先编写在头部添加节点addToHead()和删除某个位置的节点 remove()这样的基础函数。据此构建移动到头部的函数moveToHead。
4、基础的remove函数，仅仅是在链表的某个位置将该节点脱离下来，并没有真正删除节点的指针，因此当容量满了，需要删除过期节点时，需要先将尾结点获取到，随后在链表中remove它，然后再在哈希中erase，最后执行delete操作。

class HashLinkedNode {
public:    int key, val;HashLinkedNode *pre, *next;HashLinkedNode() : key(0), val(0), pre(nullptr), next(nullptr) {}HashLinkedNode(int _key, int _val) : key(_key), val(_val), pre(nullptr), next(nullptr) {}
};class LRUCache {
public:LRUCache(int capacity) : capacity(capacity), size(0) {head = new HashLinkedNode();tail = new HashLinkedNode();head->next = tail;tail->pre = head;}int get(int key) {if (mp.count(key)) {HashLinkedNode* node = mp[key];moveToHead(node);return node->val;}return -1;}void put(int key, int value) {if (mp.count(key)) {  // 如果表中已经有key，直接修改key对应的val值并移动到队列头HashLinkedNode* node = mp[key];node->val = value;moveToHead(node);} else {HashLinkedNode* node = new HashLinkedNode(key, value);mp.insert({key, node});addToHead(node);++size;if (size > capacity) {HashLinkedNode* outNode = removedTail(); mp.erase(outNode->key);delete outNode;--size;}}}void addToHead(HashLinkedNode* node) {node->next = head->next;head->next->pre = node;head->next = node;node->pre = head;}void removedNode(HashLinkedNode* node) {node->pre->next = node->next;node->next->pre = node->pre;}void moveToHead(HashLinkedNode* node) {removedNode(node);addToHead(node);}HashLinkedNode* removedTail() {HashLinkedNode* node = tail->pre;removedNode(node);return node;}private:HashLinkedNode *head, *tail;unordered_map<int, HashLinkedNode*> mp;int size, capacity;
};

栈与队列

栈实现队列/队列实现栈

最小栈/最小队列

单调队列

单调栈

哈希表

字符串

字符串处理

字符串匹配KMP

注意pre已经是前一个位置处的最长的前缀和后缀匹配长度，当不匹配且pre没有后退到0时，则pre后撤 pre = ans[pre];

vector<int> getNext(string str) {if (str.size() == 1) return {-1};vector<int> ans(str.size(), 0);ans[0] = -1;ans[1] = 0;// 从i为2开始, pre是ans[i - 1], 即前一个位置最长公共前后缀int i = 2, pre = 0;while (i < str.size()) {if (str[i- 1] == str[pre]) ans[i++] = ++pre;else if (pre > 0) pre = ans[pre];else ans[i++] = 0;}return ans;
}int strStr(string haystack, string needle) {int m = haystack.size(), n = needle.size();if (m < n) return -1;vector<int> next = getNext(needle);int p1 = 0, p2 = 0;while (p1 < m && p2 < n) {if (haystack[p1] == needle[p2]) {++p1; ++p2;}else if (p2 == 0) ++p1;else p2 = next[p2];}return p2 == n ? p1 - p2 : -1;
}

子串

二叉树

二叉树的遍历方式

递归法

略

迭代法

先序

后序

中序

二叉树的最近公共祖先

235. 二叉搜索树的最近公共祖先
236. 二叉树的最近公共祖先

回溯

动态规划

背包

01背包

完全背包

购买股票

打家劫舍

子序列/子串问题

贪心算法