leetcode118-杨辉三角

原题

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
leetcode118-杨辉三角
在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1] ]

解法

思想

根据上一行生成下一行,避免重复计算

代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<Integer> row = new ArrayList();
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for(int n = 0;n<numRows;n++){
            row = getRow(n+1,row);
            ret.add(row);
        }
        return ret;
    }

    //n:第n行,nums:上一行(n-1行)的列表
    public List<Integer> getRow(int n,List<Integer> nums){
        List<Integer> ret = new ArrayList();
        ret.add(1);//第一个1不需要计算
        if(n==1){//第一行直接返回
            return ret;
        }
        for(int i=1;i<(n+1)/2;i++){//由上一行的数相加得到结果
            ret.add(nums.get(i-1)+nums.get(i));
        }
        int size = n/2;
        for(int i=0;i<size;i++){//镜像处理
            ret.add(ret.get(size-i-1));
        }
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode118-%e6%9d%a8%e8%be%89%e4%b8%89%e8%a7%92/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年11月14日
下一篇 2019年11月18日

相关推荐

  • leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月20日
    080
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0240
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    090
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    090
  • 剑指offer05-替换空格

    原题(来源Leetcode) 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例1: 输入: s = "We are happy." 输出: "We%20are%2…

    算法 2020年4月5日
    0100
  • leetcode36-有效的数独

    原题 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-…

    2019年12月26日
    090
  • leetcode343-整数拆分

    原题 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1…

    算法 2020年4月13日
    0110

发表回复

登录后才能评论