Adrian Wang's blog

什么是索引？ 索引是数据库中用于提高查询效率的数据结构，类似于书籍的目录，帮助数据库系统快速定位和访问数据。合理的索引设计可以显著提升查询性能，减少资源消耗。 索引的分类 按数据结构分类 B+tree 索引：MySQL 默认索引类型，适用于范围查询和排序 Hash 索引：适合等值查询，不支持范围查询和排序 Full-text 索引：用于全文搜索，支持复杂文本查询 B+tree 索引(InnoDB 默认索引类型) InnoDB 是在 MySQL 5.5 之后成为默认的 MySQL 存储引擎，B+Tree 索引类型也是 MySQL 存储引擎采用最多的索引类型。 在创建表时，InnoDB 存储引擎会根据不同的场景选择不同的列作为索引： 如果有主键，默认会使用主键作为聚簇索引的索引键（key）； 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键（key）； 在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键（key）； 其它索引都属于辅助索引（Secondary Index），也被称为二级索引或非聚簇索引。创建的主键索引和二级索引默认使用的是 B+Tree 索引。 B+Tree 是一种多叉树，叶子节点才存放数据，非叶子节点只存放索引，而且每个节点里的数据是按主键顺序存放的。每一层父节点的索引值都会出现在下层子节点的索引值中，因此在叶子节点中，包括了所有的索引值信息，并且每一个叶子节点都指向下一个叶子节点，形成一个链表。 举个例子，先创建一张商品表，id 为主键，如下： 1234567CREATE TABLE `product` ( `id` int(11) NOT NULL, `product_no` varchar(20) DEFAULT NULL, `name` varchar(255) DEFAULT NULL, `price` decimal(10, 2) DEFAULT NULL, PRIMARY KEY (`id`) USING BTREE) CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic; 商品表里，有这些行数据： 主键索引的 B+Tree 如图所示(图中画的叶子节点用单向链表连接，但是有问题，实际上其实是一个 <font color="red">双向链表 </font>)： 通过主键查询数据的过程 比如我们执行了下面这条 SQL 语句： 1SELECT * FROM product WHERE id = 5; 这条语句使用了主键索引查询 id 号为 5 的商品。查询过程是这样的，B+Tree 会自顶向下逐层进行查找： 将 5 与根节点的索引数据 (1，10，20) 比较，5 在 1 和 10 之间，所以根据 B+Tree 的搜索逻辑，找到第二层的索引数据 (1，4，7)； 在第二层的索引数据 (1，4，7) 中进行查找，因为 5 在 4 和 7 之间，所以找到第三层的索引数据（4，5，6）； 在叶子节点的索引数据（4，5，6）中进行查找，然后我们找到了索引值为 5 的行数据。 数据库的索引和数据都是存储在硬盘的，我们可以把读取一个节点当作一次磁盘 I/O 操作。那么上面的整个查询过程一共经历了 3 个节点，也就是进行了 3 次 I/O 操作。 B+Tree 存储千万级的数据只需要 3-4 层高度就可以满足，这意味着从千万级的表查询目标数据最多需要 3-4 次磁盘 I/O，所以B+Tree 相比于 B 树和二叉树来说，最大的优势在于查询效率很高，因为即使在数据量很大的情况，查询一个数据的磁盘 I/O 依然维持在 3-4 次。 通过二级索引查询数据的过程 主键索引的 B+Tree 和二级索引的 B+Tree 的主要区别在于： 主键索引的 B+Tree 的叶子节点存放的是实际数据 二级索引的 B+Tree 的叶子节点存放的是主键值 假设我们将先前的商品表的 product_no 字段创建一个二级索引，如下： 1CREATE INDEX idx_product_no ON product(product_no); 那么，二级索引的 B+Tree 如图所示(图中画的叶子节点用单向链表连接，但是有问题，实际上其实是一个 <font color="red">双向链表 </font>)： 其中非叶子节点的 key值是 product_no(图中橙色部分),叶子节点存储的数据是 主键值(图中绿色部分) 如果我用 product_no二级索引查询，如下查询语句: 1select * from product where product_no = '0002'; 上面的语句可以先检查二级索引中的 B+Tree 的索引值 product_no，找到对应的叶子节点，获取到主键值，然后拿着主键值去主键索引的 B+Tree 中查找，获取到完整的数据行。这个过程就叫做回表，也就是说要查两个 B+Tree 才能查到数据，如图所示(图中画的叶子节点用单向链表连接，但是有问题，实际上其实是一个 <font color="red">双向链表 </font>)。 不过，如果我执行的查询语句是： 1select id from product where product_no = '0002'; 那么，因为二级索引的叶子节点存储的是主键值，所以其实只需要查一个 B+Tree 就可以获取到数据，那就可以避免回表，这个过程就叫做覆盖索引，也就是只需要查一个 B+Tree 就可以获取到数据。 因此，有时候我们可以利用覆盖索引，来避免回表，从而提高查询效率，比如对经常需要查询的列和查询条件建立联合索引，就可以利用覆盖索引，从而提高查询效率。 为什么 InnoDB 存储引擎选择使用 B+Tree 作为索引的数据结构？ 前面已经讲了 B+Tree 的索引原理，现在就来回答一下 B+Tree 相比于 B 树、二叉树或 Hash 索引结构的优势在哪儿？ 1、B+Tree vs B Tree B+Tree 只在叶子节点存储数据，而 B 树 的非叶子节点也要存储数据，所以 B+Tree 的单个节点的数据量更小，在相同的磁盘 I/O 次数下，就能查询更多的节点。 另外，B+Tree 叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。 2、B+Tree vs 二叉树 对于存储了 M 条数据记录的 B+Tree（其叶子节点数量 N 与 M 相关），其搜索复杂度约为 O(logdN)，其中 d 是节点允许的最大子节点个数（阶数）。 在实际应用中，d 值通常远大于 2（例如大于 100）。这保证了即使数据量 M 达到千万级别，B+Tree 的高度依然能维持在 3~4 层左右。这意味着一次数据查询操作通常只需要 3~4 次磁盘 I/O 即可完成。 相比之下，一个存储相同 M 条数据的平衡二叉搜索树，其节点总数也约为 M，搜索复杂度为 O(logM)（以 2 为底）。由于其分支因子固定为 2，树的高度会显著高于 B+Tree，导致检索目标数据需要经历更多的磁盘 I/O 次数。 3, B+Tree vs Hash Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。但也有其局限性： 数据顺序性：哈希表无法提供数据的顺序访问，更适合做等值的查询。很多查询不仅需要找到特定的键值，还需要根据键值排序来返回结果，或者执行范围查询。B+Tree 可以很好地支持，Hash 表则无法做到。 空间效率：可能导致空间利用效率不高，特别是在处理大量数据时。数据量变大时冲突也会增加。 需要重新构建：哈希索引通常只存储在内存中，当数据库重启或发生崩溃时，需要重新构建。 因此，B+Tree 索引要比 Hash 表索引有着更广泛的适用场景。 Full-text 索引 Full Text 索引（全文索引）是 MySQL 中专门用于高效处理大文本字段（如文章、描述等）内容检索的一种索引类型。它主要用于在大量文本数据中进行复杂的关键词搜索，支持模糊匹配、相关性排序等功能，远比传统的 LIKE 语句效率高，尤其适合需要全文检索的场景（如搜索引擎、商品描述搜索等）。 工作原理 Full Text 索引通常基于倒排索引（inverted index）实现。倒排索引会将文本内容分词后，建立"单词 → 文档 ID"的映射关系，从而能快速定位包含某个关键词的所有记录。这种结构极大提升了模糊查询和多关键词检索的效率。 主要特性 适用于 CHAR、VARCHAR、TEXT等文本类型字段 仅支持 InnoDB 和 MyISAM 存储引擎（MySQL 5.6 及以上 InnoDB 支持） 支持三种检索模式：自然语言模式、布尔模式、查询扩展模式 典型用法：MATCH(column) AGAINST('keyword' IN NATURAL LANGUAGE MODE) 示例 创建全文索引： 1CREATE FULLTEXT INDEX idx_content ON articles(content); 使用全文检索： 1SELECT * FROM articles WHERE MATCH(content) AGAINST('数据库 索引'); 参考 MySQL 官方文档：全文索引 CSDN: MySQL 全文索引用途及基本使用方法介绍 简而言之，Full Text 索引让 MySQL 能够像搜索引擎一样高效地在大段文本中查找关键词，是处理复杂文本检索的利器。 按物理存储分类 聚集索引：数据和主键索引存储在一起，一个表只能有一个，通常是主键。聚集索引的叶子节点存储的是数据行。 二级索引：又称非聚集索引，存储索引键和主键值，通过主键再查找数据，可以有多个。非聚集索引的叶子节点存储的是主键值，而不是数据行。 按字段特性分类 主键索引：主键索引是聚集索引（Clustered Index），一个表只能有一个，通常对应主键。其叶子节点直接存储完整的数据行（即数据和索引在一起）。 创建主键索引： 1234CREATE TABLE `table_name` ( ... PRIMARY KEY (`id`) USING BTREE); 唯一索引：唯一索引也是二级索引，要求索引列的值唯一。叶子节点同样存储索引键和主键值，通过主键回表查找数据。 创建唯一索引： 1234CREATE TABLE `table_name` ( ... UNIQUE KEY `idx_name` (`column1`, `column2`)); 或者如果表已经存在，可以通过以下方式创建： 1ALTER TABLE `table_name` ADD UNIQUE KEY `idx_name` (`column1`, `column2`); 普通索引：普通索引属于二级索引（Secondary/Non-Clustered Index），可以有多个。叶子节点存储的是索引键和主键值（InnoDB），通过主键回表查找完整数据。 创建普通索引： 1234CREATE TABLE `table_name` ( ... INDEX `idx_name` (`column1`, `column2`)); 或者如果表已经存在，可以通过以下方式创建： 1ALTER TABLE `table_name` ADD INDEX `idx_name` (`column1`, `column2`); 前缀索引：前缀索引是一种特殊的二级索引，针对字符串类型字段，只索引字段的前 N 个字符。叶子节点存储前缀、主键值，通过主键回表查找数据。 创建前缀索引： 1234CREATE TABLE `ta...

问题描述 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码只接受原链表的头节点 head 作为传入参数。 示例 示例 1: 12输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2: 12输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]] 示例 3: 12输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]] 约束条件 0 <= n <= 1000 -10^4 <= Node.val <= 10^4 Node.random 为 null 或指向链表中的节点。 节点数目不超过 1000 。 解决方案 这个问题可以通过几种不同的方法解决，下面介绍三种主要的解法： 方法一：哈希表映射 + 两次遍历 最直观的方法是使用哈希表建立原节点到新节点的映射关系。 实现步骤： 第一次遍历：创建所有新节点，并建立原节点到新节点的映射 第二次遍历：根据映射关系设置新节点的 next 和 random 指针 12345678910111213141516171819202122232425func copyRandomList(head *Node) *Node { if head == nil { return nil } // 创建原始节点到复制节点的映射 nodeMap := make(map[*Node]*Node) // 第一次遍历：创建所有新节点 cur := head for cur != nil { nodeMap[cur] = &Node{Val: cur.Val} cur = cur.Next } // 第二次遍历：设置新节点的next和random指针 cur = head for cur != nil { nodeMap[cur].Next = nodeMap[cur.Next] nodeMap[cur].Random = nodeMap[cur.Random] cur = cur.Next } return nodeMap[head]} 方法二：原地修改 + 拆分（O(1)空间解法） 这种方法不使用额外的哈希表，而是通过修改原链表结构来实现深拷贝。 实现步骤： 第一步：在每个原节点后插入对应的复制节点，形成 A->A’->B->B’->… 的链表结构 第二步：设置复制节点的 random 指针，利用 cur.Random.Next 来获取对应的复制节点 第三步：将交错的链表拆分成原链表和复制链表 1234567891011121314151617181920212223242526272829303132333435363738394041func copyRandomList(head *Node) *Node { if head == nil { return nil } // 第一步：在每个原节点后创建一个新节点 cur := head for cur != nil { copyNode := &Node{ Val: cur.Val, Next: cur.Next, } cur.Next = copyNode cur = copyNode.Next } // 第二步：设置新节点的random指针 cur = head for cur != nil { if cur.Random != nil { cur.Next.Random = cur.Random.Next } cur = cur.Next.Next } // 第三步：分离原链表和复制链表 cur = head copyHead := head.Next for cur != nil { copyNode := cur.Next cur.Next = copyNode.Next if copyNode.Next != nil { copyNode.Next = copyNode.Next.Next } cur = cur.Next } return copyHead} 方法三：递归 + 哈希表 这种方法使用递归和哈希表结合的方式解决问题。 123456789101112131415161718192021222324252627func copyRandomList(head *Node) *Node { visited := make(map[*Node]*Node) var deepCopy func(node *Node) *Node deepCopy = func(node *Node) *Node { if node == nil { return nil } // 如果已经创建过该节点，直接返回 if copy, ok := visited[node]; ok { return copy } // 创建新节点 copy := &Node{Val: node.Val} visited[node] = copy // 递归设置next和random指针 copy.Next = deepCopy(node.Next) copy.Random = deepCopy(node.Random) return copy } return deepCopy(head)} 错误分析 常见错误点和易错模式 在实现方法二（原地修改 + 拆分）时，有几个容易出错的地方： 错误实现 1234567891011121314151617181920212223242526272829303132func copyRandomList(head *Node) *Node { cur := head // 第一步：创建交错链表 for cur != nil { copyNode := &Node{ Next: cur.Next, Val: cur.Val, } cur.Next = copyNode cur = copyNode.Next } // 第二步：设置random指针 cur = head for cur != nil { cur.Next.Random = cur.Random.Next // 错误：没有检查cur.Random是否为nil cur = cur.Next.Next } // 第三步：拆分链表 cur = head copy1 := cur.Next for cur != nil { tmpNext := cur.Next cur.Next = tmpNext.Next tmpNext.Next = cur.Next.Next // 错误：没有检查cur.Next是否为nil cur = cur.Next } return copy1} 错误分析 上述实现有三个主要问题： 没有处理空链表：当 head == nil 时，应该直接返回 nil 没有处理 Random 指针为空：在设置 cur.Next.Random 时，如果 cur.Random 为 nil，会导致空指针异常 链表拆分处理不当：在拆分链表最后阶段，没有正确处理尾节点的情况，可能导致 nil 指针解引用 修正实现 1234567891011121314151617181920212223242526272829303132333435363738394041func copyRandomList(head *Node) *Node { if head == nil { return nil } // 第一步：创建交错链表 cur := head for cur != nil { copyNode := &Node{ Next: cur.Next, Val: cur.Val, } cur.Next = copyNode cur = copyNode.Next } // 第二步：设置random指针 cur = head for cur != nil { if cur.Random != nil { cur.Next.Random = cur.Random.Next } cur = cur.Next.Next } // 第三步：拆分链表 cur = head copyHead := head.Next for cur != nil { copyNode := cur.Next cur.Next = copyNode.Next if copyNode.Next != nil { copyNode.Next = copyNode.Next.Next } cur = cur.Next } return copyHead} 复杂度分析 方法 时间复杂度 空间复杂度 优点 缺点 推荐度 哈希表映射 O(n) O(n) 实现简单，直观易懂 需要额外空间 ★★★★☆ 原地修改 + 拆分 O(n) O(1) 常数空间复杂度 实现复杂，易出错 ★★★★★ 递归 + 哈希表 O(n) O(n) 代码精简，逻辑清晰 递归栈可能导致栈溢出 ★★★☆☆ 关键学习点 链表操作的边界条件处理：在链表问题中，始终要考虑空链表、单节点链表等边界情况 空指针检查的重要性：对可能为空的指针进行操作前，必须进行非空检查 不使用额外空间的技巧：如何通过修改原数据结构来避免使用额外空间 深拷贝与浅拷贝的区别：深拷贝需要复制所有相关联的对象，而不仅仅是直接引用 这道题是链表操作的经典问题，掌握它对理解更复杂的链表操作有很大帮助。原地修改的方法虽然实现复杂，但通过在原链表上巧妙地构建信息来降低空间复杂度，是一种值得学习的高级技巧。

行溢出 MYSQL 中磁盘和内存交互的基本单位是页，一页的大小为 16KB。 如果一个字段存储的内容超过了 16KB，那么这个字段就会发生行溢出。 比如之前说过 VARCHAR 类型的最大长度是 65532（允许为 NULL），那么 Varchar 的长度明显是会超过一页的大小的，那么就会发生行溢出。 VARCHAR 类型最大取值 行溢出的处理 Compact 行格式 当在使用 Compact 行格式时，如果发生行溢出，MYSQL 会使用溢出页来存储溢出的数据。它会在真实数据处只会存储一部分数据，剩余的数据会存储在溢出页中。然后在真实数据处的最后 20 个字节存储溢出页的地址，从而方便快速定位到溢出页。 Compressed 和 Dynamic 行格式 Compressed 和 Dynamic 行格式与 Compact 行格式类似，但是在溢出的处理上有所不同。它不会在真实数据处存储部分数据，而是完全只存储溢出页的地址。真实数据完全存储在溢出页中。

问题描述 给你一个链表，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1: 12输入: head = [1,2,3,4,5], k = 2输出: [2,1,4,3,5] 示例 2: 12输入: head = [1,2,3,4,5], k = 3输出: [3,2,1,4,5] 约束条件: 链表中节点的数目为 n 1 <= k <= n <= 5000 0 <= Node.val <= 1000 解题思路 本题要求我们以 k 个节点为一组进行翻转，如果最后剩余的节点不足 k 个，则保持原样。这是链表操作中的一个典型问题，主要涉及链表的翻转操作。 解决这个问题的核心思想是： 确定每组 k 个节点的范围 翻转这 k 个节点 将翻转后的组与前后部分连接起来 移动到下一组继续操作 我们使用迭代的方式来解决这个问题，通过一个循环来处理每组 k 个节点。 实现细节 错误版本分析 首先，让我们看看出错的代码版本： 123456789101112131415161718192021222324252627282930313233343536373839404142func reverseKGroup(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil || k == 1 { return head } dummyHead := &ListNode{ Next: head, } first := dummyHead var prev, end *ListNode cur := dummyHead.Next for { end = first for i := 0; i < k; i++ { end = end.Next if end == nil { break } } if end == nil { break } tmp := first.Next cur = tmp.Next prev = tmp for cur != nil && cur != end.Next { tmp2 := cur.Next cur.Next = prev prev = cur cur = tmp2 } first.Next = end tmp.Next = cur first = tmp } return dummyHead.Next} 这个版本的主要问题出现在翻转链表的循环条件中： 123456for cur != nil && cur != end.Next { tmp2 := cur.Next cur.Next = prev prev = cur cur = tmp2} 错误原因: 在翻转链表的过程中，我们修改了节点的 Next 指针。当我们在循环中检查 cur != end.Next 这个条件时，由于 end 是链表中的一个节点，其 Next 指针可能在循环过程中被修改，导致循环终止条件不符合预期。 修复版本 修复后的代码版本： 12345678910111213141516171819202122232425262728293031323334353637383940414243func reverseKGroup(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil || k == 1 { return head } dummyHead := &ListNode{ Next: head, } first := dummyHead var prev, end *ListNode cur := dummyHead.Next for { end = first for i := 0; i < k; i++ { end = end.Next if end == nil { break } } if end == nil { break } tmp := first.Next cur = tmp.Next prev = tmp afterEnd := end.Next for cur != nil && cur != afterEnd { tmp2 := cur.Next cur.Next = prev prev = cur cur = tmp2 } first.Next = end tmp.Next = cur first = tmp } return dummyHead.Next} 修复点: 通过在开始翻转前保存 end.Next 到 afterEnd 变量，我们确保了循环的终止条件不会受到链表结构变化的影响。这样，即使在翻转过程中修改了节点间的连接关系，我们仍然能正确地确定何时停止翻转当前组的节点。 优化版本 虽然修复后的代码能够正确工作，但我们可以进一步优化代码，使其逻辑更清晰： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748func reverseKGroup(head *ListNode, k int) *ListNode { // 处理特殊情况 if head == nil || head.Next == nil || k == 1 { return head } // 创建虚拟头节点简化边界处理 dummy := &ListNode{Next: head} // groupPrev 指向当前待翻转组的前一个节点 groupPrev := dummy // 持续处理每组 k 个节点 for { // 1. 检查剩余节点是否有 k 个 groupEnd := groupPrev for i := 0; i < k; i++ { groupEnd = groupEnd.Next if groupEnd == nil { // 剩余节点不足 k 个，不再翻转 return dummy.Next } } // 2. 获取分组的起始和结束位置 groupStart := groupPrev.Next groupNext := groupEnd.Next // 3. 翻转 k 个节点 prev := groupNext // 翻转后尾节点指向的位置 curr := groupStart // 经典链表翻转算法 for curr != groupNext { next := curr.Next curr.Next = prev prev = curr curr = next } // 4. 连接翻转后的组与之前的链表 groupPrev.Next = groupEnd // 前一个节点连接到翻转后的头 groupStart.Next = groupNext // 翻转后的尾连接到下一组的开始 // 5. 更新 groupPrev 为下一组的前节点 groupPrev = groupStart }} 在这个优化版本中： 使用了更有描述性的变量名（如 groupStart, groupEnd, groupNext, groupPrev） 添加了清晰的注释，解释每个步骤的目的 简化了链表翻转的实现，使用标准的三指针翻转方法 分离了不同的逻辑部分，使代码更易理解 直接返回 dummy.Next 而不是使用 break 和额外的控制变量 复杂度分析 时间复杂度: O(n)，其中 n 是链表的长度。虽然有嵌套循环，但每个节点最多被访问两次。 空间复杂度: O(1)，只使用了常数个额外变量，没有使用额外的数据结构。 关键要点 链表修改的注意点: 在修改链表结构时，需要特别注意那些依赖于链表当前结构的条件判断。在本例中，我们学到了在开始修改前保存关键节点引用的重要性。 变量命名的重要性: 优化版代码通过使用更有描述性的变量名，极大地提高了代码的可读性，使人更容易理解算法的逻辑。 分组处理的思想: 这种按组处理的思想在很多链表和数组问题中都很有用，可以将一个复杂问题分解为处理单个组和组之间连接的子问题。 这个问题是链表操作的典型例子，掌握了这里的翻转技巧，可以应用到很多其他的链表问题中，如链表的部分翻转、两两交换节点等。

Problem Description 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例 示例 1: 12输入：head = [1,2,3,4]输出：[2,1,4,3] 示例 2: 12输入：head = []输出：[] 示例 3: 12输入：head = [1]输出：[1] 约束条件 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100 Solution Approach 这是一个典型的链表操作问题，我们需要两两交换相邻节点。有两种常见的解决方法：迭代法和递归法。 迭代法 迭代法的核心思想是使用三个指针来完成相邻节点的交换。我们需要： 一个哑节点（dummy node）作为新链表的起点 一个前置指针（prev）指向已处理部分的最后一个节点 一个当前指针（curr）指向待处理的第一个节点 关键步骤: 创建一个哑节点指向原链表头 初始化 prev 为哑节点，curr 为链表头 当 curr 和 curr.next 都非空时进行交换： 临时保存 curr.next.next 调整指针完成交换 移动 prev 和 curr 指针继续处理下一对节点 返回哑节点的下一个节点作为新链表的头节点 以示例 1 为例，交换过程可视化： 1234567891011121314dummy -> 1 -> 2 -> 3 -> 4prev curr交换后dummy -> 2 -> 1 -> 3 -> 4 | | | curr (新的 curr) | prev (新的 prev)继续交换dummy -> 2 -> 1 -> 4 -> 3 | curr=nil (结束) Code Implementation 1. 迭代解法 12345678910111213141516171819202122232425262728293031323334353637383940/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func swapPairs(head *ListNode) *ListNode { // 处理边界情况：空链表或只有一个节点 if head == nil || head.Next == nil { return head } // 创建哑节点指向链表头 dummyHead := &ListNode{ Next: head, } // 初始化指针 prev, curr := dummyHead, head // 当有一对节点可交换时进行交换 for curr != nil && curr.Next != nil { // 保存下一对节点的起始位置 nextPair := curr.Next.Next // 交换当前一对节点 // 1->2->3->4 变为 2->1->3->4 second := curr.Next // second = 2 second.Next = curr // 2->1 curr.Next = nextPair // 1->3 prev.Next = second // dummy->2 // 移动指针，准备处理下一对节点 prev = curr // prev = 1 curr = nextPair // curr = 3 } return dummyHead.Next} 2. 递归解法 递归法更简洁，但需要理解递归思想： 123456789101112131415161718func swapPairs(head *ListNode) *ListNode { // 基本情况：空链表或只有一个节点 if head == nil || head.Next == nil { return head } // 保存第二个节点 second := head.Next // 递归处理剩余部分，从第三个节点开始 head.Next = swapPairs(second.Next) // 交换前两个节点 second.Next = head // 返回新的头节点（原来的第二个节点） return second} Complexity Analysis 迭代法 时间复杂度: O(n)，其中 n 是链表的长度。我们需要遍历一次链表，每次处理两个节点。 空间复杂度: O(1)，只使用了常数个额外变量。 递归法 时间复杂度: O(n)，同样需要处理每个节点一次。 空间复杂度: O(n/2) ≈ O(n)，递归栈的深度为链表长度的一半（每次递归处理两个节点）。 方法比较 方面 迭代法 递归法 时间复杂度 O(n) O(n) 空间复杂度 O(1) O(n) 代码复杂度 中等 简洁 优点 节省空间 代码简洁易懂 缺点 需要处理多个指针 大链表可能导致栈溢出 推荐度 ★★★★☆ ★★★★★ Key Learnings 链表操作的关键在于指针管理：在处理链表时，合理使用指针变量可以极大简化操作。 哑节点（Dummy Node）的使用：在许多链表问题中，使用哑节点可以统一操作，避免处理头节点的特殊情况。 迭代vs递归：链表问题通常可以用这两种方法解决。递归往往代码更简洁，但空间复杂度更高。 画图辅助理解：对于复杂的链表操作，画出节点和指针的变化过程有助于理解和调试。 这个问题是链表操作的基础练习，掌握它对理解更复杂的链表问题很有帮助。

在看这篇文章之前，需要先了解 Mysql 的记录存储方式，可以看这篇文章：Mysql 记录存储方式 然后，我们需要先知道一个知识点:MYSQL 中规定，除了 Text、Blob类型，其他类型其他所有的列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过 65535 个字节，这里注意一下，65535 是一行的最大字节数，而不是一个列的最大字节数。 需要说明的是，varchar 最大的长度其实是达不到 65535的，因为这一行中除了 varchar的真实数据，还包含了变长字段长度列表、NULL 值列表所占用的字节数 在我们创建一个 varchar类型的时候,实际上创建了三个部分: 真实数据 真实数据占用的字节数 NULL 标识(如果不允许为 NULL，则不需要) 比如我们在创建下面的表的时候: 123CREATE TABLE test( name VARCHAR(65532) NULL)ENGINE=InnoDB DEFAULT CHARACTER SET = ascii ROW_FORMAT = Compact; 就比如我们创建上面这个表的时候，由于允许为 NULL，所以需要（因为不满 8 位，所以需要一个字节来标识）一个字节来标识 紧接着，变长字段长度列表，需要占用 2 个字节来标识，因为它的规则是： 1.如果变长字段允许存储的最大字节数小于等于 255 字节，就会用 1 字节表示「变长字段长度」； 2.如果变长字段允许存储的最大字节数大于 255 字节，就会用 2 字节表示「变长字段长度」； 我们这个例子里面的 varchar(65532)，所以需要用 2 个字节来标识，所以这一行总共占用的字节数为：1+2+65532=65535，正好达到 65535 的限制。 因此我们可以得知，varchar 在可以为 NULL 的情况下，最大长度为 65532。 在不允许为 NULL 的情况下，由于不需要 NULL 标识字节，所以只需要 2 个字节来表示变长字段长度列表。因此实际可存储的最大数据字节数为 65535 - 2 = 65533 字节，即 VARCHAR(65533) 达到上限。 如果有多个字段的话，要保证所有字段的长度 + 变长字段字节数列表所占用的字节数 + NULL 值列表所占用的字节数 <= 65535。

问题描述 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 123输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807. 示例 2： 12输入：l1 = [0], l2 = [0]输出：[0] 示例 3： 12输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1] 提示： 每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零 解题思路 这道题考察的是链表操作和数字加法。由于两个链表已经是逆序存储，与我们正常从低位到高位进行加法计算的顺序相同，所以可以直接对两个链表进行遍历并相加。主要需要处理的点是： 两个数字相加可能产生进位 两个链表可能长度不同 最高位相加后可能还有进位，需要额外增加一个节点 解题的核心思想是模拟加法运算的过程，按位相加并处理进位。 初始实现分析（有待优化的代码） 下面是一个可以通过但有待优化的实现： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { oneFlag := false res := &ListNode{} var prev *ListNode cur := res for l1 != nil && l2 != nil { tmp := l1.Val + l2.Val if oneFlag { tmp += 1 } cur.Val = tmp % 10 if tmp >= 10 { oneFlag = true } else { oneFlag = false } cur.Next = &ListNode{} prev = cur cur = cur.Next l1 = l1.Next l2 = l2.Next } for l1 != nil { tmp := l1.Val if oneFlag { tmp += 1 } cur.Val = tmp % 10 if tmp >= 10 { oneFlag = true } else { oneFlag = false } cur.Next = &ListNode{} prev = cur cur = cur.Next l1 = l1.Next } for l2 != nil { tmp := l2.Val if oneFlag { tmp += 1 } cur.Val = tmp % 10 if tmp >= 10 { oneFlag = true } else { oneFlag = false } cur.Next = &ListNode{} prev = cur cur = cur.Next l2 = l2.Next } if oneFlag { cur.Val = 1 prev = cur } prev.Next = nil return res} 存在的问题 这段代码虽然可以解决问题，但存在以下几个问题： 代码冗余：有三个几乎相同的循环，处理逻辑重复 效率不高：每次循环都创建了新节点，包括可能无用的节点 可读性差：变量名不够直观（如 oneFlag 表示进位） 代码结构：循环后的收尾处理逻辑不够清晰 优化实现 我们可以通过以下几点优化代码： 合并重复的三个循环，使用一个循环处理所有情况 使用更清晰的变量名（如 carry 代替 oneFlag） 只在确实需要新节点时才创建 简化进位的处理逻辑 优化后的代码 12345678910111213141516171819202122232425262728func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { // 创建虚拟头节点，简化操作 dummy := &ListNode{} current := dummy carry := 0 // 只要有一个链表还有节点或者有进位，就继续循环 for l1 != nil || l2 != nil || carry > 0 { sum := carry // 添加当前节点的值（如果存在） if l1 != nil { sum += l1.Val l1 = l1.Next } if l2 != nil { sum += l2.Val l2 = l2.Next } // 计算进位和当前位的值 carry = sum / 10 current.Next = &ListNode{Val: sum % 10} current = current.Next } return dummy.Next} 优化说明 使用虚拟头节点（dummy head）：通过创建一个虚拟头节点，我们可以简化链表操作，避免处理头节点为空的特殊情况。 合并循环：将三个循环合并为一个循环，只要有一个链表还有节点或者有进位，就继续循环。 改进变量命名：使用 carry 代替 oneFlag，使代码更易理解。 按需创建节点：只在确实需要添加新节点时才创建，而不是提前创建可能无用的节点。 简化进位计算：使用 sum / 10 计算进位，sum % 10 计算当前位的值，代码更简洁清晰。 复杂度分析 时间复杂度：O(max(n, m))，其中 n 和 m 分别是两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。 空间复杂度：O(max(n, m))，新链表的长度最多为 max(n, m) + 1（当有进位时）。不考虑返回值所占用的空间，空间复杂度为 O(1)。 优化前后对比 方面 优化前 优化后 代码行数 ~50 行 ~20 行 循环次数 3个循环 1个循环 可读性 较差 良好 变量命名 不直观 清晰明了 节点创建 可能创建无用节点 按需创建 时间复杂度 O(max(n, m)) O(max(n, m)) 空间复杂度 O(max(n, m)) O(max(n, m)) 学习要点 代码简化：通过合并相似的逻辑，可以大幅减少代码量，提高可读性。 虚拟头节点技巧：在处理链表问题时，使用虚拟头节点可以简化边界情况的处理。 条件合并：将多个条件合并到一个循环中，使代码更加简洁。 变量命名：使用清晰的变量名可以提高代码可读性，如使用 carry 表示进位。 按需分配内存：只在必要时创建新的节点，避免无用的内存分配和释放。 这种链表加法的模式在处理大数加法等问题时也很常见，掌握这种模式对解决类似问题很有帮助。

Model Context Protocol (MCP) 介绍 为什么我们需要MCP 当今的大型语言模型(LLM)虽然功能强大，但在与外部世界交互时仍面临诸多挑战： 上下文窗口限制：模型能接收的信息量有限，导致处理大型代码库或数据集困难 数据隐私问题：敏感数据需要发送到云端处理，增加了隐私和安全风险 工具集成碎片化：每个LLM提供商有不同的工具集成方式，导致开发者需维护多套代码 本地资源访问受限：很难让LLM安全地访问本地文件系统、数据库或应用程序 多系统协作困难：让LLM与多个不同服务协同工作缺乏统一标准 Model Context Protocol (MCP)正是为解决这些问题而诞生的技术标准，它提供了一种统一、安全、灵活的方式，让语言模型能够与各种外部系统和资源进行交互。 MCP是什么 Model Context Protocol (MCP) 是一种用于构建LLM（大型语言模型）应用程序的客户端-服务器架构协议，它允许AI模型与外部数据源和工具进行交互。 名词解释： 客户端-服务器架构：一种计算模型，其中一个程序(客户端)请求服务，另一个程序(服务器)提供服务。就像餐厅中顾客(客户端)点餐，厨房(服务器)准备食物。 协议：一套规则，定义了系统间如何交换信息。类似于人们交流的语言和礼仪规范。 API(应用程序接口)：软件组件之间的连接点，允许不同程序相互通信。就像电源插座是电器与电网的接口。 MCP的核心思想是通过标准化的协议，让语言模型能够安全、灵活地访问各种本地和远程资源。这不仅仅是一个简单的API或函数调用系统，而是一个完整的架构模式，具有以下核心特征： 协议驱动: MCP 定义了客户端和服务器之间通信的标准协议，使不同组件能够无缝协作 资源抽象: 将各种数据源、工具和服务抽象为统一的资源接口 分布式设计: 支持多个服务器并行提供不同功能，实现功能解耦 安全隔离: 明确的安全边界，数据保持在服务器端，只有结果返回给客户端 可组合性: 不同MCP服务器可以组合使用，形成复杂的工作流 日常使用场景：MCP如何改变我们使用AI的方式 场景一：本地文档助手 问题：王先生有大量存储在本地电脑上的工作文档，他想让AI助手帮忙整理和总结，但又担心文档内容上传到云端会有安全风险。 MCP解决方案： 王先生在电脑上安装了支持MCP的Claude Desktop应用和文件系统MCP服务器 当他询问"帮我总结所有2025年第一季度的会议记录"时 Claude会通过MCP服务器安全地搜索本地文件系统 文档内容不会离开王先生的电脑，只有搜索结果返回给Claude Claude根据获取的会议内容生成总结报告 这一过程对王先生来说完全透明，他只需正常与AI交谈，但所有数据处理都在本地完成，保证了信息安全。 场景二：代码开发助手 问题：张女士是一名软件开发人员，使用AI助手编写代码，但发现AI无法访问她的本地代码库、运行测试或执行Git操作。 MCP解决方案： 张女士在IDE中使用支持MCP的AI编码助手 IDE运行多个MCP服务器，分别处理代码访问、测试运行和版本控制 当张女士要求"根据单元测试结果修复这个bug"时 AI通过代码访问MCP服务器读取相关文件 通过测试MCP服务器运行测试并获取结果 分析问题并生成修复方案 通过Git MCP服务器创建修复分支和提交更改 整个过程在张女士的本地环境完成，无需将完整代码库上传到云端，同时AI助手能够与她的开发工具流完美集成。 详细协议结构 MCP协议主要包含以下关键组件： 连接管理: 建立和维护客户端与服务器之间的连接 资源发现: 允许客户端发现服务器提供的资源和功能 资源请求: 客户端向服务器请求特定资源 资源响应: 服务器处理请求并返回结果 元数据交换: 交换有关资源和功能的元数据 安全机制: 保护传输中的数据并验证请求的合法性 基本原理与架构 MCP采用客户端-服务器架构，其中： MCP主机（Hosts）：如Claude Desktop、IDE或AI工具，希望通过MCP访问数据的程序 MCP客户端（Clients）：维护与服务器1:1连接的协议客户端，负责发送请求和接收响应 MCP服务器（Servers）：通过标准化的Model Context Protocol公开特定功能的轻量级程序，负责处理请求并返回结果 本地数据源：MCP服务器可以安全访问的计算机文件、数据库和服务 远程服务：MCP服务器可以连接的外部系统（如通过API） 这种架构可以通过以下Mermaid图表表示： MCP通信流程 MCP通信过程是如何实现LLM与各种资源交互的关键。以下是一个典型的MCP通信流程： sequenceDiagram participant User as 用户 participant LLM as 语言模型 participant Host as 主机应用 participant Client as MCP客户端 participant Server as MCP服务器 participant DataSource as 数据源 User->>Host: 提出请求 Host->>LLM: 转发用户请求 LLM-->>Host: 需要访问外部资源 Host->>Client: 资源请求 Client->>Server: 发送MCP请求 Server->>DataSource: 数据访问 DataSource-->>Server: 返回数据 Server-->>Client: MCP响应 Client-->>Host: 返回资源 Host->>LLM: 提供资源 LLM-->>Host: 基于资源的响应 Host->>User: 显示结果 资源接口设计 MCP定义了一套资源接口，使客户端能够统一访问各种不同类型的资源： classDiagram class Resource { +String resourceId +String resourceType +Metadata metadata +request(parameters) } class FileResource { +String path +readContent() +writeContent(data) } class DatabaseResource { +String connectionString +query(sql) +update(sql) } class APIResource { +String endpoint +call(parameters) } Resource <|-- FileResource Resource <|-- DatabaseResource Resource <|-- APIResource MCP与Function Call的区别 MCP和Function Call都是扩展LLM能力的技术，但它们在设计和实现上存在显著差异： Function Call Function Call（函数调用）是一种让LLM能够调用预定义函数的能力，主要特点： 通常在单一环境中运行 函数定义必须嵌入到模型的上下文中，占用token空间 典型的实现是在LLM生成函数调用JSON后，由应用程序执行相应函数 安全边界通常由应用程序自身定义 通常需要为每个LLM提供商实现不同的集成方式 sequenceDiagram participant User as 用户 participant App as 应用程序 participant LLM as 语言模型 participant Functions as 函数库 User->>App: 提出请求 App->>LLM: 请求(包含函数定义) Note over App,LLM: 函数定义占用上下文空间 LLM->>App: 函数调用JSON App->>Functions: 执行函数 Functions->>App: 返回结果 App->>LLM: 结果作为新上下文 LLM->>App: 生成最终响应 App->>User: 显示结果 MCP MCP则提供了一个更加分布式、标准化的架构： 采用客户端-服务器架构，明确分离责任 多个专用服务器可以并行提供不同功能，支持横向扩展 通过标准协议实现互操作性，与LLM提供商无关 明确的安全边界，数据保持在服务器端 可以跨应用程序和环境重用，提高代码复用性 资源动态发现，无需预先定义所有功能 sequenceDiagram participant User as 用户 participant Host as 主机应用 participant LLM as 语言模型 participant Client as MCP客户端 participant ServerA as MCP服务器A participant ServerB as MCP服务器B participant DataA as 数据源A participant DataB as 数据源B User->>Host: 提出请求 Host->>LLM: 转发请求 LLM->>Host: 需要资源A Host->>Client: 请求资源A Client->>ServerA: MCP请求 ServerA->>DataA: 访问数据 DataA-->>ServerA: 返回数据 ServerA-->>Client: MCP响应 Client-->>Host: 返回资源A Host->>LLM: 提供资源A LLM->>Host: 需要资源B Host->>Client: 请求资源B Client->>ServerB: MCP请求 ServerB->>DataB: 访问数据 DataB-->>ServerB: 返回数据 ServerB-->>Client: MCP响应 Client-->>Host: 返回资源B Host->>LLM: 提供资源B LLM->>Host: 生成最终响应 Host->>User: 显示结果 MCP的优势 MCP相比传统Function Call和其他工具集成方法有以下优势： 灵活性：可以轻松切换LLM提供商和供应商，无需重写集成 安全性：数据保持在您的基础设施内，明确的安全边界 可扩展性：可以根据需要连接多个专用服务器，支持复杂功能 互操作性：标准化协议确保不同系统间的兼容，避免供应商锁定 本地计算：可以在本地环境中执行计算，无需将敏感数据发送到云端 分布式架构：不同服务可以在不同位置运行，提高系统弹性和可用性 动态发现：客户端可以动态发现服务器提供的资源，无需硬编码 隔离性：不同服务器之间相互隔离，一个服务器的问题不会影响其他服务器 实际应用场景 MCP可以应用于多种场景： 开发环境集成：在IDE中通过MCP访问本地代码库、运行测试、执行版本控制操作 数据分析：安全访问和处理本地数据库或文件系统中的数据，执行复杂分析 企业应用：与内部系统安全集成，访问企业知识库、CRM系统、ERP系统等 个人助手：访问个人文件和应用程序，同时保持数据隐私，如日历、邮件、笔记 混合云部署：在本地和云端之间无缝集成资源，实现数据和功能的最佳分配 多模型协作：允许多个不同的LLM通过相同的接口访问相同的资源，实现模型协作 MCP实现示例 以下是一个简化的MCP服务器实现示例，展示了如何创建一个提供文件系统访问的MCP服务器： flo...