Java LeetCode篇-深入了解二叉树经典解法（三种方式实现：获取二叉树的最大深度）

2024-08-10




class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

这段代码是一个典型的递归解法来解决获取二叉树最大深度的问题。首先检查根节点是否为空，如果为空则返回0，表示空树的深度为0。如果不为空，则递归计算其左子树和右子树的最大深度，并返回其中较大的一个深度加1，因为加上当前节点就是整个子树的深度。

System

2024-08-10

所有,golang

题目描述：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

示例：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

进阶：

你能设计一个时间复杂度为 O(log(m + n)) 的算法解决此问题吗？

Python 解法：




class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1 + nums2
        nums.sort()
        n = len(nums)
        if n % 2 == 1:
            return nums[n // 2]
        else:
            return (nums[n // 2 - 1] + nums[n // 2]) / 2.0

Go 解法：




package main
 
import (
    "sort"
)
 
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums := append(nums1, nums2...)
    sort.Ints(nums)
    n := len(nums)
    if n%2 == 1 {
        return float64(nums[n/2])
    } else {
        return float64(nums[n/2-1]+nums[n/2]) / 2.0
    }
}
 
func main() {
    // 测试用例
}

这两个解法都是将两个数组合并，然后排序，最后根据排序后数组的长度是奇数还是偶数来计算中位数。如果是奇数，中位数就是中间的元素；如果是偶数，中位数是中间两个元素的平均值。

- 阅读更多 -

Golang | Leetcode Golang题解之第61题旋转链表

System

2024-08-09

所有,golang




/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil {
        return nil
    }
 
    // 计算链表长度
    length := 1
    current := head
    for current.Next != nil {
        current = current.Next
        length++
    }
 
    // 计算旋转次数
    rotateTimes := length - k%length
    if rotateTimes == length {
        return head
    }
 
    // 找到旋转起始点的前一个节点
    current.Next = head
    for i := 0; i < length - rotateTimes - 1; i++ {
        current = current.Next
    }
 
    // 新的头节点是旋转起始点的下一个节点
    newHead := current.Next
    current.Next = nil
 
    return newHead
}

这段代码首先检查了链表是否为空，并计算了链表的长度。然后根据需要旋转的次数计算出实际需要旋转的次数，以防k大于链表长度时。接着找到新的头节点，并将整个链表形成一个环，最后断开环的部分并返回新的头节点。

- 阅读更多 -

Java LeetCode篇-深入了解关于单链表的经典解法

System

2024-08-08

所有,java

以下是一个针对LeetCode上经典问题的Java代码解法示例，这个问题是关于删除链表中的重复节点。




// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
 
        ListNode current = head;
        while (current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
 
        return head;
    }
}

这段代码首先检查链表是否为空，然后遍历链表，如果发现相邻节点值相同，则删除后续重复的节点。最后返回处理后的链表头节点。这是一个典型的对链表进行节点删除操作的解法，适用于解决LeetCode上的其他相关问题。

- 阅读更多 -

Golang | Leetcode Golang题解之第70题爬楼梯

System

2024-08-07

所有,golang

Golang | Leetcode Golang题解之第70题爬楼梯

一、背景与问题

LeetCode第70题“爬楼梯”是经典的动态规划入门题。题目描述为：假设你正在爬楼梯，需要n步才能到达顶部。每次你可以爬1或2个台阶。请计算有多少种不同的方法可以到达楼顶。

这个问题看似简单，但隐藏着丰富的算法思维层次。其本质是斐波那契数列的变体，但需要考虑边界条件和性能优化。通过本篇文章，我们将深入探讨其算法原理、实现方式、性能优化以及实际应用场景。

二、基本原理

1. 数学建模

问题可以转化为求斐波那契数列的第n+1项。因为：

n=1时，方法数=1（1步）
n=2时，方法数=2（1+1或2步）
n=3时，方法数=3（1+1+1, 1+2, 2+1）
...
递推公式：f(n) = f(n-1) + f(n-2)

2. 算法分类

常见解法包括：

递归法（指数级时间复杂度）
迭代法（线性时间复杂度）
动态规划（线性时间复杂度）
空间优化的动态规划（常数空间复杂度）
矩阵快速幂法（对数时间复杂度）

3. 算法复杂度分析

