侯瑞哲的博客

Ruizhe's Blog

0%

发表于

直播间消息系统的核心挑战：百万并发下的实时推送、消息分类与差异化处理、礼物的可靠投递、弹幕的限流采样，以及扇出问题的分层解决方案。

发表于

从零实现一个 RPC 框架：协议设计、序列化、Netty 网络通信、动态代理、ZooKeeper 服务注册与发现、负载均衡、超时重试，逐层拆解 RPC 的核心设计。

发表于

分布式锁深度解析：从 Redis SET NX、Redlock 算法、ZooKeeper 临时顺序节点，到数据库乐观锁，逐一分析实现原理、适用场景与常见陷阱。

发表于

深入解析 MySQL InnoDB 存储引擎：Buffer Pool、redo/undo log、B+ Tree 索引、MVCC 多版本并发控制、主从复制原理与生产实践。

发表于

QUIC 是 Google 设计、IETF 标准化的新一代传输层协议，也是 HTTP/3 的底层基础。深入解析 0-RTT 握手、多路复用、连接迁移、拥塞控制等核心设计。

发表于

从 ReAct、Plan-and-Execute 到多 Agent 协作，系统梳理 AI Agent 的核心架构模式、Memory 管理、可靠性设计和工程实践。

发表于

Claude Code 是 Anthropic 发布的 AI 编程助手，整个工具打包成一个 13MB 的 npm 包。本文对其解包分析，记录了验证专家 Agent、流式降级、Prompt 缓存分层等有意思的内部实现。

发表于

Spark 是当今最流行的分布式计算框架之一。本文将深入探讨 Spark 的核心架构、RDD 原理、DAG 调度、内存管理以及性能优化策略。

发表于

Apache Kafka是一个分布式流处理平台，以高吞吐量、低延迟、可扩展性和持久性著称，是大数据生态系统中的核心组件。

发表于

Apache Zookeeper是一个开源的分布式协调服务，为分布式应用提供一致性服务。它以简单、高效、可靠著称，是很多分布式系统的基石。

发表于

ClickHouse是一个面向列的OLAP数据库管理系统，以高性能、低延迟、高压缩比著称，是实时数据分析领域的明星产品。

发表于

分布式一致性算法是解决分布式系统中一致性问题的核心理论，包括Paxos、Raft等经典算法，以及2PC、3PC、TCC、Saga等分布式事务方案。

发表于

Apache Lucene是一个高性能、全功能的文本搜索引擎库，完全用Java编写。它是ElasticSearch、Solr等搜索引擎的核心，为全文检索提供了强大的基础设施。

发表于

Rust是一种系统级编程语言，专注于安全性、并发性和性能。它由Mozilla研究院开发，旨在提供C++级别的性能，同时保证内存安全。本文将深入解析Rust的核心概念、特性和最佳实践。

发表于

ElasticSearch 是基于 Lucene 的分布式搜索引擎，以其强大的全文检索、实时分析和可扩展性著称。本文将深入剖析 ElasticSearch 的核心概念、查询语法、聚合分析以及集群架构。

发表于

Flink 是新一代大数据流式计算引擎，以其低延迟、高吞吐、精确一次等特性著称。本文将深入剖析 Flink 的核心架构、运行时机制以及流式计算的关键技术。

发表于

Redis 是高性能的键值存储数据库，以其丰富的数据结构、持久化机制和高可用特性著称。本文将深入剖析 Redis 的核心原理、数据结构、持久化机制以及集群架构。

发表于

索引是数据库优化中最重要的一环。本文将深入探讨 MySQL 索引的原理、类型、失效场景以及优化技巧，帮助你构建高效的数据库查询。

发表于

CUDA（Compute Unified Device Architecture）是 NVIDIA 推出的并行计算平台和编程模型。本文将介绍 CUDA 编程的基础知识，包括环境搭建、基本概念和常用编程技巧。

发表于

