力扣119题 解题思路和步骤 C++代码实现,力扣题目有官方答案吗
本文针对力扣（LeetCode）第119题"杨辉三角II"进行深度解析，详细讲解组合数学与动态规划两种解题思路。通过递推公式推导、空间复杂度优化分析，以及C++代码实现示例，帮助读者掌握高效计算杨辉三角指定行的核心算法。文章包含时间空间复杂度对比、边界条件处理要点和代码调试技巧，适合算法初学者与面试备考者系统学习。
一、题目理解与数学建模
力扣119题要求返回杨辉三角的第k行（从0开始计数），其本质是求解组合数C(k,n)的集合。杨辉三角每个位置的数值满足C(n,m) = C(n,m-1)(n-m+1)/m的递推关系，这为优化算法提供了数学基础。理解这个组合数公式是解题的关键，它避免了重复计算阶乘带来的时间复杂度问题。
传统动态规划解法需要构建完整的杨辉三角结构，时间复杂度为O(k²)。但通过组合数递推公式，我们可以将时间复杂度优化到O(k)。这种优化思路体现了算法设计中数学建模的重要性，如何在问题特征与数学规律之间建立有效连接，是提高算法效率的核心。
二、组合数递推算法实现步骤
具体实现分为三个步骤：初始化结果数组、计算前半部分数值、镜像复制数值。创建长度为k+1的数组，初始值设为1。从索引1开始，使用prev = prev (rowIndex - i + 1)/i 的公式迭代计算，直至中间位置。对于奇数行需单独处理中间值。这个过程中需要注意整型除法的精度问题。计算C(4,2)时，按照公式应该是43/2=6，但若先进行乘法可能导致中间值溢出。在C++实现中，采用先乘后除的顺序，并通过long类型转换确保计算精度，这是保证算法正确性的关键细节。
三、空间复杂度优化与边界处理
案例演示：当k=5时，计算过程如下：
1.初始化数组[1,1,1,1,1,1]
2.索引1：1(5-1+1)/1 = 5 → [1,5,1,1,5,1]
3.索引2：5(5-2+1)/2 = 10 → [1,5,10,10,5,1]
最终输出结果为对称数组。这个案例验证了算法的正确性，同时展示了如何通过镜像复制减少计算量。边界条件处理需要特别注意k=0和k=1的情况。当k=0时直接返回[1]，当k=1时返回[1,1]。
四、C++代码实现与调试要点
vector getRow(int rowIndex) {
vector res(rowIndex+1,1);
for(int i=1; i<=rowIndex/2; ++i){
res[i] = (long)res[i-1](rowIndex-i+1)/i;
res[rowIndex-i] = res[i];
}
return res;
}
五、算法复杂度分析与应用场景
本算法时间复杂度严格为O(k)，空间复杂度O(1)（不考虑返回结果占用的空间）。相比动态规划解法，在k>30时效率提升显著。但当k较大时（k>33），组合数值可能超过int最大值（2147483647），这时需要使用long类型或特殊处理大数。
原创内容 转载请注明出处
