FilesExpand file tree

 master

/

PascalsTriangleII119.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (51 loc) · 1.48 KB

 master

/

PascalsTriangleII119.java

Copy path

Top

File metadata and controls

• Code
• Blame

57 lines (51 loc) · 1.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

/**

* Given a non-negative index k where k ≤ 33, return the kth index row of the

* Pascal's triangle.

*

* Note that the row index starts from 0.

* https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif

*

* In Pascal's triangle, each number is the sum of the two numbers directly above it.

*

* Example:

* Input: 3

* Output: [1,3,3,1]

*

* Follow up:

* Could you optimize your algorithm to use only O(k) extra space?

*/

public class PascalsTriangleII119 {

public List<Integer> getRow(int rowIndex) {

LinkedList<Integer> res = new LinkedList<>();

res.add(1);

if (rowIndex == 0) return res;

res.add(1);

if (rowIndex == 1) return res;

int i = 2;

while (i <= rowIndex) {

int size = res.size();

res.add(1);

int pre = res.removeFirst();

for (int j=0; j<size-1; j++) {

int now = res.removeFirst();

res.add(pre + now);

pre = now;

}

res.add(1);

i++;

}

return res;

}

/**

* https://leetcode.com/problems/pascals-triangle-ii/discuss/38420/Here-is-my-brief-O(k)-solution

*/

public List<Integer> getRow2(int rowIndex) {

long nCk = 1;

List<Integer> result = new ArrayList<Integer>();

for(int i=0;i<=rowIndex;i++){

result.add((int)nCk);

nCk = nCk *(rowIndex-i)/(i+1);

}

return result;

}

}