第118题:杨辉三角

一. 问题描述

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5

输出:

[

     [1],

    [1,1],

   [1,2,1],

  [1,3,3,1],

 [1,4,6,4,1]

]

二. 解题思路

本题四路:采用递归的方法进行求解。

步骤一:构建递归函数(全局列表list存储结果,局部变量data存储某一层的结果,number表示第几层,tacket表示总层数)

步骤二:递归函数中,如果number>tacket则递归结束,否则构建临时列表newdata,根据杨辉三角的特性,将newdata的第2位到number-1位依次添加data中存储的相邻两数之和,然后将第一位和最后一位添加1。重复步骤二进行递归。

步骤三:直到如果number>tacket则递归结束。返回list。

三. 执行结果

执行用时 :1 ms, 在所有 java 提交中击败了98.50%的用户

内存消耗 :34 MB, 在所有 java 提交中击败了26.10%的用户

四. Java代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(numRows==0) {
            return list;
        }
        List<Integer> data=new ArrayList<Integer>();
        data.add(1);
        list.add(data);
        if(numRows==1) {
            return list;
        }else {
           getRow(list,data,2,numRows);
           return list;
        }
    }
     public void getRow(List<List<Integer>> list,List<Integer> data,int number,int tacket) {
        if(number>tacket) {
            return ;
                }
        List<Integer> newdata=new ArrayList<Integer>();
        for(int i=0;i<number;i++) {
            if(i==0||i==number-1) {
                newdata.add(1);
            }else {
                int temp=data.get(i-1)+data.get(i);
                newdata.add(temp);
            }
        }
        list.add(newdata);
        getRow(list,newdata,number+1,tacket);
    }
}

 

上一篇:数据类型118


下一篇:118. 杨辉三角