问题描述 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改链表。 示例 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 链表可视化： 1233 → 2 → 0 → -4 ↑ ↓ ← ← ← ← 示例 2： 123输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。 链表可视化： 1231 → 2↑ ↓← ← ← 示例 3： 123输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。 链表可视化： 11 → null 约束条件 链表中节点的数目范围在范围 [0, 10^4] 内 -10^5 <= Node.val <= 10^5 pos 的值为 -1 或者链表中的一个有效索引 进阶 你是否可以使用 O(1) 空间解决此题？ 解题思路 方法一：快慢指针（Floyd 判圈算法） 本题的核心思路是使用快慢指针（也称为 Floyd 判圈算法或龟兔赛跑算法）来解决。这是一种检测链表中是否存在环并找到环入口点的经典算法。 算法分析和数学证明 这个算法分为两个阶段： 检测环的存在：使用快慢指针，如果它们相遇，则存在环 寻找环的入口：通过数学关系确定环的入口点 让我们详细解析这个过程，并进行数学推导： 第一阶段：检测环的存在 设置两个指针 slow 和 fast，初始时都指向链表头节点 head slow 指针每次移动 1 步，fast 指针每次移动 2 步 如果链表中存在环，这两个指针最终会在环中某个节点相遇 如果 fast 指针到达了链表末尾（即 fast 或 fast.next 为 null），则链表不存在环 第二阶段：寻找环的入口 数学推导是这个算法的关键。假设： 链表头到环入口点的距离为 a 步 环入口点到相遇点的距离为 b 步 相遇点回到环入口点的距离为 c 步 那么环的总长度为 b + c 步。 环形链表示意图 Mermaid 图示 graph LR Head((Head)) --> A((A)) A --> B((B)) B --> C((C)) C --> D((D)) D --> E((E)) E --> F((F)) F --> C style C fill:#f96,stroke:#333 style F fill:#69f,stroke:#333 Head -.-> |"链表头"|A C -.-> |"环入口点"|C F -.-> |"相遇点"|F A -.-> |"距离 a"|C C -.-> |"距离 b"|F F -.-> |"距离 c"|C 纯文本图示 123456789101112 环入口 ↓head → A → B → C → D → E ↑ ↓ ↑ ↓ ↑ ↓ G ← F ← F ← 相遇点 距离标记:head到环入口C的距离: a环入口C到相遇点F的距离: b相遇点F返回环入口C的距离: c 另一种表示方式: 1234567891011 a b +---+ +---+ ↓ ↓ ↓ ↓head → → → → → → → + ↑ ↓ ↑ ↓ ↑ ↓ + ← ← + ↑ + c 当 slow 和 fast 指针相遇时： slow 走了 a + b 步 fast 走了 a + b + n(b + c) 步，其中 n 是 fast 指针在环中绕的圈数 由于 fast 指针走的步数是 slow 指针的 2 倍，所以有： 1a + b + n(b + c) = 2(a + b) 化简： 123a + b + n(b + c) = 2a + 2bn(b + c) = a + ba = n(b + c) - b = (n-1)(b + c) + c 对于 n=1 的情况（即 fast 指针绕环一圈就与 slow 相遇），我们有： 1a = c 这个结论非常重要：从链表头到环入口的距离，等于从相遇点继续前进到环入口的距离。 基于这个发现，我们的算法第二阶段为： 将 fast 指针重新指向链表头节点 保持 slow 指针在相遇点 让两个指针每次都移动 1 步 它们最终会在环的入口点相遇 这种方法的巧妙之处在于我们不需要知道环的长度或链表的长度，也不需要额外的空间来记录已访问过的节点。 代码实现 123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func detectCycle(head *ListNode) *ListNode { // 处理边界情况 if head == nil || head.Next == nil { return nil } // 阶段一：检测环的存在 slow, fast := head, head for { // 如果到达链表末尾，则无环 if fast == nil || fast.Next == nil { return nil } // 快指针移动两步，慢指针移动一步 fast = fast.Next.Next slow = slow.Next // 如果两指针相遇，则存在环 if slow == fast { break } } // 阶段二：寻找环的入口 // 重置快指针到链表头，慢指针保持在相遇点 fast = head // 两个指针每次都移动一步 for slow != fast { slow = slow.Next fast = fast.Next } // 当两指针再次相遇时，就是环的入口点 return fast} 复杂度分析 时间复杂度：O(n)，其中 n 是链表中节点的数量。在最坏情况下，需要遍历整个链表一次才能确定是否有环，然后再遍历部分链表找到环的入口。 空间复杂度：O(1)，只使用了两个指针，不需要额外的空间。 不同方法比较 方面 快慢指针法 哈希表法 时间复杂度 O(n) O(n) 空间复杂度 O(1) O(n) 优点 空间效率高 实现简单直观 缺点 数学分析较复杂 需要额外空间 推荐度 ★★★★★ ★★★☆☆ 关键收获 Floyd 判圈算法是解决链表环检测问题的经典算法，它不仅可以检测环的存在，还能找到环的入口点。 该算法的数学推导很巧妙：从链表头到环入口的距离等于从相遇点继续前进到环入口的距离。 我们可以用 O(1) 的空间复杂度解决此问题，这比使用哈希表需要 O(n) 空间的方法更加高效。 这种双指针的技巧在链表问题中非常常见，掌握这种思想可以帮助解决许多类似问题，如寻找链表中点、检测环、寻找倒数第 k 个节点等。
LeetCode 234 - 回文链表（Palindrome Linked List）
Problem Description 给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。 回文链表指的是从前往后读和从后往前读是一样的链表。例如，1->2->2->1 是回文链表，而 1->2 不是回文链表。 Examples 示例 1： 12输入：head = [1,2,2,1]输出：true 可视化表示: 11 -> 2 -> 2 -> 1 示例 2： 12输入：head = [1,2]输出：false 可视化表示: 11 -> 2 Constraints 链表中节点数目在范围 [1, 10^5] 内 0 <= Node.val <= 9 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ Solution Approach 对于回文链表的判断，我们需要考虑几个关键点： 链表不能像数组那样随机访问，无法直接从两端同时向中间比较 直观思路是将链表转为数组，但这需要 O(n) 额外空间 最优解法需要找到链表中点，反转后半部分，然后比较两半部分 以下我会介绍多种解决此问题的方法，从简单到优化逐步讲解。 方法一：转换为数组 最直观的方法是将链表节点值复制到数组中，然后使用双指针判断数组是否回文。 实现细节 遍历链表，将所有节点值存入数组 使用双指针从数组两端向中间移动并比较 代码实现 123456789101112131415func isPalindrome(head *ListNode) bool { // 将链表值复制到数组 vals := []int{} for node := head; node != nil; node = node.Next { vals = append(vals, node.Val) } // 使用双指针判断数组是否回文 for i, j := 0, len(vals)-1; i < j; i, j = i+1, j-1 { if vals[i] != vals[j] { return false } } return true} 方法二：使用栈 利用栈的特性，我们可以先将前半部分节点值入栈，然后与后半部分比较。 实现细节 使用快慢指针找到链表中点 将前半部分节点值入栈 比较栈中元素与后半部分节点值 代码实现 1234567891011121314151617181920212223242526272829303132func isPalindrome(head *ListNode) bool { if head == nil || head.Next == nil { return true } // 快慢指针找中点 slow, fast := head, head stack := []int{} // 将前半部分入栈 for fast != nil && fast.Next != nil { stack = append(stack, slow.Val) slow = slow.Next fast = fast.Next.Next } // 如果链表长度为奇数，跳过中间节点 if fast != nil { slow = slow.Next } // 比较栈顶元素与后半部分 for slow != nil { if len(stack) == 0 || stack[len(stack)-1] != slow.Val { return false } stack = stack[:len(stack)-1] slow = slow.Next } return true} 方法三：原地反转（原始实现） 这是用户提供的原始解法，使用 O(n) 时间和 O(1) 空间。 实现细节 使用快慢指针找到链表中点 反转后半部分链表 比较前半部分和反转后的后半部分 代码实现（原始版本） 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647func isPalindrome(head *ListNode) bool { if head == nil { return true } fast, slow := head, head for fast.Next != nil { fast = fast.Next if fast.Next == nil { break } slow = slow.Next fast = fast.Next } head2 := slow.Next slow.Next = nil head2 = reverseListTmp(head2) cur1, cur2 := head, head2 for cur2 != nil { if cur1.Val != cur2.Val { return false } cur1 = cur1.Next cur2 = cur2.Next } return true}func reverseListTmp(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } var cur, prev *ListNode cur = head for cur != nil { tmp := cur.Next cur.Next = prev prev = cur cur = tmp } return prev} 方法四：优化的原地反转（最优解） 在原始实现的基础上，我们可以进行一些优化，使代码更加健壮和易读。 实现细节 更清晰地处理边界情况 简化找中点的逻辑 明确区分奇偶长度链表的处理 模块化功能，提高代码可读性 提供可选的链表恢复功能 代码实现（优化版本） 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586type ListNode struct { Val int Next *ListNode}func isPalindrome(head *ListNode) bool { // 处理边界情况 if head == nil || head.Next == nil { return true } // 查找链表中点 fast, slow := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } // 处理奇数长度链表的情况 var secondHalf *ListNode if fast == nil { // 偶数长度 secondHalf = slow } else { // 奇数长度，中间节点不参与比较 secondHalf = slow.Next } // 断开链表 firstHalfEnd := slow if fast == nil { firstHalfEnd = findPredecessor(head, slow) } firstHalfEnd.Next = nil // 反转后半部分 secondHalf = reverseList(secondHalf) // 比较两半部分 result := compareHalves(head, secondHalf) // 可选：恢复链表结构 // firstHalfEnd.Next = reverseList(secondHalf) return result}// 找到前驱节点func findPredecessor(head, target *ListNode) *ListNode { if head == target { return nil } curr := head for curr != nil && curr.Next != target { curr = curr.Next } return curr}// 比较两个链表func compareHalves(first, second *ListNode) bool { for first != nil && second != nil { if first.Val != second.Val { return false } first = first.Next second = second.Next } return true}// 反转链表func reverseList(head *ListNode) *ListNode { var prev *ListNode curr := head for curr != nil { next := curr.Next curr.Next = prev prev = curr curr = next } return prev} 方法五：递归解法 递归方法也可以用来解决此问题，但需要 O(n) 的栈空间。 实现细节 使用递归遍历到链表末尾 回溯时，与前面的节点比较 代码实现 12345678910111213141516171819func isPalindrome(head *ListNode) bool { frontPointer := head var recursiveCheck func(*ListNode) bool recursiveCheck = func(currentNode *ListNode) bool { if currentNode != nil { if !recursiveCheck(currentNode.Next) { return false } if frontPointer.Val != currentNode.Val { return false } frontPointer = frontPointer.Next } return true } return recursiveCheck(head)} Comparison of Approaches 方面 方法一：数组 方法二：栈 方法三：原始反转 方法四：优化反转 方法五：递归 时间复杂度 O(n) O(n) O(n) O(n) O(n) 空间复杂度 O(n) O(n) O(1) O(1) O(n) 优点 实现简单 直观易懂 空间效率高 代码健壮，易于理解 简洁优雅 缺点 空间开销大 空间开销大 代码结构不够清晰 略微复杂 使用了隐式栈空间...
LeetCode 206 - 反转链表（Reverse Linked List）
问题描述 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 示例 1： 12输入：head = [1,2,3,4,5]输出：[5,4,3,2,1] 示例 2： 12输入：head = [1,2]输出：[2,1] 示例 3： 12输入：head = []输出：[] 约束条件： 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ 解题思路 反转链表是一个经典问题，有两种主要的解法：迭代法和递归法。 方法一：迭代法 迭代法的核心思想是：遍历链表，将当前节点的 next 指针改为指向前一个节点。由于单链表只能从前往后遍历，我们需要使用额外的指针来记录当前节点的前一个节点和后一个节点。 基本步骤： 初始化三个指针：prev（前一个节点）初始为 nil，curr（当前节点）初始为 head，next（下一个节点）在循环中赋值。 在遍历过程中，我们首先保存当前节点的下一个节点，防止链表断开后无法继续遍历。 将当前节点的 next 指针指向 prev。 将 prev 和 curr 指针向前移动一步。 重复步骤 2-4，直到 curr 指向 nil，表示已经遍历完整个链表。 方法二：递归法 递归法的核心思想是：假设链表后面的部分已经反转完成，我们只需要处理当前节点和子问题的关系。 基本思路： 终止条件：当链表为空或只有一个节点时，反转后的结果就是它本身，直接返回。 递归调用：对除了头节点以外的其他节点进行反转，并得到新的头节点（反转后链表的头）。 处理当前节点：将当前节点的下一个节点的 next 指向当前节点，并将当前节点的 next 设为 nil。 返回新的头节点。 实现细节 递归实现 在递归方法中，关键在于理解子问题的边界和如何处理当前节点与子问题的关系。 当我们递归地反转 head.Next 及其后面的节点时，我们得到了一个新的头节点 newHead，它是原链表的最后一个节点。此时，除了 head 节点外，其他所有节点都已反转完成。我们只需要将 head.Next.Next 指向 head（让原来的下一个节点指向自己），然后将 head.Next 设为 nil（断开原来的连接），就完成了整个链表的反转。 迭代实现 在迭代方法中，我们需要小心处理指针的移动，确保不会丢失链表的任何部分。特别是在反转当前节点的 next 指针之前，我们需要先保存下一个节点的引用。 代码实现 递归解法 1234567891011121314/** * 递归 */func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } newHead := reverseList(head.Next) head.Next.Next = head head.Next = nil return newHead} 迭代解法 12345678910111213141516171819202122/** * 迭代 */func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } var cur, prev *ListNode prev = head cur = head.Next prev.Next = nil for cur != nil { tmp := cur.Next cur.Next = prev prev = cur cur = tmp } return prev} 优化建议 对于上述迭代解法，虽然结果是正确的，但有几点可以优化： 初始化指针：标准的做法是将 prev 初始化为 nil，cur 初始化为 head，这样可以更简洁地处理各种情况，包括空链表和只有一个节点的链表。 特殊情况处理：虽然代码中有对 head == nil || head.Next == nil 的特殊情况处理，但使用标准的初始化方式后，这个特殊处理是不必要的，因为迭代过程会自然地处理这些情况。 代码简化：可以将初始化和迭代过程简化，减少不必要的步骤。 优化后的迭代版本如下： 12345678910111213func reverseList(head *ListNode) *ListNode { var prev *ListNode curr := head for curr != nil { next := curr.Next // 临时保存下一个节点 curr.Next = prev // 反转当前节点的指针 prev = curr // 移动 prev 指针 curr = next // 移动 curr 指针 } return prev // prev 现在指向新的头节点} 这个优化版本的特点是： 代码更简洁，逻辑更清晰 不需要特殊处理空链表或单节点链表的情况 变量命名更规范，使用 curr 和 next 更容易理解 复杂度分析 时间复杂度 递归解法：O(n)，其中 n 是链表的长度。我们需要对每个节点调用一次递归函数。 迭代解法：O(n)，其中 n 是链表的长度。我们需要遍历整个链表一次。 空间复杂度 递归解法：O(n)，其中 n 是链表的长度。主要是由于递归调用栈的开销。 迭代解法：O(1)，只需要常数级别的额外空间。 两种方法的比较 方面 递归解法 迭代解法 时间复杂度 O(n) O(n) 空间复杂度 O(n) O(1) 优点 代码简洁，思路清晰 空间效率高 缺点 空间开销大，可能栈溢出 代码稍复杂，需要多个指针 推荐度 ★★★☆☆ ★★★★★ 关键收获 指针操作：链表问题的核心是指针操作，需要小心处理指针的移动和更新，避免链表断裂或形成环。 迭代与递归：链表问题通常可以使用迭代和递归两种方式解决，迭代方法通常更高效，而递归方法则更直观。 技巧： 使用多个指针（如 prev、curr、next）可以有效地处理链表的反转操作 在修改指针前，务必先保存必要的引用，防止链表丢失 对于特殊情况（如空链表、单节点链表），可以单独处理或设计算法使其自然包含在一般情况中 空间效率：在实际应用中，通常优先考虑迭代解法，因为它的空间复杂度更低，特别是对于长链表，可以避免递归造成的栈溢出问题。
LeetCode 160 - 相交链表（Intersection of Two Linked Lists）
Problem Description 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交： 12345A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 题目数据保证整个链式结构中不存在环，函数返回结果后，链表必须保持其原始结构。 示例 1： 12345 4 → 1 ↘ 8 → 4 → 5 ↗ 5 → 6 → 1 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at ‘8’ 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 示例 2： 123451 → 9 → 1 ↘ 2 → 4 ↗ 3 输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at ‘2’ 示例 3： 1232 → 6 → 41 → 5 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：No intersection 约束条件： listA 中节点数目为 m listB 中节点数目为 n 1 <= m, n <= 3 * 10^4 1 <= Node.val <= 10^5 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB] 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？ Solution Approach 这个问题有几种解法，我们将逐一介绍，并分析各自的优缺点。 方法一：哈希表法 核心思想：使用哈希表存储第一个链表的所有节点，然后遍历第二个链表，检查每个节点是否在哈希表中存在。 实现步骤： 创建一个哈希表（Go中可以使用map） 将链表A的所有节点添加到哈希表中 遍历链表B，对于每个节点，检查它是否已经存在于哈希表中 如果找到匹配的节点，则返回该节点作为交点 如果遍历完链表B仍未找到匹配节点，则返回nil 1234567891011121314151617func getIntersectionNode(headA, headB *ListNode) *ListNode { nodeMap := make(map[*ListNode]bool) // 将链表A的所有节点添加到哈希表 for curr := headA; curr != nil; curr = curr.Next { nodeMap[curr] = true } // 遍历链表B，检查节点是否在哈希表中 for curr := headB; curr != nil; curr = curr.Next { if nodeMap[curr] { return curr } } return nil} 方法二：双指针法（最优解） 核心思想：使用两个指针 pA 和 pB 分别遍历链表 A 和链表 B。当一个指针到达链表末尾时，将其重定向到另一个链表的头部。最终，两个指针会在相交点相遇，或者在遍历完两个链表后同时为 nil。 重定向过程的深入解释 为什么需要重定向？ 这个问题的核心挑战在于两个链表可能长度不同。如果不进行重定向，两个指针永远不会在正确的位置相遇。 直观理解： 想象两个人在两条不同的道路上跑步，这两条道路在某一点相交。如果两个人以相同的速度跑步，但起点不同，他们可能永远不会在相交点相遇。重定向就像是让一个人跑完自己的路后，立即从另一个人的起点开始跑，这样他们最终会在相交点相遇。 数学证明： 设链表A的长度为m，链表B的长度为n，从交点到末尾的公共部分长度为k。 链表A中交点到末尾的距离：m-k 链表B中交点到末尾的距离：n-k 重定向后，两个指针走过的总路径： pA: m + (n-k) = m + n - k pB: n + (m-k) = n + m - k 所以两个指针走过的总距离是相等的！这就是为什么它们会在交点相遇。 具体例子演示： 12A: a1 → a2 → c1 → c2 → c3B: b1 → b2 → b3 → c1 → c2 → c3 其中c1是交点。 步骤详解： 初始状态： pA = a1, pB = b1 第一次遍历： pA: a1 → a2 → c1 → c2 → c3 → nil pB: b1 → b2 → b3 → c1 → c2 → c3 → nil 重定向过程： pA到达nil，重定向到b1 pB到达nil，重定向到a1 第二次遍历： pA: b1 → b2 → b3 → c1 pB: a1 → a2 → c1 相遇：两个指针在c1相遇！ 为什么重定向有效？ 长度相同的情况：重定向确保两个指针在相同的相对位置开始比较 长度不同的情况：重定向让较短的链表的指针"等待"较长的链表的指针，直到它们在相同的相对位置 没有交点的情况：重定向确保两个指针都会遍历完两个链表，最终同时变为nil 重定向的巧妙之处： 无需预计算长度：不需要先遍历链表计算长度 空间复杂度O(1)：只需要两个指针 时间复杂度O(m+n)：每个指针最多遍历两个链表各一次 自动处理边界情况：自然地处理了空链表、单节点等特殊情况 实现步骤： 初始化两个指针 pA 和 pB 分别指向链表 A 和链表 B 的头节点 同时移动这两个指针，每次移动一步 当 pA 到达链表 A 的末尾时，将其重定向到链表 B 的头部 当 pB 到达链表 B 的末尾时，将其重定向到链表 A 的头部 如果两个链表相交，pA 和 pB 最终会在相交点相遇 如果两个链表不相交，pA 和 pB 最终都会变为 nil 123456789101112131415161718192021222324func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pA, pB := headA, headB for pA != pB { // 当到达链表末尾时，切换到另一个链表的头部 if pA == nil { pA = headB } else { pA = pA.Next } if pB == nil { pB = headA } else { pB = pB.Next } } return pA // pA 要么是相交点，要么是 nil} 方法三：计算长度差法 核心思想：计算两个链表的长度，然后让较长的链表先移动差值步数，之后两个指针同步前进，最终会在相交点相遇。 实现步骤： 分别计算链表 A 和链表 B 的长度 计算两个链表的长度差 diff 让较长的链表的指针先移动 diff 步 然后两个指针同步前进，每次都移动一步 检查两个指针是否相等，如果相等，则返回该节点 1234567891011121314151617181920212223242526272829303132func getIntersectionNode(headA, headB *ListNode) *ListNode { // 计算链表长度的辅助函数 getLength := func(head *ListNode) int { length := 0 for curr := head; curr != nil; curr = curr.Next { length++ } return length } lenA, lenB := getLength(headA), getLength(headB) pA, pB := headA, headB // 让较长的链表先移动差值步数 if lenA > lenB { for i := 0; i < lenA - lenB; i++ { pA = pA.Next } } else { for i := 0; i < lenB - lenA; i++ { pB = pB.Next } } // 同步前进，寻找相交点 for pA != pB { pA = pA.Next pB = pB.Next } return pA // pA 要么是相交点，要么是 nil} 错误解法分析 我之前的解法存在以下问题： 1234567891011121314151617181920212223242526func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } fast, slow := headA, headB for fast != slow { if fast == nil { fast = headB } else { fast = fast.Next } if fast == nil { fast = headB } else { fast = fast.Next } if slow == nil { slow = headA } else { slow = slow.Next } } return fast} 错误点： 算法思路混淆：这个解法似乎混合了检测环形链表的快慢指针法和检测相交链表的双指针法。在相交链表问题中，不应该使用不同速度的指针。 指针移动逻辑错误：fast 指针尝试每次移动两步，而 slow 指针每次移动一步。这种方式在没有环的情况下可能导致无法正确找到相交点。 重置逻辑问题：代码中 fast 指针可能在同一次循环中被重置两次，这不符合算法的要求。 可能的无限循环：如果两个链表不相交，并且长度不同，这种实现可能导致指针永远不会相等，从而陷入无限循环。 解法比较 方面 哈希表法 双指针法 长度差法 时间复杂度 O(m+n) O(m+n) O(m+n) 空间复杂度 O(m) O(1) O(1) 优点 简单直观，容易实现 空间复杂度最优，代码简洁 思路清晰，易于理解 缺点 需要额外空间 初次理解可能有难度 代码略长，需要计算长度 推荐度 ★★★☆☆ ★★★★★ ★★★★☆ Key Learnings 双指针技巧：此问题展示了双指针在解决链表问题中的强大作用，特别是方法二的解法巧妙且优雅。 空间时间权衡：哈希表法虽然直观，但需要额外空间；而双指针法和长度差法只需O...
LeetCode 240 - 搜索二维矩阵 II（Search a 2D Matrix II）
问题描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1： 输入：matrix = 1234567[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]] target = 5 输出：true 示例 2： 输入：matrix = 1234567[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]] target = 20 输出：false 提示： m == matrix.length n == matrix[i].length 1 <= n, m <= 300 -10^9 <= matrix[i][j] <= 10^9 每行的所有元素从左到右升序排列 每列的所有元素从上到下升序排列 -10^9 <= target <= 10^9 解题思路 这道题目提供了一个特殊性质的二维矩阵，要求我们查找一个目标值。矩阵的特性是每行从左到右升序，每列从上到下升序。根据这个特性，我们可以有多种解题思路。 方法一：角落搜索法 核心思想: 利用矩阵的排序特性，从右上角或左下角开始搜索，每次能够排除一行或一列。 从右上角（或左下角）开始搜索的原理： 若当前元素等于目标值，直接返回 true 若当前元素大于目标值，则可以排除当前列（因为当前列下方的元素更大） 若当前元素小于目标值，则可以排除当前行（因为当前行左侧的元素更小） 这种方法的时间复杂度是 O(m + n)，其中 m 是行数，n 是列数，因为每次操作都会排除一行或一列。 实现细节 我们从矩阵的右上角开始搜索： 初始化指针位置为右上角坐标 (0, columns-1) 当指针在矩阵范围内时，比较当前元素与目标值： 如果相等，返回 true 如果当前元素大于目标值，则向左移动（列索引减一） 如果当前元素小于目标值，则向下移动（行索引加一） 如果搜索结束后仍未找到目标值，返回 false 代码实现 123456789101112131415161718192021222324252627282930func searchMatrix(matrix [][]int, target int) bool { // 获取矩阵的行数和列数 rows := len(matrix) if rows == 0 { return false } columns := len(matrix[0]) // 从右上角开始搜索 row, col := 0, columns-1 // 当指针在矩阵范围内时继续搜索 for row < rows && col >= 0 { currentValue := matrix[row][col] if currentValue == target { // 找到目标值 return true } else if currentValue > target { // 当前值大于目标值，排除当前列 col-- } else { // 当前值小于目标值，排除当前行 row++ } } // 搜索完毕未找到目标值 return false} 方法二：二分查找法 核心思想: 由于每一行都是排序的，我们可以对每一行使用二分查找。 实现细节 遍历矩阵的每一行 对每一行使用二分查找寻找目标值 如果在任一行中找到目标值，返回 true 否则，返回 false 这种方法的时间复杂度是 O(m log n)，其中 m 是行数，n 是列数。 代码实现 12345678910111213141516171819202122232425262728293031323334353637func searchMatrix(matrix [][]int, target int) bool { // 获取矩阵行数 rows := len(matrix) if rows == 0 { return false } // 对每一行使用二分查找 for _, row := range matrix { // 如果在当前行找到目标值，返回 true if binarySearch(row, target) { return true } } // 所有行都搜索完毕未找到目标值 return false}// 二分查找辅助函数func binarySearch(nums []int, target int) bool { left, right := 0, len(nums)-1 for left <= right { mid := left + (right-left)/2 if nums[mid] == target { return true } else if nums[mid] > target { right = mid - 1 } else { left = mid + 1 } } return false} 方法三：分治法 核心思想: 利用矩阵的特性，将矩阵划分为四个子矩阵，递归搜索。 实现细节 找到矩阵中心点 (midRow, midCol) 将矩阵分为四个区域：左上、右上、左下、右下 比较中心点的值与目标值： 如果等于目标值，返回 true 如果大于目标值，则目标值可能在左上区域或左下区域或右上区域 如果小于目标值，则目标值可能在右下区域或右上区域或左下区域 递归搜索可能包含目标值的子矩阵 这种方法的时间复杂度在最坏情况下可能接近 O(m*n)，但在平均情况下表现较好。 代码实现 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253func searchMatrix(matrix [][]int, target int) bool { // 获取矩阵的行数和列数 rows := len(matrix) if rows == 0 { return false } columns := len(matrix[0]) // 调用递归搜索函数 return searchMatrixRecursively(matrix, target, 0, 0, rows-1, columns-1)}// 递归搜索函数func searchMatrixRecursively(matrix [][]int, target int, rowStart, colStart, rowEnd, colEnd int) bool { // 基本情况：超出矩阵范围 if rowStart > rowEnd || colStart > colEnd { return false } // 基本情况：矩阵只有一个元素 if rowStart == rowEnd && colStart == colEnd { return matrix[rowStart][colStart] == target } // 计算中心点坐标 rowMid := rowStart + (rowEnd-rowStart)/2 colMid := colStart + (colEnd-colStart)/2 // 中心点值 midValue := matrix[rowMid][colMid] // 如果找到目标值，直接返回 if midValue == target { return true } // 根据中心点值与目标值的关系，决定搜索哪些子矩阵 if midValue > target { // 搜索左上区域（行结束和列结束都是中心点） return searchMatrixRecursively(matrix, target, rowStart, colStart, rowMid, colMid) || // 搜索右上区域（行从开始到中心，列从中心+1到结束） searchMatrixRecursively(matrix, target, rowStart, colMid+1, rowMid, colEnd) || // 搜索左下区域（行从中心+1到结束，列从开始到中心） searchMatrixRecursively(matrix, target, rowMid+1, colStart, rowEnd, colMid) } else { // 搜索右下区域（行开始和列开始都是中心点+1） return searchMatrixRecursively(matrix, target, rowMid+1, colMid+1, rowEnd, colEnd) || // 搜索右上区域（行从开始到中心，列从中心+1到结束） searchMatrixRecursively(matrix, target, rowStart, colMid+1, rowMid, colEnd) || // 搜索左下区域（行从中心+1到结束，列从开始到中心） searchMatrixRecursively(matrix, target, rowMid+1, colStart, rowEnd, colMid) }} 复杂度分析 方法 时间复杂度 空间复杂度 优点 缺点 角落搜索法 O(m + n) O(1) 非常高效，实现简单 需要理解特定的搜索策略 二分查找法 O(m log n) O(1) 易于理解，二分查找是常见算法 对于大矩阵，比角落搜索法慢 分治法 最坏 O(m*n) O(log(m*n)) 适用于更一般的搜索问题 实现复杂，递归调用开销大 综合考虑，角落搜索法（方法一）是解决此问题最高效的方法，它充分利用了矩阵的特性，时间复杂度为 O(m + n)，空间复杂度为 O(1)。 关键学习点 利用数据结构特性：矩阵的排序特性使我们能够设计出 O(m+n) 的算法。在解决问题时，充分理解并利用数据的特殊性质往往能找到最优解。 搜索空间缩减：角落搜索法的核心思想是每次操作都能排除一行或一列，有效地缩小搜索空间。 多种解法思考：同一个问题可以有多种解法，从暴力法到优化解法，通过比较不同算法的复杂度，可以找到最适合的解决方案。 二维空间的搜索技巧：对于二维空间的搜索问题，可以考虑从特殊点（如角落）开始，利用排序特性引导搜索方向。
LeetCode 2563 - 统计公平数对的数目（Count the Number of Fair Pairs）
问题描述 给你一个下标从 0 开始、长度为 n 的整数数组 nums 和两个整数 lower 和 upper，返回公平数对的数目。 如果 (i, j) 数对满足以下情况，则认为是一个公平数对： 0 ≤ i < j < n 且 lower ≤ nums[i] + nums[j] ≤ upper 示例 1: 123输入: nums = [0,1,7,4,4,5], lower = 3, upper = 6输出: 6解释: 共计 6 个公平数对: (0,3), (0,4), (0,5), (1,3), (1,4) 和 (1,5)。 示例 2: 123输入: nums = [1,7,9,2,5], lower = 11, upper = 11输出: 1解释: 只有单个公平数对: (2,3)。 提示: 1 ≤ nums.length ≤ 10^5 nums.length == n -10^9 ≤ nums[i] ≤ 10^9 -10^9 ≤ lower ≤ upper ≤ 10^9 解题思路 这道题目要求统计符合条件的数对数量，主要难点在于如何高效地找出所有满足 lower ≤ nums[i] + nums[j] ≤ upper 的数对。 一个常见的思路是使用嵌套循环枚举所有可能的数对，但这种方法的时间复杂度为 O(n²)，在数组长度较大时会超时。 我们可以利用排序 + 二分查找来优化解法： 首先对数组 nums 进行排序 对于每个元素 nums[j]，我们需要找出有多少个索引 i (i < j) 满足： lower ≤ nums[i] + nums[j] ≤ upper 即 lower - nums[j] ≤ nums[i] ≤ upper - nums[j] 由于数组已排序，我们可以使用二分查找： 找到第一个满足 nums[i] ≥ lower - nums[j] 的位置 left 找到第一个满足 nums[i] > upper - nums[j] 的位置 right 则满足条件的元素个数为 right - left 具体实现步骤 实现这个解法，我们可以按照以下步骤操作： 对 nums 数组排序 初始化计数器 res = 0 遍历数组中的每个位置 j： 对于当前元素 nums[j]，在 nums[0...j-1] 中二分查找： 找到第一个大于等于 lower - nums[j] 的位置 left 找到第一个大于 upper - nums[j] 的位置 right 将 right - left 加到结果 res 上 返回最终的 res 在 Golang 中，我们可以使用标准库中的 sort.SearchInts 函数来执行二分查找。 但实际上，这里有一个小问题需要注意：在题目中，我们需要找的是 nums[i] ≤ upper - nums[j] 的最右边界，而 sort.SearchInts 找的是第一个 >= 目标值的位置。所以我们需要查找的是 upper - nums[j] + 1，即找到第一个大于 upper - nums[j] 的位置。 代码实现 1234567891011func countFairPairs(nums []int, lower int, upper int) (res int64) { sort.Ints(nums) for j := 0; j < len(nums); j++ { right := sort.SearchInts(nums[:j], upper-nums[j]+1) left := sort.SearchInts(nums[:j], lower-nums[j]) res += int64(right - left) } return} 执行过程分析 让我们以示例 1 为例，跟踪代码的执行过程： 1nums = [0,1,7,4,4,5], lower = 3, upper = 6 排序后： 1nums = [0,1,4,4,5,7] 遍历每个位置 j： j = 0: 没有比 0 更小的索引，跳过 j = 1: nums[1] = 1 在 nums[0:1] = [0] 中查找 ≥ lower-nums[1] = 3-1 = 2 的位置 left = 1 在 nums[0:1] = [0] 中查找 ≥ upper-nums[1]+1 = 6-1+1 = 6 的位置 right = 1 添加 right-left = 1-1 = 0 对 j = 2: nums[2] = 4 在 nums[0:2] = [0,1] 中查找 ≥ lower-nums[2] = 3-4 = -1 的位置 left = 0 在 nums[0:2] = [0,1] 中查找 ≥ upper-nums[2]+1 = 6-4+1 = 3 的位置 right = 2 添加 right-left = 2-0 = 2 对: (0,2), (1,2) j = 3: nums[3] = 4 在 nums[0:3] = [0,1,4] 中查找 ≥ lower-nums[3] = 3-4 = -1 的位置 left = 0 在 nums[0:3] = [0,1,4] 中查找 ≥ upper-nums[3]+1 = 6-4+1 = 3 的位置 right = 2 添加 right-left = 2-0 = 2 对: (0,3), (1,3) j = 4: nums[4] = 5 在 nums[0:4] = [0,1,4,4] 中查找 ≥ lower-nums[4] = 3-5 = -2 的位置 left = 0 在 nums[0:4] = [0,1,4,4] 中查找 ≥ upper-nums[4]+1 = 6-5+1 = 2 的位置 right = 2 添加 right-left = 2-0 = 2 对: (0,4), (1,4) j = 5: nums[5] = 7 在 nums[0:5] = [0,1,4,4,5] 中查找 ≥ lower-nums[5] = 3-7 = -4 的位置 left = 0 在 nums[0:5] = [0,1,4,4,5] 中查找 ≥ upper-nums[5]+1 = 6-7+1 = 0 的位置 right = 0 添加 right-left = 0-0 = 0 对 最终结果: 0 + 0 + 2 + 2 + 2 + 0 = 6 对，符合预期。 复杂度分析 时间复杂度: O(n log n) 排序的时间复杂度为 O(n log n) 遍历数组需要 O(n)，每次遍历中进行两次二分查找，每次二分查找的时间复杂度为 O(log n) 总时间复杂度为 O(n log n) 空间复杂度: O(log n) 或 O(n) 除了输入数组外，排序可能需要 O(log n) 的栈空间 如果排序算法就地进行，则额外空间复杂度为 O(log n) 如果使用额外空间进行排序，则空间复杂度为 O(n) 关键收获 排序 + 二分查找: 这是解决区间查询问题的一种常见技巧。先将数组排序，然后通过二分查找快速确定符合条件的元素范围。 等价转换: 将条件 lower ≤ nums[i] + nums[j] ≤ upper 转换为 lower - nums[j] ≤ nums[i] ≤ upper - nums[j]，这样可以对固定的 nums[j] 查找符合条件的 nums[i]。 边界处理: 在使用标准库的二分查找函数时，需要正确理解函数的行为和边界处理。例如，sort.SearchInts 返回的是第一个大于等于目标值的位置，如果想找最后一个小于等于目标值的位置，需要做相应调整。 索引范围控制: 在二分查找中，需要明确在哪个范围内查找。在本题中，我们只在 nums[0:j] 范围内查找，确保 i < j。 这道题是对二分查找和排序应用的一个很好的例子，展示了如何通过预处理和高效的查找算法将时间复杂度从 O(n²) 优化到 O(n log n)。
LeetCode 48 - 旋转图像（Rotate Image）
问题描述 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 示例 1： 12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]] 旋转前： 1231 2 34 5 67 8 9 旋转后： 1237 4 18 5 29 6 3 示例 2： 12输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] 旋转前： 1234 5 1 9 11 2 4 8 1013 3 6 715 14 12 16 旋转后： 123415 13 2 514 3 4 112 6 8 916 7 10 11 约束条件： n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 解题思路 旋转图像是一个经典的矩阵操作问题。关键在于：如何在不使用额外空间的情况下完成矩阵的旋转。 首先，让我们理解一下顺时针旋转 90 度对矩阵元素位置的影响： 对于位置 (i, j) 的元素，旋转后它将位于 (j, n-1-i) 这个规律可以帮助我们直接交换元素，但直接这样操作会导致覆盖其他元素。因此，我们可以采用分解为多个简单变换的方法。 方法：转置 + 水平翻转 这个方法将 90 度旋转分解为两个简单的矩阵操作： 矩阵转置（沿主对角线翻转） 水平翻转（左右列交换） 步骤详解： 矩阵转置： 遍历矩阵的一半（对角线以下部分），交换 matrix[i][j] 和 matrix[j][i] 这一步将行变为列，列变为行 水平翻转： 对每一行进行左右翻转 将第 j 列和第 n-1-j 列交换 这两步操作组合起来，正好等同于将矩阵顺时针旋转 90 度。 我们可以通过一个例子来说明这个过程： 原始矩阵： 1231 2 34 5 67 8 9 转置后： 1231 4 72 5 83 6 9 水平翻转后： 1237 4 18 5 29 6 3 可以看到，最终结果正是原矩阵顺时针旋转 90 度后的结果。 实现细节 实现过程中，需要注意以下几点： 在转置操作中，我们只需要遍历矩阵的一半（主对角线以下的部分），避免重复交换 在水平翻转中，只需要遍历每行的前一半列 所有操作都是原地进行的，不需要额外的空间 代码实现 12345678910111213141516func rotate(matrix [][]int) { // 先沿着主对角线进行对称反转 n := len(matrix) for i := 0; i < n; i++ { for j := 0; j < i; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } // 然后每一行进行水平翻转 for i := 0; i < n; i++ { for j := 0; j < n/2; j++ { matrix[i][n-1-j], matrix[i][j] = matrix[i][j], matrix[i][n-1-j] } }} 复杂度分析 时间复杂度：O(n²)，其中 n 是矩阵的边长。需要遍历整个矩阵两次。 空间复杂度：O(1)，只使用了常数级别的额外空间。 其他可能的方法 除了上述方法外，还有另一种旋转方法：层层旋转。 此方法的思路是： 将矩阵看作由多个同心方形环组成 对每一层的四条边上的元素进行旋转交换 从外到内依次处理每一层 代码实现会稍微复杂一些，需要小心处理索引，但时间和空间复杂度与上述方法相同。 比较 方面 转置+水平翻转 层层旋转 时间复杂度 O(n²) O(n²) 空间复杂度 O(1) O(1) 优点 实现简单，思路清晰 直观对应旋转过程 缺点 分解为两步不直观 索引处理复杂 推荐度 ★★★★★ ★★★☆☆ 关键收获 矩阵操作的分解思想：将复杂的矩阵操作分解为简单操作的组合 原地算法的实现技巧：如何通过元素交换实现空间优化 矩阵转置和水平翻转：这是两个常用的矩阵操作，在其他问题中也经常用到 对于矩阵旋转问题，关键是找到元素变换前后位置的对应关系，然后利用这种关系设计高效的算法。
LeetCode 54 - 螺旋矩阵（Spiral Matrix）解题思路与错误分析
问题描述 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 示例 1： 12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 上面这个示例中，螺旋顺序遍历的过程如下： 123→ → →↑ ↓↑ ← ↓ 示例 2： 12输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 这个例子中，螺旋遍历的路径是： 123→ → → →↑ ↓↑ ← ← ↓ 约束条件： m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 解题思路 螺旋矩阵是一个典型的数组遍历问题，核心在于如何控制遍历的方向和边界。我们需要按照顺时针螺旋的顺序（右 → 下 → 左 → 上）依次访问矩阵中的所有元素。 方法一：按层模拟（边界法） 这个方法的核心思想是：将整个矩阵看作由多个"环"（层）组成，从外到内一层一层地剥离遍历。 步骤详解： 初始化四个边界： left = 0：左边界 right = 列数-1：右边界 top = 0：上边界 bottom = 行数-1：下边界 循环遍历各层，直到 left > right 或 top > bottom： a. 从左到右遍历上边界上的元素： 遍历 matrix[top][j]，其中 j 从 left 到 right 遍历完后，上边界下移：top++ b. 从上到下遍历右边界上的元素： 遍历 matrix[i][right]，其中 i 从 top 到 bottom 遍历完后，右边界左移：right-- c. 检查是否还有行需要遍历（防止单行情况重复遍历）： 如果 top <= bottom，从右到左遍历下边界上的元素： 遍历 matrix[bottom][j]，其中 j 从 right 到 left 遍历完后，下边界上移：bottom-- d. 检查是否还有列需要遍历（防止单列情况重复遍历）： 如果 left <= right，从下到上遍历左边界上的元素： 遍历 matrix[i][left]，其中 i 从 bottom 到 top 遍历完后，左边界右移：left++ 重复第 2 步，直到所有元素都被遍历完。 关键注意点： 在每一轮遍历中，边界会收缩，形成一个逐渐缩小的矩形 需要特别注意单行或单列的情况，避免重复访问元素 方法二：方向数组法 这种方法使用方向数组来模拟螺旋过程，关键在于知道何时改变方向。 步骤详解： 定义方向数组：表示四种移动方向（右、下、左、上） 1directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} 创建访问标记数组：避免重复访问 1234visited := make([][]bool, rows)for i := range visited { visited[i] = make([]bool, cols)} 遍历矩阵： 从(0,0)开始，按当前方向移动 记录已访问的位置 当需要转向时（即下一步会越界或已访问过），顺时针旋转方向 我的错误实现及分析 我最初的实现采用了方向数组的方法，代码如下： 12345678910111213141516171819202122232425262728func spiralOrder(matrix [][]int) []int { row := len(matrix) col := len(matrix[0]) dirX, dirY := []int{0, 1, 0, -1}, []int{1, 0, -1, 0} index := 0 x, y, cnt := 0, 0, 0 res := make([]int, row*col) for cnt < row*col { res[cnt] = matrix[x][y] nextX := x + dirX[index] nextY := y + dirY[index] if nextX < 0 || nextX >= row || nextY < 0 || nextY >= col { index = (index + 1) % 4 nextX = x + dirX[index] nextY = y + dirY[index] } x = nextX y = nextY cnt++ } return res} 错误分析： 让我们通过一个简单的例子来分析这段代码的问题： 12345[ [1,2,3], [4,5,6], [7,8,9]] 按照代码的执行逻辑： 首先访问 (0,0)：值为 1，添加到结果 按照右方向移动到 (0,1)：值为 2，添加到结果 继续按照右方向移动到 (0,2)：值为 3，添加到结果 继续按照右方向尝试移动到 (0,3)，但这超出了边界 改变方向为下，移动到 (1,2)：值为 6，添加到结果 继续按照下方向移动到 (2,2)：值为 9，添加到结果 继续按照下方向尝试移动到 (3,2)，但这超出了边界 改变方向为左，移动到 (2,1)：值为 8，添加到结果 继续按照左方向移动到 (2,0)：值为 7，添加到结果 继续按照左方向尝试移动到 (2,-1)，但这超出了边界 改变方向为上，移动到 (1,0)：值为 4，添加到结果 - 这里出现了问题！ 我们再次访问了 (0,0)，造成了死循环！因为代码只检查了边界条件，没有检查是否已经访问过该位置。正确的做法应该是使用一个额外的数组来标记已访问的位置。 我的另一个错误实现及分析 在尝试实现边界法的过程中，我还犯了另一个常见错误： 1234567891011121314151617181920212223242526272829303132333435363738394041func spiralOrder(matrix [][]int) []int { row := len(matrix) col := len(matrix[0]) res := make([]int, row*col) cnt := 0 left, right, top, bottom := 0, col-1, 0, row-1 for cnt < row*col { // 向右遍历 for i := left; i <= right; i++ { res[cnt] = matrix[top][i] cnt++ } top++ // 向下遍历 for i := top; i <= bottom; i++ { res[cnt] = matrix[i][right] cnt++ } right-- // 向左遍历 for i := right; i >= left; i-- { res[cnt] = matrix[bottom][i] cnt++ } bottom-- // 向上遍历 for i := bottom; i >= top; i-- { res[cnt] = matrix[i][left] cnt++ } left++ } return res} 错误分析： 这段代码的主要问题是缺少边界检查。以矩阵 [[1,2,3],[4,5,6]]（2 行 3 列）为例，分析执行过程： 初始状态：left=0, right=2, top=0, bottom=1, cnt=0 向右遍历：添加 [1,2,3]，cnt=3, top=1 向下遍历：添加 [6]，cnt=4, right=1 向左遍历：添加 [5,4]，cnt=6, bottom=0 问题出现：此时 top=1, bottom=0，已经交叉，但代码没有检查就继续执行向上遍历 当 top > bottom 或 left > right 时，说明当前层已经遍历完毕，应该结束循环。但这个实现中缺少了这一关键检查，导致在单行或单列等特殊情况下会重复访问元素，甚至可能发生数组越界。 另一个问题是，当矩阵只有一行或一列时，执行完一个方向的遍历后，立即执行下一个方向的遍历可能会重复处理元素。例如，对于一个单行矩阵 [[1,2,3]]： 向右遍历后 top 增加，此时 top > bottom 但代码仍会执行向下、向左和向上遍历，导致越界或重复访问 修复方法： 在每个方向遍历后，需要检查更新后的边界条件是否仍然有效： 123456789101112131415161718192021222324252627282930313233343536373839404142434445func spiralOrderFixed(matrix [][]int) []int { if len(matrix) == 0 { return []int{} } row := len(matrix) col := len(matrix[0]) res := make([]int, 0, row*col) left, right, top, bottom := 0, col-1, 0, row-1 for left <= right && top <= bottom { // 向右遍历 for i := left; i <= right; i++ { res = append(res, matrix[top][i]) } top++ // 向下遍历（需要先检查边界） if top <= bottom { for i := top; i <= bottom; i++ { res = append(res, matrix[i][right]) } right-- } // 向左遍历（需要先检查边界） if left <= right && top <= bottom { for i := right; i >= left; i-- { res = append(res, matrix[bottom][i]) } bottom-- } // 向上遍历（需要先检查边界） if left <= right && top <= bottom { for i := bottom; i >= top; i-- { res = append(res, matrix[i][left]) } left++ } } return res} 错误的根本原因： 这个错误的根本原因是没有考虑边界条件。在处理矩阵类问题时，尤其需要注意： 边界交叉检查：确保索引边界（如 left <= right 和 top <= bottom）始终有效 特殊情况处理：矩阵可能是单行、单列、甚至空矩阵 方向转换条件：每次改变遍历方向前需要验证还有元素需要遍历 这是矩阵遍历问题中最容易被忽视的细节，也是导致代码出错的常见原因。 正确实现 方法一：按层模拟（推荐） 123456789101112131415...
LeetCode 42 - 接雨水（Trapping Rain Water）
问题描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 12输入：height = [4,2,0,3,2,5]输出：9 示意图： 12345 ## ## # ## # ##### ## 约束条件： n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 解题思路 接雨水问题的核心在于理解：对于每个位置，它能接的雨水量等于该位置左右两侧最高柱子的较小值减去该位置的高度。 这个问题有多种解法，我们将介绍三种主要方法：动态规划、双指针和单调栈。 方法一：动态规划 核心思想：预处理每个位置的左侧最大高度和右侧最大高度，然后计算每个位置能接的雨水量。 步骤详解： 创建两个数组 leftMax 和 rightMax，分别存储每个位置的左侧最大高度和右侧最大高度 从左到右遍历数组，计算每个位置的左侧最大高度 从右到左遍历数组，计算每个位置的右侧最大高度 再次遍历数组，对于每个位置 i，计算 min(leftMax[i], rightMax[i]) - height[i]，累加得到总雨水量 这种方法直观易懂，适合初学者理解问题。 方法二：双指针法 核心思想：使用左右两个指针从两端向中间移动，同时记录左右两侧遇到的最大高度，优化空间复杂度。 步骤详解： 初始化左指针 left = 0 和右指针 right = n-1 记录左侧和右侧的最大高度 leftMax = 0 和 rightMax = 0 当左指针小于右指针时，执行以下操作： 如果 height[left] < height[right]： 如果 height[left] >= leftMax，更新 leftMax 否则，累加 leftMax - height[left] 到结果中 左指针向右移动 否则： 如果 height[right] >= rightMax，更新 rightMax 否则，累加 rightMax - height[right] 到结果中 右指针向左移动 这种方法优化了空间复杂度，只需要常数额外空间。 方法三：单调栈 核心思想：使用单调递减栈来找到"凹"形区域，计算能接的雨水量。 步骤详解： 维护一个单调递减栈，栈中存储柱子的下标 遍历数组，对于每个柱子： 当栈不为空且当前柱子高度大于栈顶柱子高度时： 弹出栈顶元素 top（作为凹槽的底部） 如果栈为空，无法形成凹槽，继续 计算宽度：当前下标 - 新栈顶下标 - 1 计算高度：min(当前柱子高度, 新栈顶柱子高度) - 底部高度 累加 宽度 × 高度 到结果中 将当前下标入栈 单调栈方法适合理解雨水积累的过程，特别是对于理解"凹"形区域的积水计算。 代码实现 方法一：动态规划 1234567891011121314151617181920212223242526272829303132333435363738394041424344func trap(height []int) int { n := len(height) if n <= 2 { return 0 } // 预处理左右最大高度 leftMax := make([]int, n) rightMax := make([]int, n) // 计算每个位置的左侧最大高度 leftMax[0] = height[0] for i := 1; i < n; i++ { leftMax[i] = max(leftMax[i-1], height[i]) } // 计算每个位置的右侧最大高度 rightMax[n-1] = height[n-1] for i := n-2; i >= 0; i-- { rightMax[i] = max(rightMax[i+1], height[i]) } // 计算总雨水量 result := 0 for i := 0; i < n; i++ { result += min(leftMax[i], rightMax[i]) - height[i] } return result}func max(a, b int) int { if a > b { return a } return b}func min(a, b int) int { if a < b { return a } return b} 方法二：双指针法 12345678910111213141516171819202122232425func trap(height []int) int { left, right := 0, len(height)-1 leftMax, rightMax := 0, 0 result := 0 for left < right { if height[left] < height[right] { if height[left] >= leftMax { leftMax = height[left] } else { result += leftMax - height[left] } left++ } else { if height[right] >= rightMax { rightMax = height[right] } else { result += rightMax - height[right] } right-- } } return result} 方法三：单调栈 12345678910111213141516171819202122232425262728293031323334func trap(height []int) int { n := len(height) if n <= 2 { return 0 } res := 0 stack := make([]int, 0) for i := 0; i < n; i++ { // 当栈不为空且当前高度大于栈顶高度时，可以形成凹槽 for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] { // 弹出栈顶，作为凹槽底部 top := stack[len(stack)-1] stack = stack[:len(stack)-1] // 如果栈为空，无法形成凹槽 if len(stack) <= 0 { break } // 计算凹槽的宽度和高度 left := stack[len(stack)-1] width := i - left - 1 h := min(height[i], height[left]) - height[top] res += width * h } // 当前索引入栈 stack = append(stack, i) } return res} 执行过程分析 以示例 [0,1,0,2,1,0,1,3,2,1,2,1] 分析双指针法的执行过程： 初始状态： left = 0, right = 11 leftMax = 0, rightMax = 0 result = 0 执行过程： height[0] = 0 < height[11] = 1 leftMax = max(0, 0) = 0 result += 0 - 0 = 0 left = 1 height[1] = 1 = height[11] = 1 (相等，任选一边) leftMax = max(0, 1) = 1 left = 2 height[2] = 0 < height[11] = 1 result += 1 - 0 = 1 left = 3 height[3] = 2 > height[11] = 1 rightMax = max(0, 1) = 1 result += 1 - 1 = 0 right = 10 height[3] = 2 = height[10] = 2 rightMax = max(1, 2) = 2 right = 9 … (继续执行直到 left >= right) 最终结果：result = 6 方法比较 方面 动态规划 双指针法 单调栈 时间复杂度 O(n) O(n) O(n) 空间复杂度 O(n) O(1) O(n) 易理解性 最直观，容易理解 抽象，需要理解左右边界 适合理解凹槽积水过程 实现复杂度 简单 中等 较复杂 优点 思路清晰 空间效率最高 能处理多种地形 缺点 需要额外空间 思路不够直观 实现复杂 推荐度 ★★★★☆ ★★★★★ ★★★☆☆ 复杂度分析 时间复杂度： 动态规划：O(n)，需要三次遍历数组 双指针：O(n)，只需一次遍历 单调栈：O(n)，每个元素最多入栈出栈各一次 空间复杂度： 动态规划：O(n)，需要两个额外数组 双指针：O(1)，只使用常数额外空间 单调栈：O(n)，最坏情况下栈的大小为 n 核心要点 理解积水条件：对于位置 i，能接的水量取决于 min(左侧最高，右侧最高) - 当前高度 优化思路：从空间 O(n) 到 O(1) 的优化是本题的一个亮点 双指针技巧：利用双指针避免使用额外空间，是解决此类问题的重要技巧 相关题目 LeetCode 11: 盛最多水的容器 LeetCode 407: 接雨水 II（三维版本） LeetCode 238: 除自身以外数组的乘积（类似的预处理思想） 总结 接雨水问题展示了多种算法思想：动态规划的预处理、双指针的空间优化、单调栈处理特定形状。通过分析每个位置能接的雨水量，我们可以得到整体的结果。在实际应用中，双指针法因其 O(1) 的空间复杂度而被认为是最优解，但动态规划法更易于理解和实现。
LeetCode 41 - 缺失的第一个正数（First Missing Positive）
问题描述 给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。 示例 1： 12输入：nums = [1,2,0]输出：3 示例 2： 12输入：nums = [3,4,-1,1]输出：2 示例 3： 12输入：nums = [7,8,9,11,12]输出：1 约束条件： 1 <= nums.length <= 5 * 10^5 -2^31 <= nums[i] <= 2^31 - 1 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 解题思路 这道题的关键在于理解一个重要的性质：如果长度为 n 的数组包含所有 1 到 n 的数字，那么缺失的第一个正数就是 n+1。如果存在缺失，那么答案一定在 1 到 n+1 之间。 基于这个性质，我们可以利用数组本身作为哈希表，实现原地哈希。思路是将值 x 放到索引 x-1 的位置，这样当我们再次遍历数组时，第一个不满足 nums[i] == i+1 的位置就是缺失的第一个正数。 原地哈希的核心思想 假设我们有一个完美的数组，其中： 12345nums[0] = 1nums[1] = 2nums[2] = 3...nums[i] = i+1 这样的数组中，每个正数都在"家"（正确的位置）。对于值 x，它的"家"是索引 x-1。 当数组中有缺失的正数时，我们就能通过查找哪个位置上的数不是"应该在那里的数"来找到答案。 算法步骤： 原地哈希排序： 遍历数组，将每个在 [1, n] 范围内的数放到其对应的位置 对于每个元素 nums[i]，如果 1 ≤ nums[i] ≤ n 并且 nums[i] ≠ nums[nums[i]-1]，则交换 nums[i] 和 nums[nums[i]-1] 继续检查交换后的 nums[i]，直到不需要交换为止 查找缺失的最小正数： 再次遍历数组，找到第一个不满足 nums[i] = i+1 的位置 该位置的索引 +1 就是答案 图示说明 对于数组 [3,4,-1,1]，原地哈希过程： 初始状态: [ 3, 4, -1, 1] ↓ 排序过程: [-1, 1, 3, 4] ↓ ↓ 最终状态: [ 1, -1, 3, 4] ↓ 缺失的是 2 代码实现 1234567891011121314151617181920212223func firstMissingPositive(nums []int) int { n := len(nums) // 第一阶段：将每个数放到正确的位置 for i := 0; i < n; i++ { // nums[i] 应该放在索引 nums[i]-1 的位置 // 只处理在 [1,n] 范围内的值，且目标位置没有正确的值 for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] { // 交换 nums[i] 和 nums[nums[i]-1] nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] } } // 第二阶段：找出第一个不满足 nums[i] == i+1 的位置 for i := 0; i < n; i++ { if nums[i] != i+1 { return i + 1 } } // 如果数组包含了 1 到 n 的所有数，则缺失的第一个正数是 n+1 return n + 1} 执行过程分析 以数组 [3, 4, -1, 1] 为例，详细分析执行过程： 第一阶段：原地哈希排序 i=0, nums[0]=3 3 应该在索引 2 的位置 交换 nums[0] 和 nums[2]：[3, 4, -1, 1] → [-1, 4, 3, 1] i=0, nums[0]=-1 -1 不在范围 [1, n] 内，跳过 i=1, nums[1]=4 4 应该在索引 3 的位置 交换 nums[1] 和 nums[3]：[-1, 4, 3, 1] → [-1, 1, 3, 4] i=1, nums[1]=1 1 应该在索引 0 的位置 交换 nums[1] 和 nums[0]：[-1, 1, 3, 4] → [1, -1, 3, 4] i=1, nums[1]=-1 -1 不在范围 [1, n] 内，跳过 i=2, nums[2]=3 3 已经在正确的位置（索引 2），跳过 i=3, nums[3]=4 4 已经在正确的位置（索引 3），跳过 排序完成后的数组：[1, -1, 3, 4] 第二阶段：查找缺失的最小正数 i=0, nums[0]=1 == 0+1 ✓ i=1, nums[1]=-1 != 1+1 ✗ 找到了第一个不满足条件的位置 i=1，因此答案是 1+1 = 2。 复杂度分析 时间复杂度：O(n) 虽然有嵌套循环，但每个元素最多被交换一次到正确位置，一旦到达正确位置就不会再移动 第二次遍历是线性的 O(n) 空间复杂度：O(1) 原地修改数组，不使用额外空间 常见错误与优化 死循环问题： 在内层循环的交换条件中，必须包含 nums[nums[i]-1] != nums[i] 否则当 nums[i] 等于 nums[nums[i]-1] 时会陷入无限交换的死循环 提前返回问题： 不能在第一阶段结束前判断结果，必须完成整个排序过程 因为数组可能还没有完全排好序 边界处理： 注意处理负数和超出数组长度的值，它们不需要参与交换 相关题目 LeetCode 268: 丢失的数字 LeetCode 287: 寻找重复数 LeetCode 448: 找到所有数组中消失的数字 总结 缺失的第一个正数问题是一个经典的原地哈希问题。关键洞察在于：对于长度为 n 的数组，答案一定在 1 到 n+1 之间，这使得我们可以利用数组本身作为哈希表，将值 x 放在索引 x-1 的位置上。 这种方法的精妙之处在于它既满足了 O(n) 的时间复杂度要求，又满足了 O(1) 的空间复杂度要求。它展示了如何通过巧妙地利用问题约束来设计高效算法的思想。