LeetCode C++ 118. Pascal‘s Triangle【Array】简单
发布日期:2021-07-01 02:53:54
浏览次数:2
分类:技术文章
本文共 2282 字,大约阅读时间需要 7 分钟。
Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.Example:
Input: 5Output:[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
题意:给定一个非负整数 numRows
,生成杨辉三角的前 numRows
行。
解法 递推
开始写的C++代码如下:
class Solution { public: vector> generate(int numRows) { vector > ans; if (numRows == 0) return ans; ans.push_back(vector { 1}); if (numRows == 1) return ans; ans.push_back(vector { 1, 1}); if (numRows == 2) return ans; for (int i = 2; i < numRows; ++i) { ans.push_back(vector { 1}); int size = ans[i - 1].size(); for (int j = 0; j < size - 1; ++j) ans[i].push_back(ans[i - 1][j] + ans[i - 1][j + 1]); ans[i].push_back(1); } return ans; }};
运行效率如下:
执行用时:4 ms, 在所有 C++ 提交中击败了38.91% 的用户内存消耗:6.9 MB, 在所有 C++ 提交中击败了5.03% 的用户
20201206 Update 今日打卡更新Java代码:
class Solution { public List
> generate(int numRows) { List
> ans = new ArrayList<>(); int[][] arr = new int[numRows][numRows]; for (int i = 0; i < numRows; ++i) { List subList = new ArrayList<>(); for (int j = 0; j <= i; ++j) { if (j == 0 || j == i) arr[i][j] = 1; else arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; subList.add(arr[i][j]); } ans.add(subList); } return ans; } } 运行效率见下:
执行用时:0 ms, 在所有 Java 提交中击败了100.00% 的用户内存消耗:36.5 MB, 在所有 Java 提交中击败了34.00% 的用户
这样写得太繁琐了,简化如下:
class Solution { public: vector> generate(int numRows) { vector > ans(numRows); for (int i = 0; i < numRows; ++i) { for (int j = 0; j < i + 1; ++j) { //第i行的数字个数为i+1 if (j == 0 || j == i) ans[i].push_back(1); //第i行的第0,i个数为1 else ans[i].push_back(ans[i - 1][j - 1] + ans[i - 1][j]); } } return ans; }};
提交后效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:6.6 MB, 在所有 C++ 提交中击败了40.46% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/109192803 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年05月07日 14时49分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01
你要的微信小程序终于来了
2019-05-01
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01
Linux软件万花筒
2019-05-01