方法	时间复杂度	空间复杂度	适用场景
递归	O(2^n)	O(n)	小规模测试
迭代	O(n)	O(1)	常规场景
动态规划	O(n)	O(n)	大规模数据
空间优化	O(n)	O(1)	空间敏感场景
矩阵快速幂	O(log n)	O(1)	极大n值计算

三、环境准备

# 安装Go环境（假设已安装）
# 创建项目结构
mkdir staircase-problem
cd staircase-problem
touch main.go

四、核心实现

1. 递归实现（不推荐）

package main

import "fmt"

func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

func main() {
    fmt.Println(climbStairs(5)) // 输出8
}

关键代码解释：

递归调用栈深度与n成正比
时间复杂度呈指数增长，n=40时会栈溢出
错误示例：未处理n=0的情况

2. 迭代实现（推荐）

package main

import "fmt"

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    a, b := 1, 2
    for i := 2; i < n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    fmt.Println(climbStairs(5)) // 输出8
}

关键代码解释：

使用双变量保存前两个状态
时间复杂度O(n)，空间复杂度O(1)
处理了n=0的边界情况

3. 空间优化的动态规划

package main

import "fmt"

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

func main() {
    fmt.Println(climbStairs(5)) // 输出8
}

关键代码解释：

使用数组保存所有中间结果
适合需要缓存中间结果的场景
空间复杂度O(n)

五、完整案例

1. Web服务接口实现

package main

import (
    "fmt"
    "net/http"
    "strconv"
)

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    a, b := 1, 2
    for i := 2; i < n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        nStr := r.URL.Query().Get("n")
        if nStr == "" {
            fmt.Fprintf(w, "Missing parameter n")
            return
        }
        n, err := strconv.Atoi(nStr)
        if err != nil {
            fmt.Fprintf(w, "Invalid parameter n")
            return
        }
        result := climbStairs(n)
        fmt.Fprintf(w, "Result: %d", result)
    })
    http.ListenAndServe(":8080", nil)
}

运行示例：
访问 http://localhost:8080/?n=5 将返回 Result: 8

实际应用场景：

用于计算不同步数的组合方案
可扩展为计算爬楼梯的不同路径数
需要处理大量并发请求时可考虑缓存

六、源码解析

以迭代实现为例，逐行分析：

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    a, b := 1, 2
    for i := 2; i < n; i++ {
        a, b = b, a+b
    }
    return b
}

处理n=0的特殊情况（通常不会出现）
处理n=1的特殊情况
初始化前两个状态a=1（n=1），b=2（n=2）
循环计算n>=3时的解
每次迭代更新a和b的值，保持a始终是前一个状态，b是当前状态

七、进阶使用

1. 矩阵快速幂法（对数时间复杂度）

package main

import (
    "fmt"
    "math"
)

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    // 矩阵快速幂计算斐波那契数
    return fib(n + 1)
}

func fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    // 构造变换矩阵 [[1,1],[1,0]]
    matrix := [][]int{{1, 1}, {1, 0}}
    result := matrixPower(matrix, n-1)
    return result[0][0]
}

func matrixPower(mat [][]int, power int) [][]int {
    // 初始化结果矩阵为单位矩阵
    res := [][]int{{1, 0}, {0, 1}}
    for power > 0 {
        if power%2 == 1 {
            res = matrixMultiply(res, mat)
        }
        mat = matrixMultiply(mat, mat)
        power /= 2
    }
    return res
}

func matrixMultiply(a, b [][]int) [][]int {
    result := make([][]int, len(a))
    for i := range result {
        result[i] = make([]int, len(b[0]))
        for j := range result[i] {
            result[i][j] = 0
            for k := range b {
                result[i][j] += a[i][k] * b[k][j]
            }
        }
    }
    return result
}

适用场景：

n极大时（如n=1e6）
需要快速计算斐波那契数的场景
适合数学计算库中的算法实现

八、性能与工程实践

1. 性能优化方法

优化方式	说明	效果
空间优化	用双变量代替数组	空间从O(n)降至O(1)
避免重复计算	使用记忆化缓存	避免递归的指数级计算
矩阵快速幂	将时间复杂度降至O(log n)	适合极大n值计算
并行计算	使用goroutine处理独立计算任务	适用于多核CPU环境

2. 异常处理

func climbStairs(n int) int {
    if n < 0 {
        panic("n cannot be negative")
    }
    if n == 0 {
        return 0
    }
    // ... 其他逻辑
}

