我要招人

去企业版

首页 > 试题广场 >

杨辉三角-ii

[编程题]杨辉三角-ii

热度指数：14997 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个索引k，返回杨辉三角的第k行

例如，k=3，

返回[1,3,3,1].

备注：

你能将你的算法优化到只使用O(k)的额外空间吗?

示例1

输入

输出

[1,3,3,1]

算法知识视频讲解

Java

wanbf

public ArrayList<Integer> getRow (int rowIndex) {
// write code here
//杨辉三角 [1] = 第0行
ArrayList<Integer> list = new ArrayList<Integer>();
if(rowIndex==0) {list.add(1);return list;}
ArrayList<Integer> temp = getRow(rowIndex-1);
for(int i=0;i<=rowIndex;i++){
if(i==0 || i==rowIndex){
list.add(1);
}else{
list.add(temp.get(i-1)+temp.get(i));
}
}
return list;
}

发表于 2022-01-09 23:29:09 回复(0)

Java

AriesLi

import java.util.*;
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>(rowIndex+1);
        list.add(1);
        for(int i = 1; i <= rowIndex; i++){
            list.add(0);
        };
        for(int i = 1; i <= rowIndex; i++){
            int tmp = 1;
            for(int j = 1; j <= i; j++ ){
                int now = tmp+list.get(j);
                tmp = list.get(j);
                list.set(j, now);
            }
        }
        return list;
    }
}

发表于 2020-01-10 20:05:47 回复(0)

Java

HW柯可

解法一:利用规律每个数字等于上一行的左右两个数字之和。

import java.util.ArrayList;
 
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i <= rowIndex;i ++){
            list.add(1);
        }
        for(int i = 0; i <= rowIndex; i++){
        //从后往前遍历，防止上一行的左右两个数中的左边数在使用时已被更改
            for(int j = i; j >= 0; j--){
                if(j == i || j == 0){
                    continue;
                }
                else{
                    list.set(j, list.get(j-1) + list.get(j));
                }
            }
        }
        return list;
    }
}

解法二
利用规律，第n行的第1个数为1，第二个数为1×(n-1)，第三个数为1×(n-1)×（n-2）/2，第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。

import java.util.ArrayList;
 
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = rowIndex + 1;
        //防止溢出，使用long
        long number = 1;
        for(int i = 1; i <= n; i++){
           list.add((int)number);
           number = number * (n - i) / i;
        }
        return list;
    }
}

编辑于 2019-07-25 12:31:59 回复(1)

Java

放学后我不走~

定义2个长度为k+1的数组，空间复杂度是O(k)级别，两个数组交替更新数据，最后一趟数组刚好填满，将数组用ArrayList形式返回即可，代码如下：

import java.util.*;
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        int a[] = new int[rowIndex+1];
        int b[] = new int[rowIndex+1];
        a[0] = 1;
        int indexa = 1;
        int indexb = 0;
        int index=1;//偶数行
        while(index <= rowIndex){
            if(index%2==0){
                for(int i=0;i<=indexb;i++)
                    if(i==0 || i==indexb)
                        a[i]=1;
                    else
                        a[i]=b[i]+b[i-1];
                indexa = indexb+1;
            }else{
                for(int i=0;i<=indexa;i++)
                    if(i==0 || i==indexa)
                        b[i]=1;
                    else
                        b[i]=a[i]+a[i-1];
                indexb = indexa+1;
            }
            index++;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(rowIndex%2==0)
            for(int i=0;i<indexa;i++)
                list.add(a[i]);
        else
            for(int i=0;i<indexb;i++)
                list.add(b[i]);
        return list;
    }
}

编辑于 2018-09-08 14:28:15 回复(0)

Java

吭哧吭哧埋头干

    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row = new ArrayList<Integer>();
        if (rowIndex < 0)
            return row;
        row.add(1);
        for (int i = 0; i < rowIndex; i++) {
            for (int j = i ; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
            row.add(1);
        }
        return row;
    }

发表于 2018-08-21 15:11:58 回复(0)

Java

jRomann

import java.util.*;
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(rowIndex==0) {
            res.add(1);
            return res;}
        int[][] a = new int[rowIndex+1][rowIndex+1];
        for (int i = 0; i < rowIndex+1; i++) {
        Arrays.fill(a[i], 1);
    }
        //a[0][0]=1;a[1][0]=1;a[1][1]=1;
        for(int i=2;i<rowIndex+1;i++){
            for(int j=1;j<i;j++){
                a[i][j]=a[i-1][j]+a[i-1][j-1];
            }
        }
        res.add(1);
        for(int i =1;i<rowIndex;i++){
            res.add(a[rowIndex][i]);
        }
        res.add(1);
        return res;
    }
}

发表于 2018-05-29 21:54:31 回复(0)

Java

阿拉要洗澡

import java.util.ArrayList;

public class Solution {

ArrayList<Integer> result=null;

public ArrayList<Integer> getRow(int rowIndex) {

if(rowIndex<0){

return result;

}

ArrayList<Integer> list=new ArrayList<Integer>();

list.add(1);

result=list;

if(rowIndex==0){

return result;

}

generateCore(1,rowIndex);

return result;

}

public void generateCore(int index,int numRows) {

if(numRows+1==index){

return;

}

ArrayList<Integer> list=new ArrayList<Integer>();

list.add(1);

for(int i=0;i<index-1;i++){

list.add( result.get(i)+result.get(i+1) );

}

list.add(1);

result=list;

generateCore(index+1,numRows);

}

发表于 2017-08-12 20:04:28 回复(0)

Java

pp11

import java.util.*;

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        if (rowIndex <= 0)
        	return list;
        for (int k = 1; k <= rowIndex; ++k) {
        	if (k == 1) {
        		list.add(1);
        		continue;
        	}
        	for (int i = 0; i < k + 1; ++i) {
        		if (i == 0 || i == k) {
        			list.add(1);
        			continue;
        		}
        		list.add(list.get(i - 1) + list.get(i));
        	}
        	for (int i = k - 1; i >= 0; --i) {
        		list.remove(i);
        	}
        }
        return list;
    }
}

发表于 2017-07-31 22:20:33 回复(0)

Java

Zfirsty

    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list =  new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++){
            if(i==0) {list.add(1);continue;}
            for(int j=0;j<list.size()-1;j++){
                int m=list.get(j+1);
                list.set(j+1,list.get(0)+list.get(j+1));
                list.set(0,m);
            }
            list.set(0,1);
            list.add(1);
        }
        return list;
    }

发表于 2017-07-24 16:39:15 回复(0)

Java

丫丁

//思路:从后往前计算，从而避免了之前的数据被覆盖。满足空间复杂度为O(n)
public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row=new ArrayList<>();
        if(rowIndex<0) return row;
        for(int i=0;i<rowIndex+1;i++){
            for(int j=i-1;j>0;j--){
                row.set(j,row.get(j)+row.get(j-1));
            }
            row.add(1);
        }
        return row;
    }

发表于 2017-07-17 20:28:45 回复(1)

Java

城市里的养猫者

public List<Integer> getRow(int rowIndex) {
    List<Integer> res = new ArrayList<Integer>(); for(int i = 0;i<rowIndex+1;i++) {
    		res.add(1); for(int j=i-1;j>0;j--) {
    			res.set(j, res.get(j-1)+res.get(j));
    		}
    } return res;
}