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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
// 2564. Substring XOR Queries
#include "leetcode.h"
/*
* you are given a binary string 's' and a 2d integer array 'queries' where
* 'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
* substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
* xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
* to the i'th query is the endpoints of the substring '[left_i, right_i]' or
* '[-1, -1]' if no such substring exists. if there are multiple answers, choose
* the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
* [left_i, right_i]' is the answer to the i'th query. a substring is a
* contiguous non-empty sequence of characters within a string.
*/
struct hash {
int key;
struct hash *next;
UT_hash_handle hh;
};
void resp(struct hash *entry, int idx, struct hash *entries, int **out) {
int start = idx, end = idx, target = entry->key;
while (target >>= 1)
--start;
do {
int res = entry - entries;
out[res][0] = start;
out[res][1] = end;
} while ((entry = entry->next));
}
int **substringXorQueries(char *s, int **queries, int queriesSize,
int *queriesColSize, int *returnSize,
int **returnColumnSizes) {
int **ans = (int **)malloc(queriesSize * sizeof(int *));
*returnColumnSizes = (int *)malloc(queriesSize * sizeof(int));
for (int i = 0; i < queriesSize; ++i) {
ans[i] = (int *)malloc(2 * sizeof(int));
(*returnColumnSizes)[i] = 2;
}
*returnSize = queriesSize;
struct hash *table = NULL, *entry;
struct hash *const entries =
(struct hash *)malloc(queriesSize * sizeof(struct hash));
for (int i = 0; i < queriesSize; ++i) {
int target = queries[i][0] ^ queries[i][1];
HASH_FIND_INT(table, &target, entry);
if (!entry) {
entries[i].key = target;
entries[i].next = NULL;
HASH_ADD_INT(table, key, &entries[i]);
} else {
entries[i].next = entry->next;
entry->next = &entries[i];
}
}
int arr[31], cnt = 0;
for (int i = 0; s[i]; i++) {
cnt = 30 == cnt ? 30 : cnt + 1;
for (int j = cnt - 1; j; --j) {
arr[j] = (arr[j - 1] << 1) + ('1' == s[i]);
HASH_FIND_INT(table, &arr[j], entry);
if (entry) {
resp(entry, i, entries, ans);
HASH_DEL(table, entry);
}
}
arr[0] = ('1' == s[i]);
HASH_FIND_INT(table, &arr[0], entry);
if (entry) {
resp(entry, i, entries, ans);
HASH_DEL(table, entry);
}
}
struct hash *tmp;
HASH_ITER(hh, table, entry, tmp) {
do {
ans[entry - entries][0] = -1;
ans[entry - entries][1] = -1;
} while ((entry = entry->next));
}
HASH_CLEAR(hh, table);
free(entries);
return ans;
}
int main() {
char *s1 = "101101", *s2 = "0101", *s3 = "1";
int q1i[2][2] = {{0, 5}, {1, 2}}, q2i[1][2] = {{12, 8}}, q3i[1][2] = {{4, 5}};
struct two_d_arr q1, q2, q3;
two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
two_d_arr_init(&q3, ARRAY_SIZE(q3i), ARRAY_SIZE(q3i[0]), q3i);
int rs1, *rcs1,
**sxq1 = substringXorQueries(s1, q1.arr, q1.row_size, q1.col_size, &rs1,
&rcs1);
int rs2, *rcs2,
**sxq2 = substringXorQueries(s2, q2.arr, q2.row_size, q2.col_size, &rs2,
&rcs2);
int rs3, *rcs3,
**sxq3 = substringXorQueries(s3, q3.arr, q3.row_size, q3.col_size, &rs3,
&rcs3);
for (int i = 0; i < rs1; i++) {
for (int j = 0; j < rcs1[i]; j++)
printf("%d ", sxq1[i][j]); // expect: [[0,2],[2,3]]
printf("\n");
}
printf("\n");
for (int i = 0; i < rs2; i++) {
for (int j = 0; j < rcs2[i]; j++)
printf("%d ", sxq2[i][j]); // expect: [[-1,-1]]
printf("\n");
}
printf("\n");
for (int i = 0; i < rs3; i++) {
for (int j = 0; j < rcs3[i]; j++)
printf("%d ", sxq1[i][j]); // expect: [[0,0]]
printf("\n");
}
printf("\n");
for (int i = 0; i < rs1; i++)
free(sxq1[i]);
free(sxq1);
for (int i = 0; i < rs2; i++)
free(sxq2[i]);
free(sxq1);
for (int i = 0; i < rs3; i++)
free(sxq3[i]);
free(sxq3);
free(rcs1);
free(rcs2);
free(rcs3);
two_d_arr_free(&q1);
two_d_arr_free(&q2);
two_d_arr_free(&q3);
}
|