🧩 攻克 LeetCode 困难题：7 道复杂题解深度剖析 🔗

攻克 LeetCode 困难（Hard）题目常常让人感觉像撞上了一堵南墙。然而，如果将它们拆解为易于消化的模式——例如动态规划、回溯算法和图论——它们就会变得平易近人得多。

在这篇文章中，我将分享我用 Go 语言解决过的 7 道最有趣的 LeetCode 困难题目。为了让这份指南尽可能实用，我提炼了解析内容，重点聚焦于核心直觉与复杂度分析，让你更容易理解从题目描述到可执行代码之间的跨越。

📑 目录 🔗

🔢 1. 60. 排列序列 (Permutation Sequence) 🔗

❓ 题目描述 🔗

给定 $n$ 和 $k$ ，返回从 $1$ 到 $n$ 的数字的第 $k$ 个排列序列。例如，当 $n = 3$ 时，所有排列为："123", "132", "213", "231", "312", "321"。如果 $k = 3$ ，则答案为 "213"。

💡 核心直觉 🔗

与其生成所有排列（那样太慢了），不如采用利用阶乘的数学方法。

对于 $n$ 个数字，总共有 $n!$ 种排列。如果我们固定第一个数字，剩下的数字就有 $(n-1)!$ 种排列。我们可以通过计算第 $k$ 个排列落在哪个大小为 $(n-1)!$ 的排列块中，来确定第一个数字。在已排序的可用数字列表中，下一个数字的索引就是 $(k-1) / (n-1)!$ 。选定一个数字后，我们将 $k$ 更新为余数 $k \bmod (n-1)!$ 并递归处理。

⏱️ 复杂度 🔗

时间： $O(N^2)$ ，因为从切片中删除一个元素需要 $O(N)$ 时间，而我们要执行 $N$ 次。
空间： $O(N)$ ，用于递归栈和数字数组。

💻 Go 题解 🔗

import "fmt"

func getPermutation(n int, k int) string {
	factorial := 1
	digits := []int{}

	// 计算阶乘并填充数字切片
	for i := 1; i <= n; i++ {
		factorial *= i
		digits = append(digits, i)
	}

	return solvePermutation(n-1, k-1, factorial/n, digits)
}

func solvePermutation(n, k, factorial int, digits []int) string {
	// 找出 'k' 落在哪个排列块中
	index := k / factorial
	res := fmt.Sprintf("%d", digits[index])

	if n <= 0 {
		return res
	}

	// 更新下一层的 k：k % factorial
	// 更新下一层的 factorial：factorial / n
	// 从切片中移除已选中的数字
	nextK := k % factorial
	nextFactorial := factorial / n
	remainingDigits := append(digits[:index], digits[index+1:]...)

	res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
	return res
}

🔍 2. 10. 正则表达式匹配 (Regular Expression Matching) 🔗

❓ 题目描述 🔗

实现支持 .（匹配任意单个字符）和 *（匹配零个或多个前面的那一个元素）的正则表达式匹配。匹配必须覆盖整个输入字符串。

💡 核心直觉 🔗

这是一道经典的动态规划问题。我们可以使用记忆化搜索（Memoization）来避免重复计算。

对于字符串 s 和模式 p 的任意字符位置组合，如果模式中的下一个字符是 *，我们有两个选择：

跳过它： 将前一个元素匹配零次。
继续匹配： 如果当前字符匹配，则消耗掉 s 中的一个字符，但继续停留在 p 中的 * 上，以便后续可能匹配更多字符。

⏱️ 复杂度 🔗

时间： $O(S \times P)$ ，其中 $S$ 和 $P$ 分别是字符串和模式的长度。
空间： $O(S \times P)$ ，用于二维记忆化表。

💻 Go 题解 🔗

func isMatch(s string, p string) bool {
	sn, pn := len(s), len(p)
	memo := make([][]int, sn+1)
	for i := range memo {
		memo[i] = make([]int, pn+1)
	}
	return solveRegex(s, p, sn, pn, 0, 0, memo)
}

func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
	if memo[si][pi] == 1 { return false }
	if memo[si][pi] == 2 { return true }

	res := false
	if si == sn && pi == pn {
		res = true
	} else if pi+1 < pn && p[pi+1] == '*' {
		// 选项 A：匹配零次
		if solveRegex(s, p, sn, pn, si, pi+2, memo) {
			res = true
		// 选项 B：匹配一次或多次（如果当前字符匹配）
		} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
			res = true
		}
	} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
		// 普通字符匹配
		res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
	}

	if res {
		memo[si][pi] = 2
	} else {
		memo[si][pi] = 1
	}
	return res
}

