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
|
// 967. Numbers With Same Consecutive Differences
#include "leetcode.h"
/*
* given two integers 'n' and 'k' return an array of all the integers of length
* 'n' where the difference between every two consecutive digits is 'k'. you may
* return the answer in any order. note that the integers should not have
* leading zeros. integers as 02 and 043 are not allowed.
*/
void dfs(int *res, int *idx, int val, int digit, int k) {
if (!digit) {
res[*idx] = val;
(*idx)++;
return;
}
if (val % 10 + k < 10)
dfs(res, idx, val * 10 + (val % 10 + k), digit - 1, k);
if ((val % 10) - k >= 0)
dfs(res, idx, val * 10 + (val % 10 - k), digit - 1, k);
}
int *numsSameConsecDiff(int n, int k, int *returnSize) {
if (!k) {
int *ans = (int *)malloc(9 * sizeof(int));
for (int i = 1; i <= 9; i++) {
int val = i;
for (int j = 0; j < n - 1; j++)
val = val * 10 + i;
ans[i - 1] = val;
}
*returnSize = 9;
return ans;
}
int *ans = (int *)malloc(9 * pow(2, n) * sizeof(int)), idx = 0;
for (int i = 1; i <= 9; i++)
dfs(ans, &idx, i, n - 1, k);
*returnSize = idx;
return ans;
}
int main() {
int rs1, rs2;
int *nscd1 = numsSameConsecDiff(3, 7, &rs1);
int *nscd2 = numsSameConsecDiff(2, 1, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", nscd1[i]); // expect: 181 292 707 818 929
printf("\n");
for (int i = 0; i < rs2; i++)
printf(
"%d ",
nscd2[i]); // expect: 10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98
printf("\n");
free(nscd1), free(nscd2);
}
|