3. 安全风险

输入验证：防止恶意输入导致计算错误
限制计算范围：防止整数溢出
使用safe math库：避免溢出问题

九、常见问题与踩坑

1. 常见错误示例

// 错误：未处理n=0的情况
func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

错误原因：

当n=0时会进入无限递归
当n=2时会返回0（因为n-1=1，n-2=0）

改进方案：

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

2. 其他常见问题

循环边界条件错误（如i < n vs i <= n）
数组越界访问（未初始化数组）
整数溢出（使用int类型时）

十、最佳实践

1. 推荐方案

常规场景：使用迭代法（O(n)时间，O(1)空间）
极大n值：使用矩阵快速幂法（O(log n)时间）
需要缓存中间结果：使用动态规划法
要求可读性：使用递归法（注意加记忆化）

2. 不推荐场景

需要处理大量并发请求时：避免使用递归法
对内存敏感的嵌入式系统：避免使用数组存储
需要实时计算的场景：避免使用动态规划法

十一、总结

LeetCode第70题爬楼梯作为经典的动态规划入门题，蕴含了丰富的算法思想。通过本文的深入探讨，我们了解到：

算法本质是斐波那契数列的变体，需要处理边界条件
不同实现方式有显著的性能差异，需根据实际场景选择
递归法虽然直观但存在严重性能问题
迭代法和空间优化的动态规划是工程实践中推荐的方案
矩阵快速幂法适合处理极大n值的计算
需要特别注意输入验证和异常处理

在实际项目中，当需要计算组合方案数时，可以考虑使用类似的动态规划思想。但要注意避免在需要处理大量并发请求或内存敏感的场景中使用递归或数组存储方案。通过合理选择算法实现方式，可以有效提升程序的性能和稳定性。

System

2024-08-07

所有,golang

【经典算法】LeetCode 27. 移除元素(Java/C/Python3/Go实现含注释说明,Easy)

一、背景与问题

LeetCode 27题"移除元素"是数组操作的经典问题，其核心要求是：给定一个数组和一个目标值，原地移除所有等于目标值的元素，并返回新数组的长度。该问题看似简单，但背后蕴含着对算法效率、内存管理、数据结构特性的深刻理解。

该问题的典型应用场景包括：

数据清洗时的元素过滤
数组压缩时的冗余元素删除
需要保持原地修改特性的算法设计

在实际开发中，该问题常出现在需要处理动态数组的场景，例如：

实时数据流处理系统
内存敏感的嵌入式系统
需要高效内存管理的缓存系统

二、基本原理

该问题的解决方案基于双指针法（Two Pointers），其核心思想是通过两个指针分别表示当前处理的位置和遍历的位置，通过一次遍历完成元素的筛选。

算法流程如下：

初始化两个指针：slow（指向当前已处理的最后一个位置）和fast（遍历数组）
遍历数组时，若fast指向的元素不等于val，则将其复制到slow的位置，并slow后移
遍历完成后，slow即为新数组的长度

该算法的时间复杂度为O(n)，空间复杂度为O(1)，满足题目对原地修改的要求。

三、环境准备

不同语言的实现需要不同的环境配置：

Java

JDK 1.8+
IDE：IntelliJ IDEA 或 Eclipse
无需额外依赖

C

GCC 编译器
编译命令：gcc -o remove_element remove_element.c

Python3

Python 3.8+
无需额外依赖

Go

Go 1.20+
IDE：VS Code + Go插件

四、核心实现

Java实现

public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        int slow = 0; // 慢指针，指向当前已处理的最后一个位置
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast]; // 将有效元素复制到slow位置
            }
        }
        return slow; // slow即为新数组的长度
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3};
        int val = 3;
        int newLength = removeElement(nums, val);
        System.out.println("新长度: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

关键代码解释：

slow指针始终指向当前已处理的最后一个有效元素的下一个位置
通过nums[slow++] = nums[fast]实现原地修改
最终返回slow作为新长度

C实现

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

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0; // 慢指针
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast]; // 原地修改
        }
    }
    return slow;
}