🌳 3. 124. 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) 🔗

❓ 题目描述 🔗

给定一个非空二叉树，找出其最大路径和。一条路径可以沿着父子连接向上或向下延伸，但不必经过根节点。

💡 核心直觉 🔗

我们使用深度优先搜索（DFS）。在每个节点处，我们评估两种类型的路径：

可扩展路径（fromRoot）： 从当前节点出发并沿着其某一个分支向下延伸的最大路径。父节点可以使用这条路径。
不可扩展路径（other）： 完全包含在当前子树内部的最大路径（例如，从左子节点向上经过当前节点，再向下延伸到右子节点）。这条路径是“闭合”的，无法继续向上延伸给父节点。

我们的全局最大值将是所找到的所有“不可扩展”路径中的最大值，或者是根节点的可扩展路径。

⏱️ 复杂度 🔗

时间： $O(N)$ ，因为我们恰好访问每个节点一次。
空间： $O(H)$ ，其中 $H$ 是树的高度（递归栈开销）。

💻 Go 题解 🔗

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	fromRoot, other := solveTree(root)
	if fromRoot > other {
		return fromRoot
	}
	return other
}

func solveTree(root *TreeNode) (int, int) {
	if root == nil {
		return math.MinInt, math.MinInt
	}

	left, otherLeft := solveTree(root.Left)
	right, otherRight := solveTree(root.Right)

	// 可扩展路径（只能选择一个分支，或者在当前节点处停止）
	currentFromRoot := max([]int{
		root.Val,
		sum([]int{root.Val, left}),
		sum([]int{root.Val, right}),
	})

	// 闭合路径（可以跨越当前节点拱起，或者完全位于某个子树内部）
	currentOther := max([]int{
		left, right, otherLeft, otherRight,
		sum([]int{root.Val, left, right}),
	})

	return currentFromRoot, currentOther
}

func max(s []int) int {
	res := math.MinInt
	for _, v := range s {
		if v > res { res = v }
	}
	return res
}

func sum(s []int) int {
	res := 0
	for _, v := range s {
		if v == math.MinInt { return math.MinInt }
		res += v
	}
	return res
}

🧮 4. 37. 解数独 (Sudoku Solver) 🔗

❓ 题目描述 🔗

编写一个程序来解一个 9x9 的数独谜题。你必须满足标准数独规则（行、列以及 3x3 宫格内数字不重复）。

💡 核心直觉 🔗

这需要用到回溯算法。为了提高效率并避免在 LeetCode 上出现超时（TLE）错误，我们使用一种启发式策略来优化搜索：始终优先尝试填充合法候选数字最少的空格。我们使用布尔数组来瞬间检查某个数字在某行、某列或某个 3x3 宫格中是否可用。

⏱️ 复杂度 🔗

时间： $O(9^M)$ ，其中 $M$ 是空格的数量，但在实际运行中由于启发式策略而得到了大幅剪枝。
空间： $O(1)$ ，因为棋盘始终是 9x9，且我们的布尔数组大小固定。

💻 Go 题解 🔗

func solveSudoku(board [][]byte) {
	var rows, cols [9][9]bool
	var boxes [3][3][9]bool

	// 初始化状态
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				idx := board[i][j] - '1'
				rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
			}
		}
	}
	backtrackSudoku(board, &rows, &cols, &boxes)
}

func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
	bestI, bestJ := -1, -1
	minOptions := 10 // 初始值设为大于最大可能候选项数（9）

	// 启发式策略：找出合法候选项最少的空格
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				options := 0
				for val := 0; val < 9; val++ {
					if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
						options++
					}
				}
				if options < minOptions {
					minOptions = options
					bestI, bestJ = i, j
				}
			}
		}
	}

	// 基准情况：没有剩余空格了
	if bestI == -1 { return true }

	// 尝试在选定的最优空格中填入合法数字
	for val := 0; val < 9; val++ {
		if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
			board[bestI][bestJ] = byte(val + '1')
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true

			if backtrackSudoku(board, rows, cols, boxes) {
				return true
			}

			// 回溯
			board[bestI][bestJ] = '.'
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
		}
	}
	return false
}

🎓 5. 1494. 并行课程 II (Parallel Courses II) 🔗

❓ 题目描述 🔗

给你一个整数 $n$ ，表示有 $n$ 门课程，编号从 $1$ 到 $n$ 。同时给你一个数组 relations，其中 relations[i] = [prevCourse, nextCourse] 表示先修课程关系。在一个学期内，你最多可以修读 $k$ 门课程。返回修完所有课程所需的最少学期数。

