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
|
// 932. Beautiful Array
#include "leetcode.h"
/*
* an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the
* integers in the range '[1, n]', and for every '0 <= i < j < n', there is no
* index 'k' with 'i < k < j' where '2 * nums[k] == nums[i] + nums[j]'. given
* the integer 'n', return any beautiful array 'nums' of length 'n'. there will
* be at least one valid answer for the given 'n'.
*/
int *build_arr(int n, int **ans) {
if (ans[n])
return ans[n];
int *res = (int *)malloc(n * sizeof(int));
if (n == 1)
res[0] = 1;
else {
int j = 0;
int *odds = build_arr((n + 1) / 2, ans);
for (int k = 0; k < (n + 1) / 2; k++)
res[k] = 2 * odds[k] - 1;
int *evens = build_arr(n / 2, ans);
for (int k = 0; k < n / 2; k++)
res[((n + 1) / 2) + k] = 2 * evens[k];
}
ans[n] = res;
return res;
}
int *beautifulArray(int n, int *returnSize) {
int *ans = (int *)malloc(n * sizeof(int));
*returnSize = n;
if (n == 1) {
ans[0] = 1;
return ans;
}
if (n == 2) {
ans[0] = 1;
ans[1] = 2;
return ans;
}
int **res = (int **)malloc((n + 1) * sizeof(int *));
for (int i = 0; i < n + 1; i++)
res[i] = NULL;
ans = build_arr(n, res);
*returnSize = n;
for (int i = 0; i < n; i++)
free(res[i]);
free(res);
return ans;
}
int main() {
int rs1, *ba1 = beautifulArray(4, &rs1);
int rs2, *ba2 = beautifulArray(5, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", ba1[i]); // expect: 2 1 4 3
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", ba2[i]); // expect: 3 1 2 5 4
printf("\n");
free(ba1), free(ba2);
}
|