第45周：算法与数据结构刷题

字数统计: 3.5k字   |   阅读时长≈ 17分

第45周：算法与数据结构刷题

目标：高频算法题熟练度达到大厂面试要求，重点突破哈希表、链表、树、图、DP。

1. 刷题策略

1.1 每日计划

1
2
3
4
5
6
7
8
每日刷题时间分配（建议 2-3 小时）：

  早晨 30 分钟：复习昨日错题
  上午 60 分钟：新题 2 道（中等难度）
  下午 60 分钟：复杂题 1 道（Hard）
  晚上 30 分钟：看题解、写总结

  每周：周末刷 5-10 道大厂真题

1.2 题目分类（按频率）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
大厂面试高频（必会）：

  链表（10-15%）：
    - 反转链表
    - 链表环检测
    - 合并有序链表
    - LRU/LFU 缓存
    - 链表排序

  哈希表（10%）：
    - 两数之和
    - 字母异位词分组
    - 最小覆盖子串
    - LRU 缓存

  树（15-20%）：
    - 二叉树遍历（递归 + 迭代）
    - 层序遍历（BFS）
    - BST 验证
    - 路径和系列

  图（10%）：
    - 岛屿数量
    - 课程表（拓扑排序）
    - 最短路径
    - 单词接龙

  动态规划（20-30%）：
    - 爬楼梯 / 打家劫舍（入门）
    - 零钱兑换
    - 最长子序列（LCS/LIS）
    - 背包问题
    - 编辑距离
    - 股票买卖

  二分查找（10%）：
    - 经典二分
    - 旋转数组
    - 寻找峰值
    - 搜索二维矩阵

  栈/队列（5%）：
    - 有效括号
    - 最小栈
    - 滑动窗口最大值

  字符串（5-10%）：
    - 反转字符串
    - 最长回文子串
    - 字符串匹配

1.3 大厂真题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
腾讯（TEG/微信/CDG）高频：

  1. LRU 缓存（146）- 哈希+双向链表
  2. 反转链表（206）
  3. 二叉树的层序遍历（102）
  4. 最长回文子串（5）
  5. 接雨水（42）
  6. 编辑距离（72）
  7. 课程表（207）
  8. 全排列（46）
  9. 合并 K 个升序链表（23）
  10. 滑动窗口最大值（239）

字节跳动高频：

  1. 二叉树的最近公共祖先（236）
  2. 岛屿数量（200）
  3. 寻找峰值（162）
  4. 接雨水（42）
  5. 最大子序和（53）
  6. 字符串转整数（8）
  7. 环形链表 II（142）
  8. 删除链表的倒数第 N 个结点（19）
  9. K 个一组翻转链表（25）
  10. 搜索旋转排序数组（33）

2. 网络方向专项练习

2.1 LRU 缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 146. LRU Cache (最近最少使用)
// 数据结构：哈希表 + 双向链表
// - 哈希表：O(1) 查找
// - 双向链表：O(1) 移动

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct lru_node {
    int key;
    int val;
    struct lru_node *prev;
    struct lru_node *next;
};

#define HASH_SIZE 10007

struct lru_cache {
    int capacity;
    int size;
    struct lru_node *head;  // 哨兵（最久未使用）
    struct lru_node *tail;  // 哨兵（最近使用）
    struct lru_node *table[HASH_SIZE];  // 哈希表
};

struct lru_cache *lru_create(int capacity);
int lru_get(struct lru_cache *cache, int key);
void lru_put(struct lru_cache *cache, int key, int value);
void lru_free(struct lru_cache *cache);

// 哈希函数
static unsigned int hash(int key) {
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = (key >> 16) ^ key;
    return key % HASH_SIZE;
}

struct lru_cache *lru_create(int capacity) {
    struct lru_cache *c = malloc(sizeof(*c));
    c->capacity = capacity;
    c->size = 0;
    c->head = malloc(sizeof(struct lru_node));
    c->tail = malloc(sizeof(struct lru_node));
    c->head->next = c->tail;
    c->tail->prev = c->head;
    memset(c->table, 0, sizeof(c->table));
    return c;
}

// 将节点移到链表头（最近使用）
static void move_to_head(struct lru_cache *c, struct lru_node *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;

    node->next = c->head->next;
    node->prev = c->head;
    c->head->next->prev = node;
    c->head->next = node;
}

// 移除最久未使用（tail->prev）
static struct lru_node *remove_tail(struct lru_cache *c) {
    struct lru_node *node = c->tail->prev;
    node->prev->next = c->tail;
    c->tail->prev = node->prev;
    return node;
}