GPU（Graphics Processing Unit，图形处理器）最初是为了处理图形渲染而设计的，但随着技术的发展，它已经演变成一种强大的并行计算设备。本文将介绍 GPU 的基本架构和核心概念。

发表于

GPU 并行计算的核心在于其大规模并行处理能力。本文将深入探讨 GPU 并行计算的原理、模型和优化策略。

发表于

GPU 的内存层次结构是其高性能的关键。理解 GPU 的内存层次结构对于编写高效的 CUDA 程序至关重要。本文将详细介绍 GPU 的内存层次结构及其优化策略。

发表于

CPU 和 GPU 的设计理念截然不同，各自擅长不同的任务类型。本文将深入对比 CPU 和 GPU 的架构差异、性能特点以及适用场景。

发表于 Valine：

5535. 括号的最大嵌套深度

比较简单，不贴代码了

5536. 最大网络秩

计算每个点的边，如果两点相连，减去一条重复的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        neigh = defaultdict(set)
        for x, y in roads:
            neigh[x].add(y)
            neigh[y].add(x)
        res = 0

        def maxRank(x, y):
            if y in neigh[x]:
                return len(neigh[x]) + len(neigh[y]) - 1
            return len(neigh[x]) + len(neigh[y])

        for x in range(n):
            for y in range(x + 1, n):
                res = max(res, maxRank(x, y))
        return res

5537. 分割两个字符串得到回文串

