尧图网页设计 
LeetCode-Go 题解 118Pascals Triangle杨辉三角生成算法与 Go 实现剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 leetcode/0118.Pascals-Triangle/README.md 展开完整讲解 LeetCode 第 118 题「Pascals Triangle杨辉三角」的题目规则、生成思路与 Go 实现。通过本文你将掌握杨辉三角逐行递推的经典算法理解本仓库LeetCode-Go中generate函数的源码组织方式学会如何用go test验证题解并能顺带掌握其姊妹题 119 号「Pascals Triangle II」的空间优化技巧。题目生成杨辉三角的前 numRows 行给定一个非负整数numRows生成杨辉三角Pascals Triangle的前numRows行。杨辉三角的核心生成规则在杨辉三角中每个数字是它正上方两个数字之和。每一行的首尾元素恒为 1。示例Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]题目大意给定一个非负整数numRows生成杨辉三角的前numRows行。在杨辉三角中每个数是它左上方和右上方两个数的和。注意本题的numRows从 1 开始计数即第一行就是[1]。解题思路按生成规则逐行递推这是一道简单题核心思路只有一个按照杨辉三角的生成规则逐行构造。对第i行从 0 开始计数而言行首j 0处恒为 1行尾j i处恒为 1中间位置0 j i的元素等于上一行第i-1行的result[i-1][j-1]与result[i-1][j]之和。将这一规则循环应用numRows次即可自顶向下地构造出整个三角形。复杂度分析时间复杂度O(numRows²)。共需构造 numRows 行第 i 行有 i1 个元素总元素数为 n(n1)/2每个元素仅做一次常数时间的加法。空间复杂度O(numRows²)。需要保存整个三角形即全部 n(n1)/2 个元素结果数组本身即为空间主体。Go 源码实现逐行递推仓库中该题解的完整源码位于 leetcode/0118.Pascals-Triangle/118. Pascals Triangle.go与 关联文档 中的代码一致package leetcode func generate(numRows int) [][]int { result : [][]int{} for i : 0; i numRows; i { row : []int{} for j : 0; j i1; j { if j 0 || j i { row append(row, 1) } else if i 1 { row append(row, result[i-1][j-1]result[i-1][j]) } } result append(result, row) } return result }对这段源码做逐步拆解外层循环控制行号for i : 0; i numRows; i依次生成第 0 行到第numRows-1行。内层循环控制列号for j : 0; j i1; j表示第i行恰好有i1个元素。首尾置 1j 0 || j i时直接追加1这是每一行的边界条件。中间求和else if i 1分支中result[i-1][j-1] result[i-1][j]即每个数等于它上方两个数之和的直接翻译。注意这里用i 1而非i 1是安全的当i 1时内层j只能取 0 或 1都会命中首尾置 1 的分支根本不会进入求和分支因此不会出现越界访问result[0][-1]的问题。追加整行每行构造完成后通过result append(result, row)累积到最终结果。这段代码与文档保持一致任何对该题解的修改都应同步更新 文档 与源码保证文档即题解、题解即文档的仓库惯例。测试验证表驱动用例覆盖边界与常规输入仓库为每道题都配套了测试文件本题的测试位于 leetcode/0118.Pascals-Triangle/118. Pascals Triangle_test.go。测试采用典型的表驱动table-driven风格定义了两个结构体来组织参数与期望输出type para118 struct { numRows int } type ans118 struct { one [][]int }测试用例覆盖了三种具有代表性的输入输入 numRows期望输出2[[1], [1, 1]]5[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]10从[1]到[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]共 10 行完整结果其中numRows 2验证最小的非平凡输入两行即可覆盖首尾为 1与行间递推两条分支numRows 5与文档示例一致numRows 10则验证了第 10 行系数[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]对应二项式(ab)^9的展开系数。运行测试的方式如下仓库根目录的 gotest.sh 展示了覆盖率的收集方式# 运行单个用例 go test ./leetcode/0118.Pascals-Triangle/ -run Test_Problem118 -v # 或按仓库惯例对整个 leetcode 目录跑测试并生成覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...测试运行时会以【input】:... 【output】:...的格式打印每组用例的实际输出便于人工核对结果。仓库模块定义见 go.mod模块名为github.com/halfrost/LeetCode-GoGo 版本为 1.19。延伸思考119 号题如何把空间压缩到 O(k)杨辉三角还有一个经典姊妹题 119「Pascals Triangle II」给定从0开始计数的行索引rowIndex只返回第rowIndex行并要求仅使用 O(k) 的额外空间。相关题解同样位于仓库中见 leetcode/0119.Pascals-Triangle-II/README.md 与 119. Pascals Triangle II.go。之所以能做到 O(k) 空间是因为杨辉三角的第 n 行恰好是二项式(ab)^n的展开系数。由组合数知识$$C_{n}^{m} \frac{n!}{m!(n-m)!}, \quad C_{n}^{m-1} \frac{n!}{(m-1)!(n-m1)!}$$两者相除可得相邻两项之间的递推关系$$C_{n}^{m} C_{n}^{m-1} \times \frac{n-m1}{m}$$利用该递推式只需一个长度为rowIndex1的数组即可从C_n^0 1依次推出整行func getRow(rowIndex int) []int { row : make([]int, rowIndex1) row[0] 1 for i : 1; i rowIndex; i { row[i] row[i-1] * (rowIndex - i 1) / i } return row }注意题目约束0 rowIndex 33中间乘积与结果均可用 Go 的int安全承载。118 题关注生成整个三角形119 题关注单行 空间优化两题形成很好的递推实现与数学递推的对照学习材料。小结本题作为数组/动态规划入门题核心价值在于两点一是理解每个数是它上方两数之和这一可递推的生成规则二是体会如何用二维切片[][]int组织行与列的累积结果。对照仓库源码 118. Pascals Triangle.go、测试 118. Pascals Triangle_test.go 与文档 README.md即可完成读题 → 看实现 → 跑测试的完整学习闭环进一步研究 119 号题还能掌握组合数递推公式带来的 O(k) 空间优化思路。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 118：Pascal‘s Triangle（杨辉三角）生成算法与 Go 实现剖析
LeetCode-Go 题解 118Pascals Triangle杨辉三角生成算法与 Go 实现剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 leetcode/0118.Pascals-Triangle/README.md 展开完整讲解 LeetCode 第 118 题「Pascals Triangle杨辉三角」的题目规则、生成思路与 Go 实现。通过本文你将掌握杨辉三角逐行递推的经典算法理解本仓库LeetCode-Go中generate函数的源码组织方式学会如何用go test验证题解并能顺带掌握其姊妹题 119 号「Pascals Triangle II」的空间优化技巧。题目生成杨辉三角的前 numRows 行给定一个非负整数numRows生成杨辉三角Pascals Triangle的前numRows行。杨辉三角的核心生成规则在杨辉三角中每个数字是它正上方两个数字之和。每一行的首尾元素恒为 1。示例Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]题目大意给定一个非负整数numRows生成杨辉三角的前numRows行。在杨辉三角中每个数是它左上方和右上方两个数的和。注意本题的numRows从 1 开始计数即第一行就是[1]。解题思路按生成规则逐行递推这是一道简单题核心思路只有一个按照杨辉三角的生成规则逐行构造。对第i行从 0 开始计数而言行首j 0处恒为 1行尾j i处恒为 1中间位置0 j i的元素等于上一行第i-1行的result[i-1][j-1]与result[i-1][j]之和。将这一规则循环应用numRows次即可自顶向下地构造出整个三角形。复杂度分析时间复杂度O(numRows²)。共需构造 numRows 行第 i 行有 i1 个元素总元素数为 n(n1)/2每个元素仅做一次常数时间的加法。空间复杂度O(numRows²)。需要保存整个三角形即全部 n(n1)/2 个元素结果数组本身即为空间主体。Go 源码实现逐行递推仓库中该题解的完整源码位于 leetcode/0118.Pascals-Triangle/118. Pascals Triangle.go与 关联文档 中的代码一致package leetcode func generate(numRows int) [][]int { result : [][]int{} for i : 0; i numRows; i { row : []int{} for j : 0; j i1; j { if j 0 || j i { row append(row, 1) } else if i 1 { row append(row, result[i-1][j-1]result[i-1][j]) } } result append(result, row) } return result }对这段源码做逐步拆解外层循环控制行号for i : 0; i numRows; i依次生成第 0 行到第numRows-1行。内层循环控制列号for j : 0; j i1; j表示第i行恰好有i1个元素。首尾置 1j 0 || j i时直接追加1这是每一行的边界条件。中间求和else if i 1分支中result[i-1][j-1] result[i-1][j]即每个数等于它上方两个数之和的直接翻译。注意这里用i 1而非i 1是安全的当i 1时内层j只能取 0 或 1都会命中首尾置 1 的分支根本不会进入求和分支因此不会出现越界访问result[0][-1]的问题。追加整行每行构造完成后通过result append(result, row)累积到最终结果。这段代码与文档保持一致任何对该题解的修改都应同步更新 文档 与源码保证文档即题解、题解即文档的仓库惯例。测试验证表驱动用例覆盖边界与常规输入仓库为每道题都配套了测试文件本题的测试位于 leetcode/0118.Pascals-Triangle/118. Pascals Triangle_test.go。测试采用典型的表驱动table-driven风格定义了两个结构体来组织参数与期望输出type para118 struct { numRows int } type ans118 struct { one [][]int }测试用例覆盖了三种具有代表性的输入输入 numRows期望输出2[[1], [1, 1]]5[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]10从[1]到[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]共 10 行完整结果其中numRows 2验证最小的非平凡输入两行即可覆盖首尾为 1与行间递推两条分支numRows 5与文档示例一致numRows 10则验证了第 10 行系数[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]对应二项式(ab)^9的展开系数。运行测试的方式如下仓库根目录的 gotest.sh 展示了覆盖率的收集方式# 运行单个用例 go test ./leetcode/0118.Pascals-Triangle/ -run Test_Problem118 -v # 或按仓库惯例对整个 leetcode 目录跑测试并生成覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...测试运行时会以【input】:... 【output】:...的格式打印每组用例的实际输出便于人工核对结果。仓库模块定义见 go.mod模块名为github.com/halfrost/LeetCode-GoGo 版本为 1.19。延伸思考119 号题如何把空间压缩到 O(k)杨辉三角还有一个经典姊妹题 119「Pascals Triangle II」给定从0开始计数的行索引rowIndex只返回第rowIndex行并要求仅使用 O(k) 的额外空间。相关题解同样位于仓库中见 leetcode/0119.Pascals-Triangle-II/README.md 与 119. Pascals Triangle II.go。之所以能做到 O(k) 空间是因为杨辉三角的第 n 行恰好是二项式(ab)^n的展开系数。由组合数知识$$C_{n}^{m} \frac{n!}{m!(n-m)!}, \quad C_{n}^{m-1} \frac{n!}{(m-1)!(n-m1)!}$$两者相除可得相邻两项之间的递推关系$$C_{n}^{m} C_{n}^{m-1} \times \frac{n-m1}{m}$$利用该递推式只需一个长度为rowIndex1的数组即可从C_n^0 1依次推出整行func getRow(rowIndex int) []int { row : make([]int, rowIndex1) row[0] 1 for i : 1; i rowIndex; i { row[i] row[i-1] * (rowIndex - i 1) / i } return row }注意题目约束0 rowIndex 33中间乘积与结果均可用 Go 的int安全承载。118 题关注生成整个三角形119 题关注单行 空间优化两题形成很好的递推实现与数学递推的对照学习材料。小结本题作为数组/动态规划入门题核心价值在于两点一是理解每个数是它上方两数之和这一可递推的生成规则二是体会如何用二维切片[][]int组织行与列的累积结果。对照仓库源码 118. Pascals Triangle.go、测试 118. Pascals Triangle_test.go 与文档 README.md即可完成读题 → 看实现 → 跑测试的完整学习闭环进一步研究 119 号题还能掌握组合数递推公式带来的 O(k) 空间优化思路。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考