int lru_get(struct lru_cache *c, int key) {
    unsigned int h = hash(key);
    struct lru_node *node = c->table[h];
    while (node) {
        if (node->key == key) {
            move_to_head(c, node);
            return node->val;
        }
        node = node->next;  // 简化：实际应使用链表/红黑树
    }
    return -1;
}

void lru_put(struct lru_cache *c, int key, int value) {
    unsigned int h = hash(key);
    struct lru_node *node = c->table[h];
    while (node) {
        if (node->key == key) {
            node->val = value;
            move_to_head(c, node);
            return;
        }
        node = node->next;
    }

    // 新 key
    if (c->size == c->capacity) {
        // 淘汰最久未使用
        struct lru_node *removed = remove_tail(c);
        // 从哈希表移除
        unsigned int rh = hash(removed->key);
        c->table[rh] = NULL;  // 简化
        free(removed);
        c->size--;
    }

    node = malloc(sizeof(*node));
    node->key = key;
    node->val = value;
    node->next = c->table[h];
    c->table[h] = node;
    move_to_head(c, node);
    c->size++;
}

2.2 令牌桶（限速算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 限速器：令牌桶算法
// 用途：限速、平滑流量

struct token_bucket {
    int capacity;       // 桶容量
    int tokens;         // 当前令牌数
    int rate;           // 每秒生成速率
    long last_update;   // 上次更新时间（ms）
};

struct token_bucket *tb_create(int capacity, int rate) {
    struct token_bucket *tb = malloc(sizeof(*tb));
    tb->capacity = capacity;
    tb->tokens = capacity;
    tb->rate = rate;
    tb->last_update = current_time_ms();
    return tb;
}

// 是否允许（及扣除令牌）
int tb_allow(struct token_bucket *tb, int cost) {
    long now = current_time_ms();
    long elapsed = now - tb->last_update;

    // 补充令牌
    int add = (elapsed * tb->rate) / 1000;
    tb->tokens = min(tb->capacity, tb->tokens + add);
    tb->last_update = now;

    if (tb->tokens >= cost) {
        tb->tokens -= cost;
        return 1;  // 允许
    }
    return 0;  // 拒绝
}

// 滑动窗口版（更精确）
struct sliding_window {
    int window_size;     // 窗口大小（ms）
    int max_count;      // 窗口内最大请求数
    int *timestamps;     // 窗口内所有请求时间戳
    int count;           // 当前数量
};

int sw_allow(struct sliding_window *sw) {
    long now = current_time_ms();
    long window_start = now - sw->window_size;

    // 移除过期的
    while (sw->count > 0 && sw->timestamps[0] < window_start) {
        // 移除
        memmove(sw->timestamps, sw->timestamps + 1,
                (sw->count - 1) * sizeof(int));
        sw->count--;
    }

    if (sw->count < sw->max_count) {
        sw->timestamps[sw->count++] = now;
        return 1;
    }
    return 0;
}

2.3 位图统计（10 亿数找重）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 位图：节省空间的布尔数组
// 用途：去重、布隆过滤器

#include <stdint.h>

struct bitmap {
    uint64_t *bits;
    int size;        // 位数
    int n_words;     // uint64_t 数量
};

struct bitmap *bitmap_create(int size) {
    struct bitmap *bm = malloc(sizeof(*bm));
    bm->size = size;
    bm->n_words = (size + 63) / 64;
    bm->bits = calloc(bm->n_words, sizeof(uint64_t));
    return bm;
}

static inline int bitmap_get(struct bitmap *bm, int pos) {
    return (bm->bits[pos / 64] >> (pos % 64)) & 1;
}

static inline void bitmap_set(struct bitmap *bm, int pos) {
    bm->bits[pos / 64] |= (1ULL << (pos % 64));
}

// 10 亿数（int32 范围）去重
// 需要 2^31 / 8 = 256MB 内存

// 布隆过滤器（多 hash，可假阳性）
struct bloom_filter {
    struct bitmap *bm;
    int n_hash;
    int (*hashes[8])(const void *);
};

int bloom_may_contain(struct bloom_filter *bf, const void *key) {
    for (int i = 0; i < bf->n_hash; i++) {
        int h = bf->hashes[i](key) % bf->bm->size;
        if (!bitmap_get(bf->bm, h)) return 0;  // 一定不存在
    }
    return 1;  // 可能存在（有假阳性）
}

2.4 超时轮（时间轮）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 哈希时间轮：O(1) 定时器
// 用途：Netty/Kafka 等大量连接的超时管理

struct timer_node {
    int id;
    int expire_time;     // 过期时间（ticks）
    void (*callback)(int id);
    struct timer_node *next;
};

