-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0119.c
74 lines (72 loc) · 1.46 KB
/
q0119.c
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//
// q0119.c
// LeetCode
//
// Created by NowOrNever on 18/02/2020.
// Copyright © 2020 DoubleL. All rights reserved.
//
#include "q0119.h"
#include "../common.h"
//119. Pascal's Triangle II
//Easy
//
//636
//
//188
//
//Add to List
//
//Share
//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.
//
//
//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?
//
//Accepted
//250,430
//Submissions
//534,052
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getRow(int rowIndex, int* returnSize){
if (rowIndex < 0) {
return NULL;
}
int size = rowIndex + 1;
*returnSize = size;
int *array1 = calloc(size, sizeof(int));
int *array2 = calloc(size, sizeof(int));
array1[0] = 1;
array2[0] = 1;
for (int i = 1; i < size; i++) {
int *temp = array1;
array1 = array2;
array2 = temp;
for (int j = 1; j <= i; j++) {
array2[j] = array1[j] + array1[j - 1];
}
}
free(array1);
int *result = array2;
return result;
}
int question119(){
int size = 0;
int *result = getRow(4, &size);
for (int i = 0; i < size; i++) {
printf("%4d", result[i]);
}
printf("\n");
return 0;
};