💡 核心直觉 🔗

因为 $n$ 很小（ $n \leq 15$ ），我们可以使用广度优先搜索（BFS）结合状态压缩（Bitmask）。位掩码（bitmask）表示我们已经修完的课程状态。在每个学期中，我们找出所有当前可修的课程（即先修课已全部完成的课程）。如果可修课程数量超过 $k$ ，我们必须通过子集枚举遍历所有大小为 $k$ 的可能组合。我们使用一个已访问集合来避免重复访问相同的组合状态。

⏱️ 复杂度 🔗

时间： 最坏情况下为 $O(3^N)$ ，因为我们要遍历可用课程的子集掩码。
空间： $O(2^N)$ ，用于存储已访问状态和 BFS 队列。

💻 Go 题解 🔗

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	// prerequisites[i] 是一个位掩码，表示在修读课程 i 之前必须先修完的课程
	prerequisites := make([]int, n)
	for _, relation := range relations {
		prevCourse := relation[0] - 1
		nextCourse := relation[1] - 1
		prerequisites[nextCourse] |= 1 << prevCourse
	}

	// states 和 costs 充当 BFS 队列
	states := []int{0}
	costs := []int{0}
	added := map[int]bool{0: true}

	for cur := 0; ; cur++ {
		state := states[cur]
		cost := costs[cur]

		// 基准情况：所有课程都已修完
		if state == (1<<n)-1 {
			return cost
		}

		// 找出本学期所有可以修读的课程
		courses := []int{}
		next := state
		for course := 0; course < n; course++ {
			bit := 1 << course
			if (state&bit) == 0 && (prerequisites[course]|state) == state {
				courses = append(courses, course)
				next |= bit
			}
		}

		add := func(next int) {
			if added[next] {
				return
			}
			added[next] = true
			states = append(states, next)
			costs = append(costs, cost+1)
		}

		// 如果本学期能修完所有可修课程，直接全部修读
		if len(courses) <= k {
			add(next)
			continue
		}

		// 否则，探索所有大小为 k 的组合
		var addStates func(next, k, from int)
		addStates = func(next, k, from int) {
			if k == 0 {
				add(next)
				return
			}
			for i := from; i < len(courses); i++ {
				addStates(next|(1<<courses[i]), k-1, i+1)
			}
		}
		addStates(state, k, 0)
	}
}

📐 6. 363. 矩形区域不超过 K 的最大数值和 (Max Sum of Rectangle No Larger Than K) 🔗

❓ 题目描述 🔗

给你一个 $m \times n$ 的矩阵和一个整数 $k$ ，找出并返回矩阵内部矩形区域的不超过 $k$ 的最大数值和。

💡 核心直觉 🔗

我们可以通过固定左右列边界，将二维矩阵压缩为一维数组。一旦我们得到了表示这两列之间各行累加和的一维数组，问题就简化为寻找和 $\leq k$ 的最大子数组。通过维护一个有序的前缀和列表（使用平衡二叉搜索树或简单的有序数组插入），我们可以高效查询满足 current_prefix - past_prefix <= k 的最小前缀和，或者预先计算二维前缀和表，以 $O(1)$ 的时间复杂度查询任意子矩形。

⏱️ 复杂度 🔗

时间： 使用二维前缀和时为 $O(R^2 \times C^2)$ （若使用有序一维前缀和则为 $O(C^2 \times R \log R)$ ，其中 $C$ 为列数， $R$ 为行数）。
空间： 二维前缀和矩阵需要 $O(R \times C)$ （或一维压缩行和需要 $O(R)$ ）。

💻 Go 题解 🔗

import "math"

func maxSumSubmatrix(matrix [][]int, k int) int {
	n := len(matrix)
	m := len(matrix[0])
	res := math.MinInt
	sums := make([][]int, n)
	for i := 0; i < n; i++ {
		sums[i] = make([]int, m)
	}

	// 预计算二维前缀和
	sums[0][0] = matrix[0][0]
	for i := 1; i < n; i++ {
		sums[i][0] = matrix[i][0] + sums[i-1][0]
	}
	for j := 1; j < m; j++ {
		sums[0][j] = matrix[0][j] + sums[0][j-1]
	}
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
		}
	}

	// 使用容斥原理评估所有可能的子矩形
	for starti := 0; starti < n; starti++ {
		for startj := 0; startj < m; startj++ {
			for endi := starti; endi < n; endi++ {
				for endj := startj; endj < m; endj++ {
					sum := sums[endi][endj]
					if starti > 0 {
						sum -= sums[starti-1][endj]
					}
					if startj > 0 {
						sum -= sums[endi][startj-1]
					}
					if starti > 0 && startj > 0 {
						sum += sums[starti-1][startj-1]
					}
					if sum <= k && sum > res {
						res = sum
					}
				}
			}
		}
	}
	return res
}