int main() {
    int nums[] = {3, 2, 2, 3};
    int val = 3;
    int newLength = removeElement(nums, 4, val);
    printf("新长度: %d\n", newLength);
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

关键点说明：

C语言数组是固定长度的，直接操作原数组
slow指针的递增操作确保内存连续性
返回的slow值即为新数组长度

Python3实现

def remove_element(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]  # 原地修改
            slow += 1
    return slow

# 测试用例
nums = [3, 2, 2, 3]
val = 3
new_length = remove_element(nums, val)
print(f"新长度: {new_length}")
print("新数组:", nums[:new_length])

特性说明：

Python列表是动态数组，可自动调整大小
通过切片nums[:new_length]获取新数组
无需显式处理内存管理

Go实现

package main

import "fmt"

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast] // 原地修改
            slow++
        }
    }
    return slow
}

func main() {
    nums := []int{3, 2, 2, 3}
    val := 3
    newLength := removeElement(nums, val)
    fmt.Printf("新长度: %d\n", newLength)
    fmt.Println("新数组:", nums[:newLength])
}

特性说明：

Go的切片是引用类型，修改会直接影响原数组
nums[:newLength]获取新数组的视图
切片的动态特性简化了内存管理

五、完整案例

多语言对比案例

输入：

数组：[3, 2, 2, 3, 4, 5, 3]
目标值：3

预期输出：

新长度：4
新数组：[2, 2, 4, 5]

Java实现

