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
|
// 1630. Arithmetic Subarrays
#include "leetcode.h"
/*
* a sequence of numbers is called arithmetic if it consists of at least two
* elements and the difference between every two consecutive elements is the
* same. more formally, a sequence 's' is arithmetic if and only if 's[i + 1] -
* s[i] == s[1] - s[0]' for all valid 'i'. you are given an array of 'n'
* integers 'nums' and two arrays of 'm' integers each 'l' and 'r' respectively
* representingthe 'm' range queries where the i'th query isthe range '[l[i],
* r[i]]'. all the arrays are 0-indexed. return a list of boolean elements 'ans'
* where 'ans[i]' is true if the subarray 'nums[l[i]], nums[l[i] + 1], ...,
* nums[r[i]]' can be rearrange to form an arithmetic sequence and false
* otherwise
*/
int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
bool check(int *nums, int start, int size) {
int *arr = (int *)malloc(size * sizeof(int));
memcpy(arr, nums + start, size * sizeof(int));
qsort(arr, size, sizeof(int), cmp);
int res = arr[1] - arr[0];
for (int i = 1; i < size; i++)
if (arr[i] - arr[i - 1] != res) {
free(arr);
return false;
}
free(arr);
return true;
}
bool *checkArithmeticSubarrays(int *nums, int nums_size, int *l, int l_size,
int *r, int r_size, int *return_size) {
*return_size = l_size;
bool *ans = (bool *)malloc((*return_size) * sizeof(bool));
for (int i = 0; i < (*return_size); i++) {
int start = l[i], size = r[i] - l[i] + 1;
ans[i] = check(nums, start, size);
}
return ans;
}
int main() {
int n1[] = {4, 6, 5, 9, 3, 7},
n2[] = {-12, -9, -3, -12, -6, 15, 20, -25, -20, -15, -10};
int l1[] = {0, 0, 2}, r1[] = {2, 3, 5}, l2[] = {0, 1, 6, 4, 8, 7},
r2[] = {4, 4, 9, 7, 9, 10};
int rs1[] = {}, rs2[] = {};
bool *cas1 = checkArithmeticSubarrays(n1, ARRAY_SIZE(n1), l1, ARRAY_SIZE(l1),
r1, ARRAY_SIZE(r1), rs1);
bool *cas2 = checkArithmeticSubarrays(n2, ARRAY_SIZE(n2), l2, ARRAY_SIZE(l2),
r2, ARRAY_SIZE(r2), rs2);
for (int i = 0; i < 3; i++)
printf("%d", cas1[i]); // expect: 1 0 1
printf("\n");
for (int i = 0; i < 6; i++)
printf("%d", cas2[i]); // expect: 0 1 0 0 1 1
printf("\n");
}
|