 空间解法详解)
LeetCode-Go 中的组合递推优化Pascals Triangle IILeetCode 119O(k) 空间解法详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 119 题的题解文档与配套源码讲解如何仅用 O(k) 额外空间返回杨辉三角Pascals Triangle的第 k 行。读完本文你将掌握从二项式组合数定义出发推导相邻项递推公式C(n,m) C(n,m-1) × (n-m1)/m的完整过程理解该公式在整数运算下的整除与溢出安全性并看到仓库中可运行的 Go 实现、测试用例与 100% 覆盖率的验证方式。题目描述与约束给定一个整数rowIndex返回杨辉三角的第rowIndex行行索引从0开始计数。在杨辉三角中每个数等于它上方两数之和。Follow up进阶要求能否将算法优化到只使用 O(k) 的额外空间仓库中的原始题解文档位于 0119.Pascals-Triangle-II.md其中给出的示例与约束如下示例输入输出Example 1rowIndex 3[1, 3, 3, 1]Example 2rowIndex 0[1]Example 3rowIndex 1[1, 1]约束条件0 rowIndex 33第 k 行恰好有 k1 个数且首尾元素恒为 1。约束上限 33 并非随意设定第 33 行的最大值C(33,16) 1166803110仍在 32 位有符号整数最大值2147483647之内因此用 Go 的int存储整行结果不会溢出。从组合数定义推导 O(k) 递推公式朴素做法是先构造整个三角形再取第 k 行这会用到 O(k²) 的空间和时间。仓库中前一道题 118Pascals Triangle的解法正是这种二维 DP逐行追加result[i-1][j-1] result[i-1][j]见 118. Pascals Triangle.go。但 119 题只要求一行且每个元素本质上就是二项式(ab)^n展开的系数C(n, m)。由组合数定义C(n, m) n! / (m! · (n-m)!)C(n, m-1) n! / ((m-1)! · (n-m1)!)两式相除即可得到同一行内相邻项的递推关系C(n, m) C(n, m-1) × (n - m 1) / m这就是文档中给出的核心结论只要知道前一项就能用一次乘法和一次除法推出当前项全程只需要一维数组空间复杂度从 O(k²) 优化到 O(k)。整数运算下的两个关键点整除无误差。由恒等式C(n,m-1) × (n-m1) m × C(n,m)可知乘积必然能被m整除先乘后除不会产生舍入。因此在 Go 中可以直接写row[i-1] * (rowIndex-i1) / i无需浮点数或大数库。中间乘积不溢出。中间量C(n,m-1) × (n-m1) m × C(n,m)最坏情形约为33 × 1166803110 ≈ 3.85×10^10超过了 32 位整数范围。Go 的int在 64 位平台上是 64 位类型该中间量可安全容纳这也说明此实现适用前提是 64 位平台这也是当前主流环境。Go 实现逐行注释仓库中的完整实现位于 119. Pascals Triangle II.go与题解文档中的代码完全一致package leetcode func getRow(rowIndex int) []int { row : make([]int, rowIndex1) // 第 rowIndex 行恰好有 rowIndex1 个元素 row[0] 1 // 行首恒为 1 for i : 1; i rowIndex; i { // 递推公式 C(n,i) C(n,i-1) × (n-i1) / i row[i] row[i-1] * (rowIndex - i 1) / i } return row }几个实现细节值得注意make([]int, rowIndex1)一次性预分配整行避免append的多次扩容这也正好对应 O(k) 空间上限循环从i 1开始因为row[0]已初始化为 1且递推式依赖row[i-1]rowIndex 0时循环不执行直接返回[1]与 Example 2 一致。思路对比。除组合数递推外另一类常见的 O(k) 空间做法是单数组从右向左倒序 DP倒序更新row[j] row[j] row[j-1]时row[j-1]尚未被本轮覆盖仍保存上一行的值。仓库源码选择了更直接、只需乘除的组合递推方案没有采用倒序 DP。测试用例与覆盖率验证LeetCode-Go 仓库的核心承诺是 100% 测试覆盖率119 题同样遵循这一规范。测试文件 119. Pascals Triangle II_test.go 采用表驱动结构type para119 struct { rowIndex int } type ans119 struct { one []int } func Test_Problem119(t *testing.T) { qs : []question119{ {para119{3}, ans119{[]int{1, 3, 3, 1}}}, // 覆盖 Example 1主循环路径 {para119{0}, ans119{[]int{1}}}, // 覆盖 Example 2循环空转边界 } // ... 遍历 qs 并调用 getRow 打印输入输出 }这两个用例的组合具有针对性rowIndex 3使for循环体至少执行一次验证递推式rowIndex 0让循环完全空转验证边界初始化逻辑。仓库根目录的 coverage.txt 中可以查到该文件全部三个可执行块的命中记录最后两列为语句数与执行次数均大于 0与仓库 README 宣称的 100% 覆盖率一致。若要本地复现仓库提供的 gotest.sh 脚本执行的命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以单独验证本题目录go test ./leetcode/0119.Pascals-Triangle-II/测试会打印【input】:{3} 【output】:[1 3 3 1]之类的对照输出便于人工核对。小结119 题的本质是把生成整行转化为沿组合数递推C(n,m) C(n,m-1) × (n-m1)/m逐位推导空间从朴素二维 DP 的 O(k²) 降到 O(k)实现上一次性预分配rowIndex1长度数组利用乘积恒可整除的特性直接整数乘除约束rowIndex 33保证了最终结果不超出 32 位整数中间乘积则依赖 64 位int容纳仓库中 leetcode/0119.Pascals-Triangle-II/ 目录下的实现、测试与覆盖率产物构成完整的可验证闭环读题看 英文题解运行go test即可复现全部断言。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
