diff options
Diffstat (limited to 'substring_xor_queries.c')
-rw-r--r-- | substring_xor_queries.c | 137 |
1 files changed, 137 insertions, 0 deletions
diff --git a/substring_xor_queries.c b/substring_xor_queries.c new file mode 100644 index 0000000..4c2a6d2 --- /dev/null +++ b/substring_xor_queries.c @@ -0,0 +1,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); +} |