public class RemoveElementDemo {
    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3, 4, 5, 3};
        int val = 3;
        int newLength = removeElement(nums, val);
        System.out.println("新长度: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

Python3实现

def remove_element(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

nums = [3, 2, 2, 3, 4, 5, 3]
val = 3
new_length = remove_element(nums, val)
print(f"新长度: {new_length}")
print("新数组:", nums[:new_length])

C实现

#include <stdio.h>

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

int main() {
    int nums[] = {3, 2, 2, 3, 4, 5, 3};
    int val = 3;
    int newLength = removeElement(nums, 7, val);
    printf("新长度: %d\n", newLength);
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

六、源码解析

以Java实现为例，逐行分析关键代码：

int slow = 0;：初始化慢指针，指向当前已处理的最后一个有效元素的下一个位置
for (int fast = 0; fast < nums.length; fast++)：快指针遍历整个数组
if (nums[fast] != val)：判断当前元素是否需要保留
nums[slow++] = nums[fast];：将有效元素复制到慢指针位置，并递增慢指针
return slow;：返回慢指针位置作为新长度

该实现的关键在于：

通过一次遍历完成元素筛选
原地修改保证空间复杂度O(1)
顺序处理确保内存连续性

七、进阶使用

1. 高效内存管理

在C语言中，可以结合realloc实现动态数组调整：

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

int removeElement(int* nums, int* size, int val) {
    int slow = 0;
    int new_size = *size;
    for (int fast = 0; fast < *size; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    int* new_nums = (int*)realloc(nums, slow * sizeof(int));
    if (new_nums) {
        *size = slow;
        return slow;
    }
    return -1;
}

2. 并发场景下的应用

在Go语言中，可以结合goroutine实现并发处理：

func removeElementConcurrent(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

func main() {
    nums := []int{3, 2, 2, 3, 4, 5, 3}
    val := 3
    newLength := removeElementConcurrent(nums, val)
    fmt.Printf("新长度: %d\n", newLength)
    fmt.Println("新数组:", nums[:newLength])
}

3. 异常处理增强

在Java中添加边界检查：

public static int removeElement(int[] nums, int val) {
    if (nums == null) {
        return 0;
    }
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

八、性能与工程实践

1. 性能分析

时间复杂度：O(n)（一次遍历）
空间复杂度：O(1)（原地修改）
优化方向：避免不必要的内存拷贝

2. 高效实现技巧

避免使用额外的数组创建
利用语言特性（如Python的切片）
在C语言中使用realloc动态调整内存

3. 安全考量

避免数组越界访问
在C/C++中注意内存释放
在Go中注意切片的容量限制

4. 异常处理

检查输入参数有效性
处理空数组情况
在多线程环境中处理并发访问

九、常见问题与踩坑

1. 常见错误

错误示例：

public static int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++; // 错误：先递增再赋值
        }
    }
    return slow;
}

问题分析：

指针递增顺序错误导致元素覆盖
造成部分元素丢失

改进方案：

nums[slow++] = nums[fast]; // 先赋值再递增

2. 常见陷阱

陷阱1：忽略数组长度变化

int newLength = removeElement(nums, 7, val);
printf("新长度: %d\n", newLength);
for (int i = 0; i < newLength; i++) {
    printf("%d ", nums[i]);
}

陷阱2：在Python中修改列表长度

nums = [3, 2, 2, 3]
val = 3
slow = 0
for fast in range(len(nums)):
    if nums[fast] != val:
        nums[slow] = nums[fast]
        slow += 1
print("新长度:", slow)
print("新数组:", nums[:slow]) # 正确切片

十、最佳实践

1. 推荐方案

使用双指针法实现O(n)时间复杂度
原地修改保证空间效率
避免创建额外数组
在多语言中注意内存管理差异

2. 实际应用场景

数据清洗：过滤无效元素
数组压缩：减少内存占用
缓存管理：动态调整数据结构

3. 不推荐使用场景

不需要原地修改时
数据结构允许使用额外空间时
需要保持元素顺序时（需额外处理）

4. 优化建议

在C语言中使用realloc动态调整内存
在Go中利用切片特性
在Python中利用列表切片操作

十一、总结

LeetCode 27题"移除元素"作为经典算法问题，其核心在于理解双指针法的原理和应用。通过不同语言的实现，我们可以看到：

Java/C需要显式管理内存
Python/Go利用语言特性简化实现
无论哪种语言，都遵循相同的算法逻辑

在实际开发中，该算法适用于需要高效内存管理的场景，但在不需要原地修改或需要保持元素顺序时，应选择更适合的方案。通过深入理解算法原理，我们可以更好地应对各种数据处理场景，提升代码质量和运行效率。

- 阅读更多 -

leetcode 题解 628.三个数的最大乘积（Typescript）

System

2024-08-07

所有,typescript

leetcode 题解 628.三个数的最大乘积（Typescript）

一、背景与问题

LeetCode 628 题要求我们找出一个数组中三个数的最大乘积。这个问题看似简单，但其背后涉及多个数学逻辑和边界条件的处理，是算法面试中常见的考察点。

在实际开发中，类似的问题可能出现在数据处理、统计分析、金融计算等场景。例如：

股票交易中计算连续三天的最高收益
传感器数据中寻找最大能量值
高频交易系统中分析历史数据的极值

问题的核心在于：如何在保证时间复杂度的前提下，准确处理所有可能的数学组合。

二、基本原理

1. 数学逻辑分析

三个数的乘积最大值可能出现在以下两种情况：

三个最大正数的乘积（例如：[1, 2, 3]）
两个最小负数和一个最大正数的乘积（例如：[-5, -4, 3]）

2. 数组边界条件

数组长度必须≥3（题目保证）
需要处理全为负数的情况（如[-3, -2, -1]）
需要处理零值的情况（如[0, 0, 0]）

3. 算法选择

常见的解法有两种：

排序法：先排序再比较两种情况
遍历法：一次遍历同时记录最大值和最小值

三、环境准备

1. 开发环境

TypeScript 4.9+
Node.js 18+
VS Code 或任何支持TS的编辑器

2. 依赖安装（无外部依赖）

npm init -y
npm install typescript --save-dev
npx tsc --init

四、核心实现

1. 排序法实现（简洁但效率较低）

function maximumProduct(nums: number[]): number {
    if (nums.length < 3) return 0;
    nums.sort((a, b) => a - b);
    const n = nums.length;
    return Math.max(
        nums[n-1] * nums[n-2] * nums[n-3], // 三个最大正数
        nums[0] * nums[1] * nums[n-1]      // 两个最小负数与最大正数
    );
}

关键代码解释：

nums.sort()：对数组进行升序排序
nums[n-1] * nums[n-2] * nums[n-3]：获取最后三个元素（最大正数）
nums[0] * nums[1] * nums[n-1]：获取前两个元素（最小负数）与最后元素（最大正数）

2. 遍历法实现（效率更高）

function maximumProduct(nums: number[]): number {
    if (nums.length < 3) return 0;
    
    let first = second = third = -Infinity;
    let min1 = min2 = Infinity;

    for (const num of nums) {
        // 更新前三个最大值
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second) {
            third = second;
            second = num;
        } else if (num > third) {
            third = num;
        }

        // 更新前两个最小值
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }

    return Math.max(
        first * second * third,         // 三个最大正数
        min1 * min2 * first             // 两个最小负数与最大正数
    );
}

关键代码解释：

first, second, third：记录最大的三个数
min1, min2：记录最小的两个数
通过单次遍历完成所有值的记录
时间复杂度为 O(n)，比排序法更高效

3. 特殊情况处理

function maximumProduct(nums: number[]): number {
    if (nums.length < 3) return 0;
    
    let first = second = third = -Infinity;
    let min1 = min2 = Infinity;

    for (const num of nums) {
        // 更新前三个最大值
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second) {
            third = second;
            second = num;
        } else if (num > third) {
            third = num;
        }

        // 更新前两个最小值
        if (num < min1) {
            min2 = min1;
            min1 = num;
        } else if (num < min2) {
            min2 = num;
        }
    }

    // 特殊情况处理：当数组长度为3时，直接返回结果
    if (nums.length === 3) {
        return first * second * third;
    }

    // 增加对全负数的处理
    if (min1 < 0 && min2 < 0 && first > 0) {
        return Math.max(first * second * third, min1 * min2 * first);
    }

    return Math.max(first * second * third, min1 * min2 * first);
}

五、完整案例

案例1：常规正数情况

输入：[1, 2, 3, 4, 5]
输出：60（5 * 4 * 3）

案例2：负数与正数混合

输入：[-10, -9, 1, 2, 3]
输出：90（-10 * -9 * 3）

案例3：全负数情况

输入：[-3, -2, -1]
输出：-6（-3 * -2 * -1）

案例4：包含零值

输入：[0, 0, 0, 1]
输出：0（0 * 0 * 1）

六、源码解析

1. 排序法源码分析

nums.sort((a, b) => a - b);

排序后数组按升序排列，最大值在末尾，最小值在开头
时间复杂度：O(n log n)

2. 遍历法源码分析

if (num > first) { ... }

通过比较更新最大值，确保 first >= second >= third
保持三个最大值的有序性

if (num < min1) { ... }

通过比较更新最小值，确保 min1 <= min2

七、进阶使用

1. 大数据量优化

对于超大规模数据（如10^6个元素），遍历法的O(n)复杂度比排序法的O(n log n)更优。

2. 并行计算

可使用Web Worker或Node.js的worker_threads模块进行并行处理，但需注意线程同步问题。

3. 空间优化

遍历法的空间复杂度为O(1)，而排序法需要额外O(n)空间（如原地排序）。

八、性能与工程实践

1. 性能优化

遍历法：时间复杂度O(n)，适合大数据量
排序法：时间复杂度O(n log n)，适合小数据量或需要排序的场景
空间优化：遍历法不占用额外空间，适合内存敏感场景

2. 异常处理

需要处理数组长度小于3的边界情况
需要处理全为负数的情况（如[-5, -4, -3]）

3. 安全风险

当输入数据包含非数字类型时，需增加类型校验
需要处理数组为空的异常情况

九、常见问题与踩坑

1. 忘记处理负数情况

错误代码：

return first * second * third;

问题：未考虑两个负数与正数的组合
修复：增加对两种情况的比较

2. 数组长度不足

错误代码：

nums.sort((a, b) => a - b);

问题：未处理数组长度小于3的情况
修复：增加边界判断

3. 错误处理逻辑

错误代码：

return Math.max(...);

问题：未考虑所有可能的数学组合
修复：明确比较所有可能的乘积组合

十、最佳实践

1. 推荐方案

常规场景：使用遍历法，时间复杂度O(n)，代码可读性强
需要排序的场景：使用排序法，代码简洁但效率较低

2. 应用场景

数据处理：适合处理大数据集
实时计算：需要快速响应的场景
资源受限：内存或CPU资源有限的环境

3. 避免使用场景

小数据集：排序法的简洁性优势可能不明显
需要排序的场景：遍历法无法满足排序需求
代码可读性要求不高：遍历法的逻辑较复杂

十一、总结

LeetCode 628 题的解法涉及多个数学逻辑和边界条件的处理，其核心在于理解三种可能的乘积组合：

三个最大正数
两个最小负数与一个最大正数
全为负数或零的情况

通过对比排序法和遍历法，我们可以根据具体场景选择合适的实现方式。遍历法在时间和空间效率上更具优势，但需要更复杂的逻辑处理。在实际开发中，需要根据数据规模、性能需求和代码可维护性综合考虑，选择最合适的方案。

本题的解法可扩展到更复杂的场景，如寻找最大/最小的k个数的乘积，其核心思想依然适用：通过数学分析确定关键条件，结合算法优化实现高效计算。

System

2024-08-06

所有,golang

[Go] LeetCode 24.两两交换链表中的节点 19.删除链表的倒数第N个节点面试题02.07.链表相交 142.环形链表 II

一、背景与问题

链表作为基础数据结构，在软件开发中广泛应用。这四个LeetCode题目分别涉及链表的常见操作：节点交换、倒数节点删除、链表相交查找、环形链表入口点定位。这些问题在实际开发中常出现在以下场景：

数据结构设计：如构建链表缓存、链表队列等
算法实现：如图的邻接表表示、树的序列化等
系统底层开发：如内存管理、资源回收机制
并发控制：如链表节点的原子操作

这些题目共同的特点是：需要对链表的指针操作有深刻理解，同时需要考虑边界条件、空指针、异常处理等场景。本文将深入分析这四个题目的核心原理，探讨其在实际开发中的应用价值和注意事项。

二、基本原理

1. 链表节点交换（LeetCode 24）

核心原理：通过指针的链式操作，逐个交换相邻节点。关键点在于保持链表的连续性，处理头节点的特殊情况。

2. 删除倒数第N个节点（LeetCode 19）

核心原理：利用快慢指针法，先让快指针移动N步，再同时移动快慢指针，最终慢指针指向要删除的节点。需要特别注意空链表和头节点删除的边界情况。

3. 链表相交（面试题02.07）

核心原理：通过哈希表存储节点，或者利用双指针法（先移动长链表指针到等长位置，再同时移动指针）来判断相交点。

4. 环形链表 II（LeetCode 142）

核心原理：使用快慢指针法，当快指针追上慢指针时，说明存在环。进一步通过数学推导找到环的入口点。

三、环境准备

package main

import (
    "fmt"
    "os"
)

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// 创建链表
func createList(nums []int) *ListNode {
    if len(nums) == 0 {
        return nil
    }
    head := &ListNode{Val: nums[0]}
    current := head
    for i := 1; i < len(nums); i++ {
        current.Next = &ListNode{Val: nums[i]}
        current = current.Next
    }
    return head
}

// 打印链表
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " -> ")
        head = head.Next
    }
    fmt.Println("nil")
}

