leetcode题目解答报告（2）

た入场券 2022-07-13 09:53 170阅读 0赞

Pascal's Triangle

## 题目描述 ##

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]
    ]

题目思路：

把每一行的数据看作一个list，每行的每个数据按顺序存入list中。再把整个一行看作一个整体，存入一个新的list中，这个list的每个元素都是一个list对象。也就是list的嵌套。

分析数字排列结构可以知道，每一行的第一个和最后一个数都是1。每一行的其他位置的数是由上一行对应位置的数a加上a的前一个数的和。对于第一行第二行单独分出即可。

需要注意的是list的下标都是从零开始。

代码1：

import java.util.*;
    public class PascalsTriangle {
        public ArrayList<ArrayList<Integer>> generate(int numRows) {
    //List<List<Integer>>定义一个List，其子元素是List对象，子元素包含的数据是Integer类型
        	//也就是int的类封装
            if (numRows < 0) {
                return null;
            }
    
            ArrayList<ArrayList<Integer>>list = new ArrayList<ArrayList<Integer>>();
    //定义一个list作为返回值
            if (numRows >= 1) {//大于等于1行时都执行该语句块。
                ArrayList<Integer> data = new ArrayList<Integer>();
                data.add(1);//把数字1加入到data中
                list.add(data);//把data作为元素加入list中，这时第一行数据存储结束
            }
    
            if (numRows >= 2) {//大于等于2行时都执行该语句块。
                ArrayList<Integer> data = new ArrayList<Integer>();
                data.add(1);
                data.add(1);
                list.add(data);//data作为第二行数据存入list中
            }
    
            if (numRows >=3) {
                for (int i = 3; i <=numRows; i++) {
                    ArrayList<Integer> data = new ArrayList<Integer>();
                    ArrayList<Integer> prev = list.get(i - 2);//下标从零开始，所以是i-2，这里的i
                    //等于3在list中实际上是下标为2的元素，其前一个元素是下标为1的元素，也就是
                    //3-2=1.
                    data.add(1);//第一个数字为1
                    //第i行有i个数字，且第1个和第i个数字为1
                    for (int j = 2; j <= i -1; j++) {//计算第2到i-1个的元素数字。（对应在list的下标是1到i-2）
                        data.add(prev.get(j - 2) + prev.get(j - 1));//是前一行的第j-1和j的数字和。因为
                        //下标从零开始，所以对应的下标为j-2和j-1
                    }
                    data.add(1);//末尾数字为1
    
                    list.add(data);//把第i行加入list
                }
            }
    
            return list;
        }
        public static void main(String[] args) {
        	PascalsTriangle test=new PascalsTriangle();
        	ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        	list=test.generate(5);
        	for(int i=0;i<list.size();i++) {
        		System.out.println(list.get(i));
        	}
    	}
    }

代码2：

import java.util.*;
    public class PascalsTriangle {
        public ArrayList<ArrayList<Integer>> generate(int numRows) {
            ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(numRows <= 0){
                return lists;
            }
            list.add(1);//上一个判断未执行，则numRows至少为1，
            lists.add(new ArrayList<Integer>(list));//无论numRows等于多少，第一行的数据就是1
            for(int i = 1; i < numRows; i++){
                list.clear();//每次大循环后，list清零
                list.add(1);//每行第一个元素为1，对应的下标是0
                for(int j = 1; j < i; j++){//下标从1到i-1共i-1个元素。该行一共有i+1个元素，
                	//i最大为numRows-1，j最大为numRow-2.
                    list.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
                }
                list.add(1);//末尾元素为1
                lists.add(new ArrayList<Integer>(list));
            }
            return lists;
        }
        public static void main(String[] args) {
        	PascalsTriangle test=new PascalsTriangle();
        	ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        	list=test.generate(5);
        	for(int i=0;i<list.size();i++) {
        		System.out.println(list.get(i));
        	}
       }
    }

Pascal's Triangle II

## 题目描述 ##

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?

题目思路：题目要求空间复杂度为O(k),我们开辟的数组空间受限

import java.util.*;
    import java.lang.*;
    public class Solution {
        public ArrayList<Integer> getRow(int rowIndex) {
            int[] last=new int[rowIndex+1];
             int[] now=new int[rowIndex+1];
            int[] tmp=new int[rowIndex+1];//中间转换数组，因为数组之间的直接赋值是引用
            //最后指向和操作的还是同一个数据块
            last[0]=1;
            for(int i=1;i<=rowIndex;i++){
                now[0]=1;
                now[i]=1;
                  for(int j=1;j<i;j++){
                      now[j]=last[j-1]+last[j];
                  }
                //  tmp的作用是交换last和now的引用值。主要是保存当前的now为last，用于
                  //下次循环的计算，now不能再指向当前的now，应指向其他的数据块，值不必管，
                  //下次循环计算时now的值会被重新赋值
               tmp=last;//tmp指向了last的数据块，
                last=now;//last指向了now的数据块
                now=tmp;//now指向了last的数据块
            }
             
            ArrayList ans=new ArrayList<Integer>();
             
            for(int i=0;i<=rowIndex;i++){
                ans.add(last[i]);
            }
            return ans;
        }
        public static void main(String[] args) {
        	ArrayList<Integer> mylist=new ArrayList<Integer>();
        	Solution mytest=new Solution();
        	mylist=mytest.getRow(4);
        	System.out.println(mylist);
    	}
    }