pascals-triangleI、II——生成规律的三角形
2024-10-19 14:00:28
1、Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
res[i][j]=res[i-1][j-1]+res[i-1][j]
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int>> res;
if(numRows==) return res;
for(int i=;i<numRows;i++){
vector<int> tmp;
if(i==){
tmp.push_back();
res.push_back(tmp);
continue;
}
for(int j=;j<=i;j++){
if(j==||j==i){
tmp.push_back();
continue;
} tmp.push_back(res[i-][j-]+res[i-][j]);
}
res.push_back(tmp);
}
return res;
}
};
2、
Given an index k, return the k th row of the Pascal's triangle.
For example, given k = 3,
Return[1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?这道题跟Pascal's Triangle很类似,只是这里只需要求出某一行的结果。Pascal's Triangle中因为是求出全部结果,所以我们需要上一行的数据就很自然的可以去取。而这里我们只需要一行数据,就得考虑一下是不是能只用一行的空间来存储结果而不需要额外的来存储上一行呢?这里确实是可以实现的。对于每一行我们知道如果从前往后扫,第i个元素的值等于上一行的res[i]+res[i+1],可以看到数据是往前看的,如果我们只用一行空间,那么需要的数据就会被覆盖掉。所以这里采取的方法是从后往前扫,这样每次需要的数据就是res[i]+res[i-1],我们需要的数据不会被覆盖,因为需要的res[i]只在当前步用,下一步就不需要了。这个技巧在动态规划省空间时也经常使用,主要就是看我们需要的数据是原来的数据还是新的数据来决定我们遍历的方向。时间复杂度还是O(n^2),而空间这里是O(k)来存储结果,仍然不需要额外空间。代码如下:
class Solution {
public:
vector<int> getRow(int rowIndex) { if(rowIndex<) return vector<int>();
vector<int> res(rowIndex+,);
for(int i=;i<=rowIndex;i++){
for(int j=i-;j>=;j--){
res[j]=res[j]+res[j-];
}
}
return res;
}
};
最新文章
- C#线程同步手动重置事件——ManualResetEvent
- Android初涉及之Android Studio&;JAVA入门--二月不能不写东西
- Unity热门插件推荐
- node
- Ubuntu14.04安装和配置Tomcat8.0.12(转)
- Hibernate中的一级缓存、二级缓存和懒加载
- Builder模式在Java中的应用(转)
- 【Java基础01】Java InputStream的read方法
- nginx + memcached-session-manager 实现tomcat下的负载均衡
- MySQL安装与测试
- hadoop启动守护进程报JAVA_HOME is not set and could not be found
- 小猪猪逆袭成博士之C++基础篇(一)数据精度、强制类型转换、变量命名规则
- Java的static关键字
- Eclipse rap 富客户端开发总结(2):rap项目目前的进度和存在的问题
- Git版本管理工具常用命令说明
- Linux出现Read-only file system错误的解决方法
- Prometheus监控学习记录
- Note | 学术论文写作方法和技巧
- WAI-ARIA无障碍网页应用属性完全展示
- AMM调整为ASMM命令(关闭memory_target自动管理方式)
热门文章
- C++ 将string转换成char*字符串
- NVIDIA NVML Driver/library version mismatch
- python装饰器实现用户密码认证(简单初形)
- HDU——1062Text Reverse(水题string::find系列+reverse)
- animation总结
- poj 1981 Circle and Points
- FOJ Problem 2254 英语考试
- POJ 2893 M &#215; N Puzzle
- git提交node-modules报文件名过长无法提交问题
- 卸载重安firefox