四、核心实现

1. 两两交换链表中的节点（LeetCode 24）

// 两两交换链表中的节点
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{Val: 0, Next: head}
    current := dummyHead
    
    for current.Next != nil && current.Next.Next != nil {
        // 保存当前节点的下一个节点
        first := current.Next
        second := current.Next.Next
        
        // 交换指针
        current.Next = second
        first.Next = second.Next
        second.Next = first
        
        // 移动指针
        current = current.Next.Next
    }
    
    return dummyHead.Next
}

关键代码解释：

创建虚拟头节点dummyHead处理头节点特殊情况
使用双指针first和second保存待交换的两个节点
通过指针重定向完成交换操作
通过current指针移动完成遍历

2. 删除链表的倒数第N个节点（LeetCode 19）

// 删除链表的倒数第N个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyHead := &ListNode{Val: 0, Next: head}
    fast, slow := dummyHead, dummyHead
    
    // 快指针先走n步
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    
    // 快慢指针同时移动
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // 删除节点
    slow.Next = slow.Next.Next
    return dummyHead.Next
}

关键代码解释：

使用虚拟头节点处理头节点删除的特殊情况
快指针先走n步，确保慢指针最终指向要删除的节点
删除节点时需要调整指针链接

3. 链表相交（面试题02.07）