🔗 7. 685. 冗余连接 II (Redundant Connection II) 🔗

❓ 题目描述 🔗

在一个有向图中，除了根节点没有父节点外，每个节点都恰好有一个父节点。现在额外添加了一条有向边。请找出可以删除的那条边，使得剩余的图是一棵合法的有根树。如果有多个答案，返回在输入中最后出现的那条边。

💡 核心直觉 🔗

因为这是一个有向图，额外添加的边会导致以下两种问题之一（或两者兼有）：

某个节点有两个父节点。
形成了一个有向环。

我们首先扫描图中是否有任何节点拥有两个父节点。如果有，冗余边必定是指向该节点的两条边之一。否则，多出来的边一定构成了有向环。我们可以按输入逆序测试候选边，并通过 DFS（或并查集）验证：删除候选边后，是否能留下一棵从根节点出发可以无环到达所有 $N$ 个节点的合法有根树。

⏱️ 复杂度 🔗

时间： 使用 DFS 验证时为 $O(N^2)$ （若使用并查集则为 $O(N \times \alpha(N))$ ，其中 $\alpha$ 为反阿克曼函数）。
空间： $O(N)$ ，用于邻接映射表和已访问集合。

💻 Go 题解 🔗

func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	parents := map[int][]int{}
	outs := map[int][]int{}
	for _, edge := range edges {
		src := edge[0] - 1
		dst := edge[1] - 1
		parents[dst] = append(parents[dst], src)
		outs[src] = append(outs[src], dst)
	}

	roots := map[int]bool{}
	bad := -1
	for i := 0; i < n; i++ {
		if len(parents[i]) == 0 {
			roots[i] = true
		}
		if len(parents[i]) > 1 {
			bad = i
		}
	}

	if len(roots) == 0 {
		for i := 0; i < n; i++ {
			if check(n, outs, i, -1, -1, map[int]bool{}) {
				roots[i] = true
			}
		}
	}

	if len(roots) > 1 {
		for i := len(edges) - 1; i >= 0; i-- {
			edge := edges[i]
			src := edge[0] - 1
			dst := edge[1] - 1
			if roots[dst] {
				return []int{src + 1, dst + 1}
			}
		}
	}

	for root := range roots {
		if len(parents[root]) > 0 {
			return []int{parents[root][0] + 1, root + 1}
		}
		for from := len(parents[bad]) - 1; from >= 0; from-- {
			if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
				return []int{parents[bad][from] + 1, bad + 1}
			}
		}
	}
	return []int{-1, -1}
}

func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
	if visited[from] {
		return false
	}
	visited[from] = true
	if len(visited) == n {
		return true
	}
	for _, to := range outs[from] {
		if from == badfrom && to == badto {
			continue
		}
		if check(n, outs, to, badfrom, badto, visited) {
			return true
		}
	}
	return false
}

喜欢这篇解析吗？LeetCode 困难题目需要耐心，但研究其背后的底层模式会让解题过程变得可复制。继续构建，继续练习，祝你面试顺利！

📚 免费下载我的电子书 🔗

获取《卡乌埃的生活方式》精选离线版——一份全面优化 🍏 健康、💰 财富、❤️ 爱与 🧘 意义的实践指南。

📬 订阅邮件通讯 🔗

当我发布关于美好生活的新随笔、读书笔记和实践指南时接收通知。绝无垃圾邮件——可随时退订。

💬 评论与讨论 🔗

有任何问题、见解或建议吗？欢迎在下方分享您的想法。评论功能由 GitHub Discussions 驱动（无广告、无垃圾信息）——点击下方的使用 GitHub 登录即可发表评论或互动（注册免费 GitHub 账号不到一分钟即可完成）。

免责声明：本站所有内容仅供信息参考与教育用途，不构成任何医疗、心理、财务、投资、税务或法律建议。此处呈现的观点、整理与见解仅代表我个人，不代表我雇主的立场。书籍、演讲及文章摘要均为独立的教育性评论，其知识产权归原作者所有。本站可能使用 AI 工具辅助编辑、排版与归纳；尽管我们竭力确保准确无误，但仍可能存在疏漏。隐私政策：本站使用第三方服务提供可选的邮件通讯订阅（follow.it）、评论（giscus / GitHub Discussions）以及嵌入媒体（YouTube），这些服务可能会依据各自的隐私政策处理访客的 IP 地址和 Cookie。