記錄一下如果 LeetCode 回傳值是二維陣列要怎麼處理
最近無聊寫了一些 LeetCode，在碰到題目要回傳二維陣列時有點卡關，不論怎麼寫都遇到
1
2
3
4
5
|
=================================================================
==32==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff01384c48 at pc 0x556b0238f4f1 bp 0x7fff01384910 sp 0x7fff01384900
READ of size 8 at 0x7fff01384c48 thread T0
#2 0x7efd505ac0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
... (後面一大串)
|
後來認真看了後才知道是沒有仔細看題目的註解，也對 C 語言一些機制不大了解。
static vs. dynamic array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char const *argv[])
{
int a[10];
printf("size of a is %lu\n", sizeof(a));
// size of b is 8
int *b;
b = malloc(sizeof(int) * 10);
printf("size of b is %lu\n", sizeof(b));
// size of b is 8
return 0;
}
|
靜態的陣列可以用 sizeof 來知道陣列的大小。
但動態宣告的陣列無法，如上面的範例，印出 b 的值是 8，表示 b 這個指向 int 的指標的大小。
所以如果有在 function 中新分配空間給動態陣列，並想把這個動態陣列傳到其他地方使用，除了這個動態陣列的本身 (也就是陣列的開始位置，以上面的例子來說是 b)，還要讓呼叫的地方那邊知道你分配了多長的位子。
但 C 語言的 function 只能有一個回傳值。解決方法可以把這個動態陣列連同長度包成 struct，或是讓陣列長度的這個資訊透過 function arguments 的方式改動呼叫那邊的值。
好像寫的有點亂，來看下面的例子
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
|
#include <stdio.h>
#include <stdlib.h>
int *createDynamicArray(int *arrayLength) {
*arrayLength = 5;
int *ret = calloc(sizeof(int), (*arrayLength));
return ret;
}
int main(int argc, char const *argv[])
{
int arrayLength;
int *arr;
arr = createDynamicArray(&arrayLength);
for(int i = 0; i < arrayLength; i++) {
printf("a[%d] = %d\n", i, arr[i]);
}
free(arr);
return 0;
}
|
我在 createDynamicArray 這個 function 中建立了一個動態陣列，想在 main 中用它。除了回傳這個動態陣列外，在 main 還會需要知道他的長度。在 main 中第 13 行宣告了他的長度，在 createDynamicArray 中以它作為 function argument，第 6 行修改了他的值。因此在 main 中可以操作這個陣列。
LeetCode 429. N-ary Tree Level Order Traversal (Medium)
那時候我是在寫 https://leetcode.com/problems/n-ary-tree-level-order-traversal/
簡單來說要回傳一個二維陣列，但呼叫那邊不知道這個陣列的長寬，所以這個陣列的長相也要讓呼叫端知道。
1
2
3
4
5
6
7
8
9
|
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
}
|
題目其實很清的寫了回傳的陣列高是 *returnSize，而每個 col 的大小則是存在 *returnColumnSizes 中。
在 main function 中，returnSize 是 int，而 returnColumnSizes 是 int *，但因為我想在 function 中更改他們的值，所以各自都多了一顆 *，變成 int * 和 int **。
一開始沒仔細看說明，以為一個長度為 3，各 colSize 為 [1,3,2] 的陣列只要回傳 [1,3,2]，但沒有長度不行，而且想改一個整數指標的指向在 function 只用整數指標去接根本無法真的改動到，而是要用整數指標的指標。
這題我的完整 code 長這樣
main function 主要是展示了應該如何呼叫，在 submit 時不能交
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#include <stdlib.h>
struct Node {
int val;
int numChildren;
struct Node** children;
};
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void findDepth(struct Node* root, int *depth, int curDepth) {
if(root->numChildren == 0) {
*depth = (curDepth > *depth ? curDepth : *depth);
}
else {
for(int i = 0; i < root->numChildren; i++) {
findDepth(root->children[i], depth, curDepth+1);
}
}
}
void findNodeNumEachLevel(struct Node* root, int** returnColumnSizes, int level) {
if(!root) {
return;
}
else {
(*returnColumnSizes)[level] ++;
for(int i = 0; i < root->numChildren; i++) {
findNodeNumEachLevel(root->children[i], returnColumnSizes, level+1);
}
}
}
void levelOderTraverse(struct Node* root, int **ans, int** returnColumnSizes, int level, int **levelCurPos) {
if(!root) {
return;
}
else {
ans[level][(*levelCurPos)[level]] = root->val;
(*levelCurPos)[level]++;
for(int i = 0; i < root->numChildren; i++) {
levelOderTraverse(root->children[i], ans, returnColumnSizes, level+1, levelCurPos);
}
}
}
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
//***********************************************************************//
// Deals with the case of empty tree.
if(!root) {
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
//***********************************************************************//
// Step 1. Get the depth of the tree.
// i.e. Obtain the value of returnSize.
int depth = 0;
findDepth(root, &depth, 1);
*returnSize = depth;
//***********************************************************************//
// Step 2. Get the number of nodes of each level.
// i.e. Decide the value of returnColumnSizes array.
*returnColumnSizes = malloc(sizeof(int*) * depth);
for(int i = 0; i < depth; i++) {
(*returnColumnSizes)[i] = 0;
}
findNodeNumEachLevel(root, returnColumnSizes, 0);
//***********************************************************************//
// Step 3. Fill in the result 2d array by the correct value.
// Traverse the whole tree and fill the number to the correct
// position in the result 2d array.
int **result;
result = malloc(sizeof(int*) * depth);
for(int i = 0; i < depth; i++) {
result[i] = malloc(sizeof(int) * (*returnColumnSizes)[i]);
}
int *levelCurPos = malloc(sizeof(int)*depth);
for(int i = 0; i < depth; i++) {
levelCurPos[i] = 0;
}
levelOderTraverse(root, result, returnColumnSizes, 0, &levelCurPos);
free(levelCurPos);
return result;
}
int main() {
int returnSize;
int *returnColumnSizes;
levelOrder(0, &returnSize, &returnColumnSizes);
return 0;
}
|