找到a b从中心开始的最长回文串，从al, ar, bl, br，然后比较a[:al] == b[ar+1:] or a[:bl] == b[br + 1] or b[:al] == a[ar+1:] or b[:bl] == a[br+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
class Solution:
    def checkPalindromeFormation(self, a: str, b: str) -> bool:
        def isPalindrome(s):
            return s == s[::-1]

        if isPalindrome(a) and isPalindrome(b):
            return True
        n = len(a)

        if n & 1:
            l = r = n >> 1
        else:
            l, r = (n >> 1) - 1, n >> 1
        # print(len(a))
        # print(l, r)
        al, ar = l, r
        while al >= 0 and ar < n and a[al] == a[ar]:
            al -= 1
            ar += 1
        bl, br = l, r
        while bl >= 0 and br < n and b[bl] == b[br]:
            bl -= 1
            br += 1
        # print(a[:al + 1], b[ar:][::-1])
        # print(b[:bl + 1], a[br:][::-1])
        return a[:al + 1] == b[ar:][::-1] or b[:bl + 1] == a[br:][::-1] \
               or b[:al + 1] == a[ar:][::-1] or a[:bl + 1] == b[br:][::-1]

5538. 统计子树中城市之间最大距离

状压枚举所有集合，以集合的每一个点为根顶点，bfs计算这个点为根顶点时的树的高度，最大值即为这个集合构成子树的最大距离

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
class Solution(object):

    def countSubgraphsForEachDiameter(self, n, edges):
        G = [[] for _ in range(n)]
        for i, j in edges:
            G[i - 1].append(j - 1)
            G[j - 1].append(i - 1)

        def maxd(mask0):
            res = 0
            for i in range(n):
                if (1 << i) & mask0:
                    mask = mask0
                    bfs, bfs2 = [i], []
                    cur = 0
                    while bfs:
                        for i in bfs:
                            mask ^= 1 << i
                            for j in G[i]:
                                if mask & (1 << j):
                                    bfs2.append(j)
                        cur += 1
                        bfs, bfs2 = bfs2, []
                    if mask:
                        return 0
                    res = max(res, cur - 1)
            return res

        res = [0] * (n - 1)
        for mask in range(1 << n):
            if mask & (mask - 1) == 0:
                continue
            d = maxd(mask)
            if d:
                res[d - 1] += 1

        return res

AcWing《LeetCode究极班》拼团优惠！https://www.acwing.com/activity/content/introduction/31/group_buy/1154/

发表于 Valine：

5515. 设计停车系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.big = big
        self.medium = medium
        self.small = small

    def addCar(self, carType: int) -> bool:
        if carType == 1:
            if self.big == 0:
                return False
            self.big -= 1
            return True
        elif carType == 2:
            if self.medium == 0:
                return False
            self.medium -= 1
            return True
        else:
            if self.small == 0:
                return False
            self.small -= 1
            return True

5516. 警告一小时内使用相同员工卡大于等于三次的人

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
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        res = set()
        record = defaultdict(list)
        for name, time in zip(keyName, keyTime):
            if name in res:
                continue
            tmp = self.to_minute(time)
            loc = bisect.bisect_left(record[name], tmp)
            record[name].insert(loc, tmp)
            if loc - 2 >= 0 and tmp - record[name][loc - 2] <= 60:
                res.add(name)
                continue
            if loc - 1 >= 0 and loc + 1 < len(record[name]) and record[name][
                loc + 1] - record[name][loc - 1] <= 60:
                res.add(name)
                continue
            if loc + 2 < len(record[name]) and record[name][loc + 2] - tmp <= \
                    60:
                res.add(name)
                continue
        res = list(res)
        res.sort()
        return res

    def to_minute(self, time_str):
        h, m = map(int, time_str.split(":"))
        return h * 60 + m

5518. 给定行和列的和求可行矩阵

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def restoreMatrix(self, rowSum: List[int],
                      colSum: List[int]) -> List[List[int]]:
        m = len(rowSum)
        n = len(colSum)
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                res[i][j] = min(rowSum[i], colSum[j])
                rowSum[i] -= res[i][j]
                colSum[j] -= res[i][j]
        return res

5517. 找到处理最多请求的服务器

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
class Solution:
    def busiestServers(self, ks: int, a: List[int], d: List[int]) -> List[int]:
        from sortedcontainers import SortedList
        ans = [0] * ks
        pq = []
        fu = SortedList(range(ks))
        v = 0
        for i, j in zip(a, d):
            heappush(pq, [i, 1, i + j, v])
            v += 1
        # print(pq,fu)
        while pq:
            i, k, j, num = heappop(pq)
            if k == 1 and fu:
                v = fu.bisect_left(num % ks)
                if v == len(fu):
                    v = 0
                v = fu[v]
                fu.remove(v)
                ans[v] += 1
                heappush(pq, [j, 0, v, num])
            elif k == 0:
                fu.add(j)
            # print(pq,fu)
        # print(ans)
        t = max(ans)
        return [i for i in range(ks) if ans[i] == t]

发表于 Valine：

5531. 特殊数组的特征值

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n + 1):
            c = 0
            for num in nums:
                if num >= i:
                    c += 1
            if c == i:
                return i
        return -1

5532. 奇偶树

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
class Solution:
    def isEvenOddTree(self, root: TreeNode) -> bool:
        q, nq = [root], []
        flag = True
        while q:
            if flag:
                pre = float('-inf')
                for node in q:
                    if node.val & 1 == 0 or node.val <= pre:
                        return False
                    pre = node.val
                    if node.left:
                        nq.append(node.left)
                    if node.right:
                        nq.append(node.right)
            else:
                pre = float('inf')
                for node in q:
                    if node.val & 1 == 1 or node.val >= pre:
                        return False
                    pre = node.val
                    if node.left:
                        nq.append(node.left)
                    if node.right:
                        nq.append(node.right)
            q, nq = nq, []
            flag = not flag
        return True

5534. 可见点的最大数目

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
class Solution:
    def visiblePoints(self, points: List[List[int]],
                      angle: int, location: List[int]) -> int:
        import math
        angle = angle / 360 * 2 * math.pi
        cnt = 0
        a = []
        for x, y in points:
            if x == location[0] and y == location[1]:
                cnt += 1
            else:
                xx, yy = x - location[0], y - location[1]
                a.append(math.atan2(yy, xx))
        a.sort()
        n = len(a)
        b = [x + math.pi * 2 for x in a]
        a += b
        j = 0

        ret = 0
        for i in range(n):
            while j < len(a):
                if a[j] - a[i] > angle:
                    break
                j += 1
            ret = max(ret, j - i)
        return ret + cnt