#define WHEEL_SIZE 512
#define TICK_MS 10

struct timer_wheel {
    struct timer_node *slots[WHEEL_SIZE];
    int current_tick;     // 当前指针
    int cur_time;         // 当前时间
};

void tw_add(struct timer_wheel *tw, int id, int delay_ms,
            void (*cb)(int)) {
    int ticks = delay_ms / TICK_MS;
    int slot = (tw->current_tick + ticks) % WHEEL_SIZE;

    struct timer_node *node = malloc(sizeof(*node));
    node->id = id;
    node->expire_time = tw->cur_time + ticks;
    node->callback = cb;
    node->next = tw->slots[slot];
    tw->slots[slot] = node;
}

// 时钟滴答
void tw_tick(struct timer_wheel *tw) {
    struct timer_node *node = tw->slots[tw->current_tick];
    while (node) {
        struct timer_node *next = node->next;
        if (node->expire_time <= tw->cur_time) {
            node->callback(node->id);
            free(node);
        }
        node = next;
    }
    tw->slots[tw->current_tick] = NULL;
    tw->current_tick = (tw->current_tick + 1) % WHEEL_SIZE;
    tw->cur_time++;
}

3. 高频数据结构实现

3.1 二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 二叉树基本结构
struct tree_node {
    int val;
    struct tree_node *left;
    struct tree_node *right;
};

