当前位置:首页 > 力扣 > 力扣119题:从O(n²)到O(2n):杨辉三角高效空间优化

力扣119题:从O(n²)到O(2n):杨辉三角高效空间优化

2个月前 (05-18)

力扣119题:从O(n²)到O(2n):杨辉三角高效空间优化 杨辉三角形 C++ 算法 力扣 滚动数组 数组 第1张


题目重解:

给定一个非负索引 rowIndex,返回杨辉三角的第 rowIndex 行。不同于生成整个杨辉三角,这道题要求我们只返回特定行,且空间复杂度应尽可能优化。例如输入3,需要返回[1,3,3,1]。


解题思路:

1.使用两个一维数组交替存储当前行和上一行数据

2.通过now/pre指针异或运算实现数组切换

3.首尾元素固定为1,中间元素由上一行相邻元素相加得到

4.最终只需保留最后计算的行数据


代码详解

class Solution {
public:
    vector<int> getRow(int rowIndex) {
       int a[2][34]; // 双数组存储空间
       int now=1;    // 当前写入数组索引
       int pre=0;    // 上一行数据数组索引
       a[pre][0]=1;  // 初始化第0行
       
       // 逐行计算
       for(int i=1;i<=rowIndex;i++) {
            for(int j=0;j<=i;j++) {
                if(j==i or j==0) {  // 首尾元素为1
                    a[now][j]=1;
                }
                else {  // 中间元素=上一行相邻元素之和
                    a[now][j]=a[pre][j]+a[pre][j-1];
                }
            }
            now^=1;  // 位运算切换数组
            pre^=1;  // 等价于now=(now+1)%2, pre=(pre+1)%2
       }
       
       // 组装结果
       vector<int> v;
       for(int i=0;i<=rowIndex;i++) {
            v.push_back(a[pre][i]); // 注意最后使用pre指针
       }
       return v;
    }
};




原创内容 转载请注明出处

分享给朋友:

相关文章

力扣451:ASCII数组计数法 用128个桶解决频率排序问题

力扣451:ASCII数组计数法 用128个桶解决频率排序问题

题目重解给定一个字符串,将字符按照出现频率降序排列。例如输入"tree",可能返回"eetr"或"eert"。题目要求我们不考虑字母顺序,只...

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

力扣501题最优解:不用额外空间找出BST中的众数?这个解法让你大开眼界

力扣501题最优解:不用额外空间找出BST中的众数?这个解法让你大开眼界

题目解读‌:在二叉搜索树的世界里,每个节点都默默记录着自己的数值。现在我们需要找出这些数值中出现频率最高的那些数字,也就是所谓的"众数"。有趣的是,二叉搜索树本身具有左小右大的特性...

牛客14496题解:括号最大深度问题(栈思想与代码优化)

牛客14496题解:括号最大深度问题(栈思想与代码优化)

一、题目解读牛客14496题要求计算给定括号字符串中的最大深度。例如,对于字符串 "(()())",最大深度为2。题目考察对括号嵌套结构的理解,以及如何通过编程找到最深嵌套层次。二...

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

一、题目解读力扣3112题要求解决带时间限制的最短路径问题:给定一个有向图,节点具有消失时间,需计算从起点到各节点的最短路径,且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法(如D...

牛客NC67题解:汉诺塔递归算法与解题步骤

牛客NC67题解:汉诺塔递归算法与解题步骤

一、题目解读牛客NC67题要求解决汉诺塔问题,这是一个经典的递归算法题目。题目给定整数n,代表汉诺塔中的盘子数量,需要输出将n个盘子从起始柱移动到目标柱的所有步骤。汉诺塔问题规则为:每次只能移动一个盘...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。