5533. 使整数变为 0 的最少操作次数

1
2
3
4
5
6
7
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n:
            ans ^= n
            n >>= 1
        return ans
1
2
3
4
5
6
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0
        p = n.bit_length()
        return (1 << p) - 1 - self.minimumOneBitOperations(n - (1 << (p - 1)))

两种做法

发表于 Valine：

1. 文件夹操作日志搜集器

简单模拟

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minOperations(self, logs: List[str]) -> int:
        cur = 0
        for log in logs:
            if log == '../':
                if cur:
                    cur -= 1
            elif log == './':
                continue
            else:
                cur += 1
        return cur

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
class Solution:
    def minOperationsMaxProfit(self, customers: List[int],
                               boardingCost: int, runningCost: int) -> int:
        ans = 0
        res = 0
        p = 0
        w = 0
        i = 0
        for c in customers:
            i += 1
            w += c
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        while w:
            i += 1
            b = min(w, 4)
            w -= b
            p += b * boardingCost - runningCost
            if p > res:
                res = p
                ans = i
        return ans if ans else -1

3. 皇位继承顺序

树节点的设计，和dfs先序遍历

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
class TreeNode:
    def __init__(self, name):
        self.name = name
        self.children = []
        self.is_death = False


class ThroneInheritance:

    def __init__(self, kingName: str):
        self.root = TreeNode(kingName)
        self.mem = {kingName: self.root}

    def birth(self, parentName: str, childName: str) -> None:
        p_node = self.mem[parentName]
        c_node = TreeNode(childName)
        p_node.children.append(c_node)
        self.mem[childName] = c_node

    def death(self, name: str) -> None:
        node = self.mem[name]
        node.is_death = True

    def getInheritanceOrder(self) -> List[str]:
        res = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            if not node.is_death:
                res.append(node.name)
            for child in reversed(node.children):
                stack.append(child)
        return res

4. 最多可达成的换楼请求数目

状态压缩dp，以及了解图中任何一个节点入度与出度相等时，就满足净变化为0

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
class Solution {
    int tot[25];
public:
    int maximumRequests(int n, vector<vector<int>> &req) {
        int ans = 0;
        int m = req.size();
        int lim = (1 << m) - 1;
        for (int i = 1; i <= lim; ++i) {
            for (int j = 0; j < n; ++j) tot[j] = 0;
            int cnt = 0;
            for (int j = 0, k = 1; j < m; ++j, k <<= 1)
                if (i & k) {
                    ++tot[req[j][1]], --tot[req[j][0]];
                    ++cnt;
                }
            bool flag = true;
            for (int j = 0; j < n; ++j) {
                if (tot[j] != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) ans = max(ans, cnt);
        }
        return ans;
    }
};

发表于 Valine：

1. K步编辑

描述

给出一个只含有小写字母的字符串的集合以及一个目标串(target)，输出所有可以经过不多于 k 次操作得到目标字符串的字符串。

你可以对字符串进行一下的3种操作:

  • 加入1个字母
  • 删除1个字母
  • 替换1个字母

思路：一个应用编辑距离的问题，使用python语言会超时。

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
class Solution {
public:
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */

    int minDistance(string word1, string word2, int k) {
        int m = word1.size();
        int n = word2.size();
        if (m - n > k || n - m > k) return k + 1;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[m][n];
    }

    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> res;
        for (auto &word: words) {
            if (minDistance(word, target, k) <= k) {
                res.push_back(word);
            }
        }
        return res;
    }
};

2. 折纸

描述