// 链表相交
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    // 计算链表长度
    lenA, lenB := 0, 0
    for current := headA; current != nil; current = current.Next {
        lenA++
    }
    for current := headB; current != nil; current = current.Next {
        lenB++
    }
    
    // 调整指针位置
    for lenA > lenB {
        headA = headA.Next
        lenA--
    }
    for lenB > lenA {
        headB = headB.Next
        lenB--
    }
    
    // 同步移动指针
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    return headA
}

关键代码解释：

通过遍历计算链表长度
通过调整指针位置使两个链表长度相等
同步移动指针直到找到相交点

五、完整案例

func main() {
    // 创建测试链表
    list1 := createList([]int{1, 2, 3, 4, 5})
    list2 := createList([]int{6, 1, 2, 3})
    
    // 链表相交测试
    list2.Next = list1.Next.Next // 让两个链表在节点3处相交
    
    fmt.Println("原始链表：")
    printList(list1)
    printList(list2)
    
    // 查找相交点
    intersectNode := getIntersectionNode(list1, list2)
    fmt.Printf("相交点：%v\n", intersectNode.Val)
    
    // 删除倒数第N个节点
    fmt.Println("删除倒数第2个节点后：")
    list1 = removeNthFromEnd(list1, 2)
    printList(list1)
    
    // 两两交换节点
    fmt.Println("交换后：")
    list1 = swapPairs(list1)
    printList(list1)
    
    // 环形链表测试
    list3 := createList([]int{1, 2, 3, 4, 5})
    list3.Next.Next.Next.Next.Next = list3.Next // 创建环
    
    fmt.Println("环形链表：")
    printList(list3)
    
    // 找到环入口点
    entryNode := detectCycle(list3)
    fmt.Printf("环入口点：%v\n", entryNode.Val)
}

