SUN 从求职材料中拆出的基础题，覆盖 LRU、排序、二分与动态规划。
手撕：LRU（O(1)）
要求：
get(key)
put(key, value)
时间复杂度：
O(1)
核心思路
使用：
hash map + 双向链表
HashMap
作用：
key → node
实现 O(1) 查找。
双向链表
作用：
维护 访问顺序。
最近使用：
头部
最久未使用：
尾部
C++ 实现
#include <unordered_map>
using namespace std;
class LRUCache {
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map<int, Node*> cache;
Node* head;
Node* tail;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insert(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int cap) {
capacity = cap;
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key))
return -1;
Node* node = cache[key];
remove(node);
insert(node);
return node->value;
}
void put(int key, int value) {
if (cache.count(key)) {
Node* node = cache[key];
node->value = value;
remove(node);
insert(node);
return;
}
if (cache.size() == capacity) {
Node* node = tail->prev;
remove(node);
cache.erase(node->key);
}
Node* node = new Node(key, value);
cache[key] = node;
insert(node);
}
};
快排时间复杂度
| 情况 | 复杂度 |
|---|---|
| 最好 | O(n log n) |
| 平均 | O(n log n) |
| 最坏 | O(n²) |
最坏情况：
每次划分极不均匀。
二分查找时间复杂度
时间复杂度：
O(log n)
原因：
每次减少一半数据。
斐波那契递归
递归写法：
F(n) = F(n-1) + F(n-2)
时间复杂度：
O(2^n)
原因：
存在大量重复计算。
斐波那契优化
动态规划
时间复杂度：
O(n)
代码：
int fib(int n) {
if (n <= 1) return n;
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
空间复杂度：
O(1)