折纸，每次都是将纸从右向左对折，凹痕为 0，凸痕为 1，求折 n 次后，将纸展开所得折痕组成的 01 序列。

1<=n<=20

思路：类似中序遍历，加入一个是正是反的变量，模拟折纸过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    """
    @param n: The folding times
    @return: the 01 string
    """

    def getString(self, n):
        # Write your code here
        def printProcess(i, N, down):
            if i > N:
                return
            printProcess(i + 1, N, True)
            if down is True:
                res.append('0')
            else:
                res.append('1')
            printProcess(i + 1, N, False)

        res = []
        printProcess(1, n, True)
        return "".join(res)

3. 字符串的不同排列

描述

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。 请以字典序从小到大输出。 0<=n<=20

思路：提前去重，输出排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    """
    @param str: A string
    @return: all permutations
    """

    def stringPermutation(self, s):
        # write your code here
        li = list(s)
        li.sort()
        q, nq = [""], []
        for char in li:
            for ans in q:
                for i in range(len(ans), -1, -1):
                    if i < len(ans) and char == ans[i]:
                        break
                    nq.append(ans[:i] + char + ans[i:])
            q, nq = nq, []
        q.sort()
        return q

4. 硬币排成线

描述

有 n 个硬币排成一条线, 第 i 枚硬币的价值为 values[i].

两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.

请判定 第一个玩家 会赢还是会输.

1<=n<=2000 0<=value[i]<=1e7

思路：一个常见的dp问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """

    def firstWillWin(self, values):
        # write your code here
        n = len(values)
        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = values[i]
        for gap in range(1, n):
            for i in range(n - gap):
                j = i + gap
                left = dp[i + 1][j][1] + values[i]
                right = dp[i][j - 1][1] + values[j]
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i + 1][j][0]
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j - 1][0]
        return dp[0][n - 1][0] > dp[0][n - 1][1]

PS: 今天第一次答阿里云，阿里云的罚时有点多，罚时时间还没有写出来，要注意有十足的保证再提交

发表于 Valine：

上帝，请赐予我平静，

去接受我无法改变的。

给予我勇气，

去改变我能改变的，

赐我智慧，

分辨这两者的区别。

过好我的每一天，

享受你所赐每一刻，

把困苦当成通往平安的道路，

像主耶稣那样，接受这罪恶的世界，

按其现实本相，而非如我所愿

相信他会使一切变得美好，

只要我顺服他的旨意；

我可以在此生有合宜的欢乐，

并在永生里，与他永享至福。

阿门。

无神论者，只是汲取其中的营养

发表于 Valine：

桶排序适用于待排序数据值域较大但分布比较均匀的情况，是一个期望时间复杂度为O(n)的排序算法。

其大致思想是对值域进行分块，每块分别排序。由于每块元素不多，一般使用插入排序。如果使用稳定的内层排序，并且将元素插入桶中时不改变相对顺序，那么桶排序就是稳定的。

如果待排序数据是随机生成的，将值域平均分成n块的期望时间复杂度是O(n)，证明可以参考算法导论或维基百科。

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
const int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A{j};
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; k < bucket[i].size() ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

发表于 Valine： 
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
void max_heapify(int arr[], int start, int end) {
  // 建立父结点指标和子结点指标
  int dad = start;
  int son = dad * 2 + 1;
  while (son <= end) {  // 子结点指标在范围内才做比较
    if (son + 1 <= end && arr[son] < arr[son + 1])  // 先比较两个子结点大小，选择最大的
      son++;
    if (arr[dad] > arr[son])  // 如果父结点比子结点大，代表调整完毕，直接跳出函数
      return;
    else {  // 否则交换父子内容，子结点再和孙结点比较
      swap(arr[dad], arr[son]);
      dad = son;
      son = dad * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // 初始化，i从最后一个父结点开始调整
  for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1);
  // 先将第一个元素和已经排好序的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    max_heapify(arr, 0, i - 1);
  }
}