// 递归遍历
void inorder(struct tree_node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

// 迭代遍历（用栈模拟递归）
void inorder_iter(struct tree_node *root) {
    struct tree_node *stack[1000];
    int top = 0;
    struct tree_node *cur = root;

    while (cur || top > 0) {
        while (cur) {
            stack[top++] = cur;
            cur = cur->left;
        }
        cur = stack[--top];
        printf("%d ", cur->val);
        cur = cur->right;
    }
}

// 层序遍历（BFS）
void bfs(struct tree_node *root) {
    if (!root) return;
    struct tree_node *queue[1000];
    int head = 0, tail = 0;
    queue[tail++] = root;
    while (head < tail) {
        struct tree_node *n = queue[head++];
        printf("%d ", n->val);
        if (n->left)  queue[tail++] = n->left;
        if (n->right) queue[tail++] = n->right;
    }
}

3.2 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 经典 DP 问题
// 1. 爬楼梯（70）
int climb_stairs(int n) {
    if (n <= 2) return n;
    int dp[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 2. 零钱兑换（322）
int coin_change(int *coins, int n, int amount) {
    int dp[amount + 1];
    for (int i = 0; i <= amount; i++) dp[i] = amount + 1;
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < n; j++) {
            if (i >= coins[j] && dp[i - coins[j]] + 1 < dp[i]) {
                dp[i] = dp[i - coins[j]] + 1;
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// 3. 最长公共子序列（1143）
int lcs(char *s1, char *s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = 0;
    for (int j = 0; j <= n; j++) dp[0][j] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

3.3 图算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 邻接表表示
struct graph {
    int n;
    struct adj_list *adj;
};

struct adj_list {
    int dest;
    struct adj_list *next;
};

void graph_add_edge(struct graph *g, int src, int dest) {
    struct adj_list *node = malloc(sizeof(*node));
    node->dest = dest;
    node->next = g->adj[src].next;
    g->adj[src].next = node;
}

// BFS 最短路径
int bfs_shortest(struct graph *g, int src, int dest) {
    int *dist = malloc(g->n * sizeof(int));
    int *visited = calloc(g->n, sizeof(int));
    int queue[g->n];
    int head = 0, tail = 0;

    queue[tail++] = src;
    visited[src] = 1;
    dist[src] = 0;

    while (head < tail) {
        int u = queue[head++];
        if (u == dest) {
            int d = dist[u];
            free(dist); free(visited);
            return d;
        }
        for (struct adj_list *p = g->adj[u].next; p; p = p->next) {
            if (!visited[p->dest]) {
                visited[p->dest] = 1;
                dist[p->dest] = dist[u] + 1;
                queue[tail++] = p->dest;
            }
        }
    }
    free(dist); free(visited);
    return -1;
}

// 拓扑排序
int topological_sort(struct graph *g, int *result) {
    int *in_degree = calloc(g->n, sizeof(int));
    for (int u = 0; u < g->n; u++) {
        for (struct adj_list *p = g->adj[u].next; p; p = p->next) {
            in_degree[p->dest]++;
        }
    }

    int queue[g->n];
    int head = 0, tail = 0;
    for (int i = 0; i < g->n; i++) {
        if (in_degree[i] == 0) queue[tail++] = i;
    }

    int count = 0;
    while (head < tail) {
        int u = queue[head++];
        result[count++] = u;
        for (struct adj_list *p = g->adj[u].next; p; p = p->next) {
            if (--in_degree[p->dest] == 0) {
                queue[tail++] = p->dest;
            }
        }
    }

    free(in_degree);
    return count;  // count == n 才是有效拓扑
}

4. 刷题模板与套路

4.1 链表模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 链表通用操作
struct list_node {
    int val;
    struct list_node *next;
};

// 1. 反转链表
struct list_node *reverse(struct list_node *head) {
    struct list_node *prev = NULL, *cur = head;
    while (cur) {
        struct list_node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// 2. 找链表中点（快慢指针）
struct list_node *middle(struct list_node *head) {
    struct list_node *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 3. 检测环
int has_cycle(struct list_node *head) {
    struct list_node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

4.2 二分模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 经典二分：找目标
int binary_search(int *nums, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 找左边界
int lower_bound(int *nums, int n, int target) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

4.3 DP 套路

1
2
3
4
5
6
7
8
9
10
11
12
DP 三步法：
  1. 定义 dp[i] 是什么（状态）
  2. 找状态转移方程
  3. 确定初始值和遍历顺序

类型：
  1. 线性 DP：爬楼梯、最大子序和
  2. 区间 DP：最长回文子序列、戳气球
  3. 背包 DP：0-1 背包、完全背包
  4. 状态机 DP：股票买卖（带状态）
  5. 树形 DP：树的直径、路径和
  6. 状压 DP：旅行商问题（TSP）

5. 面试中的算法题

5.1 沟通技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
面试中解题流程：

  1. 澄清问题（5 分钟）
     - 输入范围？
     - 边界条件？
     - 时间/空间要求？
     - 示例验证

  2. 思考算法（5 分钟）
     - 先讲思路，不写代码
     - 分析复杂度
     - 讨论多种方案

  3. 写代码（15-20 分钟）
     - 边写边讲解
     - 命名清晰
     - 关键处加注释

  4. 测试（5 分钟）
     - 用给的示例验证
     - 自己造边界用例
     - 空输入、单元素、全相同等

  5. 优化（如时间允许）
     - 是否能更优？
     - 空间换时间？
     - 改写为更简洁的代码

5.2 常见面试题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
字节跳动算法面试题：

  简单：
  - 两数之和（1）
  - 反转链表（206）
  - 二分查找（704）
  - 合并两个有序数组（88）
  - 有效的括号（20）

  中等：
  - LRU 缓存（146）
  - 二叉树的层序遍历（102）
  - 岛屿数量（200）
  - 课程表（207）
  - 接雨水（42）
  - 全排列（46）
  - 最长回文子串（5）
  - 跳跃游戏（55）

  Hard：
  - 滑动窗口最大值（239）
  - 接雨水 II（407）
  - 编辑距离（72）
  - K 个一组翻转链表（25）

  经典：
  - 实现 LRU / LFU
  - 实现线程池
  - 实现一致性哈希
  - 实现限流器
  - 实现分布式锁

5.3 大厂风格题

1
2
3
4
5
6
7
// 1. 设计一个限流器（令牌桶）
// 2. 实现 LRU 缓存（O(1)）
// 3. 实现内存池（线程安全）
// 4. 实现无锁队列
// 5. 实现定时器（时间轮）
// 6. 实现读写锁
// 7. 实现协程（ucontext/swapcontext）

6. 时间安排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
每周刷题计划（建议 20-30 题）：

  周一：链表（3 道）
  周二：栈/队列（2 道）+ 字符串（1 道）
  周三：哈希表（2 道）+ 树（1 道）
  周四：图（2 道）+ 高级数据结构（1 道）
  周五：动态规划（3 道）
  周六：模拟面试（2-3 道大厂真题）
  周日：错题复习 + 难题补强

  月度目标：
    - 200+ 题
    - 覆盖每个类型至少 20 道
    - 错题本累积
    - 简单题 5 分钟内 AC
    - 中等题 15-25 分钟
    - Hard 题 30-40 分钟

7. 关键资源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
刷题平台：
  - LeetCode（中文站 / 国际站）
  - 牛客网（国内大厂真题）
  - LintCode
  - HackerRank

书籍：
  - 《剑指 Offer》（第二版）
  - 《编程之美》
  - 《算法导论》（深入理解）
  - 《算法竞赛入门经典》

题解：
  - LeetCode 题解（官方 / 三叶 / 灵茶）
  - 各大厂面经（牛客、知乎）
  - 代码随想录
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、Linux开发、
公众号开发、开源爱好者、Linux

联系QQ:562054870