六、源码解析

1. 环形链表II（LeetCode 142）

// 环形链表 II
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    // 快慢指针
    slow, fast := head, head
    
    // 找到快慢指针相遇点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    
    // 如果没有环
    if slow != fast {
        return nil
    }
    
    // 计算环的长度
    length := 0
    for slow.Next != fast {
        slow = slow.Next
        length++
    }
    
    // 移动指针找到入口点
    slow = slow.Next
    for i := 0; i < length; i++ {
        slow = slow.Next
    }
    
    return slow
}

关键代码解释：

快慢指针法寻找相遇点
计算环的长度时需要从相遇点开始遍历
通过数学推导找到入口点：slow = slow.Next后，让快指针走环的长度

七、进阶使用

在实际开发中，这些链表操作可以用于：

缓存系统：使用链表实现LRU缓存，通过删除倒数节点实现最近最少使用策略
资源管理：通过链表相交检测实现内存泄漏检测
并发控制：在锁机制中使用环形链表实现等待队列

优化方案

空间优化：所有解法都使用O(1)空间复杂度
时间优化：所有解法都使用O(n)时间复杂度
多线程安全：在链表操作时需要加锁，避免竞态条件

八、性能与工程实践

1. 性能分析

题目	时间复杂度	空间复杂度	优化点
24	O(n)	O(1)	无需额外空间
19	O(n)	O(1)	快慢指针法
02.07	O(n)	O(1)	双指针法
142	O(n)	O(1)	数学推导

2. 异常处理

链表为空时的处理
删除头节点时的处理
环形链表的边界条件处理

3. 安全风险

指针越界访问（如current.Next时未检查current是否为nil）
空指针解引用（如head.Next时未检查head是否为nil）
无限循环（如环形链表未正确处理）

九、常见问题与踩坑

1. 常见错误

错误示例：

// 错误的链表相交实现
func getIntersectionNodeWrong(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

错误原因：

没有处理链表长度不一致的情况
快慢指针法未正确实现

解决办法：

使用双指针法调整链表长度
在循环中处理指针移动

2. 常见坑点

坑点	解决方案
删除头节点时未处理虚拟头节点	使用虚拟头节点统一处理
环形链表未正确找到入口点	使用数学推导计算环长
指针操作时未检查空指针	增加nil判断
快慢指针未正确处理相遇条件	确保指针移动逻辑正确

十、最佳实践

使用虚拟头节点：统一处理头节点删除的特殊情况
使用快慢指针法：高效处理链表长度相关问题
边界条件检查：在操作指针前检查空指针
数学推导：在环形链表问题中使用数学公式计算入口点
代码注释：对关键指针操作添加详细注释
单元测试：为每个函数编写测试用例覆盖边界情况

十一、总结

这四个链表问题展示了Go语言在处理指针操作时的灵活性和效率。通过深入理解指针的链式操作原理，我们能够设计出高效的链表处理算法。在实际开发中，这些技术可以用于缓存系统、资源管理等场景，但需要注意处理边界条件、指针越界等问题。

需要特别注意的是：链表操作虽然在某些场景下效率较高，但在需要频繁随机访问或数据量较大的情况下，应考虑使用数组或更高效的数据结构。同时，多线程环境下需要特别注意指针的同步和安全问题。

这些算法的掌握不仅能帮助解决LeetCode题目，更能提升我们对底层数据结构的理解，为开发高性能系统打下坚实基础。

- 阅读更多 -