diff options
-rw-r--r-- | count_and_say.c | 68 | ||||
-rw-r--r-- | count_and_say.py | 35 | ||||
-rw-r--r-- | count_equal_div_pair_arr.c | 23 | ||||
-rw-r--r-- | count_equal_div_pair_arr.py | 37 | ||||
-rw-r--r-- | count_hidden_sequences.c | 29 | ||||
-rw-r--r-- | count_hidden_sequences.py | 30 | ||||
-rw-r--r-- | count_num_fair_pairs.c | 51 | ||||
-rw-r--r-- | count_num_fair_pairs.py | 5 | ||||
-rw-r--r-- | count_num_good_subarr.c | 94 | ||||
-rw-r--r-- | count_num_good_subarr.py | 35 | ||||
-rw-r--r-- | count_num_ideal_arr.c | 36 | ||||
-rw-r--r-- | count_num_ideal_arr.py | 38 | ||||
-rw-r--r-- | max_product_len_palindrome_subseq.c | 46 | ||||
-rw-r--r-- | max_product_len_palindrome_subseq.py | 46 | ||||
-rw-r--r-- | rabbits_in_forest.c | 36 | ||||
-rw-r--r-- | rabbits_in_forest.py | 30 | ||||
-rw-r--r-- | substring_xor_queries.c | 137 | ||||
-rw-r--r-- | substring_xor_queries.py | 43 |
18 files changed, 735 insertions, 84 deletions
diff --git a/count_and_say.c b/count_and_say.c index 8d186fc..95726cd 100644 --- a/count_and_say.c +++ b/count_and_say.c @@ -1,7 +1,5 @@ // 38. Count and Say -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +#include "leetcode.h" /* * the count-and-say sequence is a sequence of digit strings defined by the @@ -16,53 +14,33 @@ * term of the count and say sequence. */ -char *int_to_char(int n) { - char *res = malloc(11); - res[10] = '\0'; - int idx = 9; - while (n) { - res[idx] = '0' + n % 10; - n /= 10; - idx--; - } - return &res[idx + 1]; -} - char *countAndSay(int n) { - char *curr = malloc(5000), *post = malloc(5000); - curr[0] = '1'; - curr[1] = '\0'; if (n == 1) - return curr; - for (int i = 2; i <= n; i++) { - int curr_len = strlen(curr), idx = 0, cnt = 1, pos = 0; - char *tmp; - for (int j = 1; j < curr_len; j++) { - if (curr[j] == curr[j - 1]) - cnt++; - else { - tmp = int_to_char(cnt); - strncpy(&post[pos], tmp, strlen(tmp)); - pos += strlen(tmp); - post[pos] = curr[j - 1]; - pos++; - cnt = 1; - } + return "1"; + char *s = countAndSay(n - 1), curr = *s; + char *ans = (char *)malloc(4463 * sizeof(char)); + int m = strlen(s), idx = 0, cnt = 1; + for (int i = 1; i < m; i++) { + char c = *(s + i); + if (c == curr) + cnt++; + else { + *(ans + idx++) = ('0' + cnt); + *(ans + idx++) = curr; + curr = c; + cnt = 1; } - tmp = int_to_char(cnt); - strncpy(&post[pos], tmp, strlen(tmp)); - pos += strlen(tmp); - post[pos] = curr[curr_len - 1]; - pos++; - post[pos] = '\0'; - tmp = curr; - curr = post; - post = tmp; } - return curr; + *(ans + idx++) = ('0' + cnt); + *(ans + idx++) = curr; + *(ans + idx) = '\0'; + return ans; } int main() { - printf("%s\n", countAndSay(1)); // expect: 1 - printf("%s\n", countAndSay(4)); // expect: 1211 + char *cas1 = countAndSay(4), *cas2 = countAndSay(1); + printf("%s\n", cas1); // expect: 1211 + printf("%s\n", cas2); // expect: 1 + free(cas1); + free(cas2); } diff --git a/count_and_say.py b/count_and_say.py new file mode 100644 index 0000000..e8521b3 --- /dev/null +++ b/count_and_say.py @@ -0,0 +1,35 @@ +# 38. Count and Say +from re import findall + +""" +the count-and-say sequence is a sequence of digit strings defined by the +recursive formula: +- countAndSay(1) = "1" +- countAndSay(n) is the way you would "say" the digit string from +'countAndSay(n - 1)', which is then converted into a different digit string +to determine how you "say" a digit string, split it into minimal number of +substrings such that each substring contains exactly one unique digit. then +for each substring, say the number of digits, then say the digit, finally, +concatenate every said digit. given a positive integer 'n', return the n'th +term of the count and say sequence. +""" + + +class Solution(object): + def countAndSay(self, n): + """ + :type n: int + :rtype: str + """ + ans = "1" + for _ in range(n - 1): + ans = "".join( + str(len(group)) + digit for group, digit in findall(r"((.)\2*)", ans) + ) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countAndSay(n=4)) + print(obj.countAndSay(n=1)) diff --git a/count_equal_div_pair_arr.c b/count_equal_div_pair_arr.c new file mode 100644 index 0000000..d6aeb12 --- /dev/null +++ b/count_equal_div_pair_arr.c @@ -0,0 +1,23 @@ +// 2176. Count Equal and Divisible Pairs in an Array +#include "leetcode.h" + +/* + * given a 0-indexed integer array 'nums' of length 'n' and an integer 'k', + * return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i] + * == nums[j]' and '(i * j)' is divisble by 'k'. + */ + +int countPairs(int *nums, int numsSize, int k) { + int cnt = 0; + for (int i = 0; i < numsSize; i++) + for (int j = i + 1; j < numsSize; j++) + if (nums[i] == nums[j] && !((i * j) % k)) + cnt++; + return cnt; +} + +int main() { + int n1[] = {3, 1, 2, 2, 2, 1, 3}, n2[] = {1, 2, 3, 4}; + printf("%d\n", countPairs(n1, ARRAY_SIZE(n1), 2)); // expect: 4 + printf("%d\n", countPairs(n2, ARRAY_SIZE(n2), 1)); // expect: 0 +} diff --git a/count_equal_div_pair_arr.py b/count_equal_div_pair_arr.py new file mode 100644 index 0000000..84d4a55 --- /dev/null +++ b/count_equal_div_pair_arr.py @@ -0,0 +1,37 @@ +# 2176. Count Equal and Divisible Pairs in an Array +import collections +from math import gcd + +""" +given a 0-indexed integer array 'nums' of length 'n' and an integer 'k', +return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i] +== nums[j]' and '(i * j)' is divisble by 'k'. +""" + + +class Solution(object): + def countPairs(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ids = collections.defaultdict(list) + for i, j in enumerate(nums): + ids[j].append(i) + ans = 0 + for i in ids.values(): + gcds = collections.Counter() + for j in i: + curr_i = gcd(j, k) + ans += sum( + cnt for curr_j, cnt in gcds.items() if curr_i * curr_j % k == 0 + ) + gcds[curr_i] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countPairs(nums=[3, 1, 2, 2, 2, 1, 3], k=2)) + print(obj.countPairs(nums=[1, 2, 3, 4], k=1)) diff --git a/count_hidden_sequences.c b/count_hidden_sequences.c new file mode 100644 index 0000000..0d8c2e1 --- /dev/null +++ b/count_hidden_sequences.c @@ -0,0 +1,29 @@ +// 2145. Count the Hidden Sequences +#include "leetcode.h" + +/* + * you are given a 0-indexed array of 'n' integers 'differences', which + * describes the differences between each pair of consecutive integers of a + * hidden sequence of length '(n + 1)'. you are further given two integers + * 'lower' and 'upper' that describe the inclusive range of values '[lower, + * upper]' that the hidden sequence can contain. return the number of possible + * hidden sequences there are. if there are no possible sequences, return 0. + */ + +int numberOfArrays(int *differences, int differencesSize, int lower, + int upper) { + long long cnt = 0, a = 0, b = 0; + for (int i = 0; i < differencesSize; i++) { + cnt += differences[i]; + a = fmax(a, cnt); + b = fmin(b, cnt); + } + return fmax(0L, (upper - lower) - (a - b) + 1); +} + +int main() { + int d1[] = {1, -3, 4}, d2[] = {3, -4, 5, 1, -2}, d3[] = {4, -7, 2}; + printf("%d\n", numberOfArrays(d1, ARRAY_SIZE(d1), 1, 6)); // expect: 2 + printf("%d\n", numberOfArrays(d2, ARRAY_SIZE(d2), -4, 5)); // expect: 4 + printf("%d\n", numberOfArrays(d3, ARRAY_SIZE(d3), 3, 6)); // expect: 0 +} diff --git a/count_hidden_sequences.py b/count_hidden_sequences.py new file mode 100644 index 0000000..c229f7a --- /dev/null +++ b/count_hidden_sequences.py @@ -0,0 +1,30 @@ +# 2145. Count the Hidden Sequences +from itertools import accumulate + +""" +you are given a 0-indexed array of 'n' integers 'differences', which +describes the differences between each pair of consecutive integers of a +hidden sequence of length '(n + 1)'. you are further given two integers +'lower' and 'upper' that describe the inclusive range of values '[lower, +upper]' that the hidden sequence can contain. return the number of possible +hidden sequences there are. if there are no possible sequences, return 0. +""" + + +class Solution(object): + def numberOfcntrrays(self, differences, lower, upper): + """ + :type differences: List[int] + :type lower: int + :type upper: int + :rtype: int + """ + cnt = list(accumulate(differences, initial=0)) + return max(0, (upper - lower) - (max(cnt) - min(cnt)) + 1) + + +if __name__ == "__main__": + obj = Solution() + print(obj.numberOfcntrrays(differences=[1, -3, 4], lower=1, upper=6)) + print(obj.numberOfcntrrays(differences=[3, -4, 5, 1, -2], lower=-4, upper=5)) + print(obj.numberOfcntrrays(differences=[4, -7, 2], lower=3, upper=6)) diff --git a/count_num_fair_pairs.c b/count_num_fair_pairs.c index 80d26f1..9ddfc9a 100644 --- a/count_num_fair_pairs.c +++ b/count_num_fair_pairs.c @@ -7,46 +7,25 @@ * i < j < n' and 'lower <= nums[i] + nums[j] <= upper' */ -int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } - -int bs_lower(int *nums, int n, int left, int right, int lower) { - int l = left, r = right; - if (nums[r] < lower) - return -1; - while (l < r) { - int m = l + (r - l) / 2; - if (nums[m] < lower) - l = m + 1; - else - r = m; - } - return l; -} - -int bs_upper(int *nums, int n, int left, int right, int upper) { - int l = left, r = right; - if (nums[l] > upper) - return -1; - while (l < r) { - int m = r - (r - l) / 2; - if (nums[m] > upper) - r = m - 1; - else - l = m; - } - return l; +int cmp(const void *a, const void *b) { + return (*(int *)a > *(int *)b) - (*(int *)b > *(int *)a); } long long countFairPairs(int *nums, int numsSize, int lower, int upper) { - int n = numsSize; + qsort(nums, numsSize, sizeof(int), cmp); long long ans = 0; - qsort(nums, n, sizeof(int), cmp); - for (int i = 0; i < n - 1; i++) { - int left = bs_lower(nums, n, i + 1, n - 1, lower - nums[i]); - int right = bs_upper(nums, n, i + 1, n - 1, upper - nums[i]); - if (left != -1 && right != -1) - ans += right - left + 1; - } + int i = 0, j = numsSize - 1; + while (i < j) + if (nums[i] + nums[j] < lower) + ans -= j - i++; + else + j--; + i = 0, j = numsSize - 1; + while (i < j) + if (nums[i] + nums[j] <= upper) + ans += j - i++; + else + j--; return ans; } diff --git a/count_num_fair_pairs.py b/count_num_fair_pairs.py index 5933dbd..8d02562 100644 --- a/count_num_fair_pairs.py +++ b/count_num_fair_pairs.py @@ -19,9 +19,8 @@ class Solution(object): nums.sort() ans = 0 for i in range(len(nums) - 1, -1, -1): - v = nums[i] - a = bisect.bisect_left(nums, lower - v, lo=0, hi=i) - b = bisect.bisect_right(nums, upper - v, lo=0, hi=i) + a = bisect.bisect_left(nums, lower - nums[i], i + 1) + b = bisect.bisect_right(nums, upper - nums[i], i + 1) ans += b - a return ans diff --git a/count_num_good_subarr.c b/count_num_good_subarr.c new file mode 100644 index 0000000..40c20c4 --- /dev/null +++ b/count_num_good_subarr.c @@ -0,0 +1,94 @@ +// 2537. Count the Number of Good Subarrays +#include "leetcode.h" + +/* + * given an integer array 'nums' and an integer 'k', return the number of good + * subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs + * of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a + * contiguous non-empty sequence of elements within an array. + */ + +struct hash { + int *key; + int *val; + int size; +}; + +bool is_prime(int n) { + for (int i = 2; i < (int)sqrt(n) + 1; i++) + if (!(n % i)) + return false; + return true; +} + +struct hash *hash_init(int size) { + int max; + if (size < 8) + max = 11; + else { + max = size * 4 / 3; + int remove = (max - 3) % 4; + max += (remove > 0) * (4 - remove); + while (!is_prime(max)) + max += 4; + } + struct hash *new = (struct hash *)malloc(sizeof(struct hash)); + *new = (struct hash){(int *)calloc(max, sizeof(int)), + (int *)calloc(max, sizeof(int)), max}; + return new; +} + +void hash_free(struct hash *obj) { + free(obj->key); + free(obj->val); + free(obj); +} + +int hash_getidx(struct hash *obj, int key) { + int idx = key % obj->size; + while (obj->key[idx] > 0 && obj->key[idx] != key) + if (++idx == obj->size) + idx = 0; + obj->key[idx] = key; + return idx; +} + +int hash_getkey(struct hash *obj, int key) { + int idx = key % obj->size; + while (obj->key[idx] > 0) { + if (obj->key[idx] == key) + return idx; + if (++idx == obj->size) + idx = 0; + } + return -1; +} + +int hash_addkey(struct hash *obj, int key) { return hash_getidx(obj, key); } + +long long countGood(int *nums, int numsSize, int k) { + long long ans = 0; + int curr = 0; + struct hash *map = hash_init(numsSize); + for (int l = 0, r = 0; r < numsSize; r++) { + int i = hash_getkey(map, nums[r]); + if (i == -1) { + i = hash_addkey(map, nums[r]); + map->val[i] = 1; + } else + curr += map->val[i]++; + while (curr >= k) { + ans += numsSize - r; + curr -= --map->val[hash_getidx(map, nums[l])]; + l++; + } + } + hash_free(map); + return ans; +} + +int main() { + int n1[] = {1, 1, 1, 1, 1}, n2[] = {3, 1, 4, 3, 2, 2, 4}; + printf("%lld\n", countGood(n1, ARRAY_SIZE(n1), 10)); // expect: 1 + printf("%lld\n", countGood(n2, ARRAY_SIZE(n2), 2)); // expect: 4 +} diff --git a/count_num_good_subarr.py b/count_num_good_subarr.py new file mode 100644 index 0000000..69eedce --- /dev/null +++ b/count_num_good_subarr.py @@ -0,0 +1,35 @@ +# 2537. Count the Number of Good Subarrays +from collections import Counter + +""" +given an integer array 'nums' and an integer 'k', return the number of good +subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs +of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a +contiguous non-empty sequence of elements within an array. +""" + + +class Solution(object): + def countGood(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ans, i = 0, 0 + cnt = Counter() + for j in range(len(nums)): + k -= cnt[nums[j]] + cnt[nums[j]] += 1 + while k <= 0: + cnt[nums[i]] -= 1 + k += cnt[nums[i]] + i += 1 + ans += i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countGood(nums=[1, 1, 1, 1, 1], k=10)) + print(obj.countGood(nums=[3, 1, 4, 3, 2, 2, 4], k=2)) diff --git a/count_num_ideal_arr.c b/count_num_ideal_arr.c new file mode 100644 index 0000000..298b1da --- /dev/null +++ b/count_num_ideal_arr.c @@ -0,0 +1,36 @@ +// 2338. Count the Number of Ideal Arrays +#include "leetcode.h" + +/* + * you are given two integers 'n' and 'maxValue' which are used to describe an + * ideal array. a 0-indexed integer array 'arr' of length 'n' is considered + * ideal if the following conditions hold true: every 'arr[i]' is a value from 1 + * to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i - + * 1]'. return the number of distinct ideal arrays of length 'n'. since the + * answer may be very large, return it modulo 10^9+7. + */ + +int idealArrays(int n, int maxValue) { + int cmb[10001][14] = {1}, cnt[10001][14] = {}, mod = 1e9 + 7; + if (!cmb[1][1]) { + for (int i = 1; i <= 10000; ++i) + for (int j = 0; j < 14; ++j) + cmb[i][j] = !j ? 1 : (cmb[i - 1][j - 1] + cmb[i - 1][j]) % mod; + for (int i = 1; i <= 10000; ++i) { + ++cnt[i][0]; + for (int j = 2 * i; j <= 10000; j += i) + for (int k = 0; cnt[i][k]; ++k) + cnt[j][k + 1] += cnt[i][k]; + } + } + int ans = 0; + for (int i = 1; i <= maxValue; ++i) + for (int j = 0; j < fmin(14, n) && cnt[i][j]; ++j) + ans = (1LL * cnt[i][j] * cmb[n - 1][j] + ans) % mod; + return ans; +} + +int main() { + printf("%d\n", idealArrays(2, 5)); // expect: 10 + printf("%d\n", idealArrays(5, 3)); // expect: 11 +} diff --git a/count_num_ideal_arr.py b/count_num_ideal_arr.py new file mode 100644 index 0000000..6966711 --- /dev/null +++ b/count_num_ideal_arr.py @@ -0,0 +1,38 @@ +# 2338. Count the Number of Ideal Arrays +from collections import Counter +from math import comb + +""" +you are given two integers 'n' and 'maxValue' which are used to describe an +ideal array. a 0-indexed integer array 'arr' of length 'n' is considered +ideal if the following conditions hold true: every 'arr[i]' is a value from 1 +to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i - +1]'. return the number of distinct ideal arrays of length 'n'. since the +answer may be very large, return it modulo 10^9+7. +""" + + +class Solution(object): + def idealArrays(self, n, maxValue): + """ + :type n: int + :type maxValue: int + :rtype: int + """ + ans = maxValue + freq = {i: 1 for i in range(1, maxValue + 1)} + for i in range(1, n): + tmp = Counter() + for j in freq: + for k in range(2, maxValue // j + 1): + ans += comb(n - 1, i) * freq[j] + tmp[k * j] += freq[j] + freq = tmp + ans %= 10**9 + 7 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.idealArrays(n=2, maxValue=5)) + print(obj.idealArrays(n=5, maxValue=3)) diff --git a/max_product_len_palindrome_subseq.c b/max_product_len_palindrome_subseq.c new file mode 100644 index 0000000..b3e3a66 --- /dev/null +++ b/max_product_len_palindrome_subseq.c @@ -0,0 +1,46 @@ +// 2002. Maximum Product of the Length of Two Palindromic Subsequences +#include "leetcode.h" + +/* + * given a string 's', find two disjoint palindromic subsequences of 's' such + * that the product of their lengths is maximised. the two subsequences are + * disjoint if they do not both pick a character at the same index. return the + * maximum possible product of the lengths of the two palindromic subsequences. + * a subsequence is a string that can be derived from another string by deleting + * some or none of its characters without changing the ordering of the remaining + * characters. a string is palindromic if it reads the same forward and backward + */ + +int maxProduct(char *s) { + int n = strlen(s), *bits = (int *)calloc(1 << n, sizeof(int)); + for (int i = 1; i < 1 << n; i++) + bits[i] = bits[i >> 1] + (i & 1); + for (int i = (1 << n) - 1; i >= 0; i--) { + int l = 0, r = n - 1; + while (l < r) { + while (l < n && !(i & (1 << l))) + l++; + while (r >= 0 && !(i & (1 << r))) + r--; + if (l < r && s[l] != s[r]) { + bits[i] = 0; + break; + } + l++, r--; + } + } + int ans = 1; + for (int i = (1 << n) - 1; i > 0; i--) + if (bits[i]) + for (int j = (i + 1) & ~i; j < 1 << n; j = ((j | i) + 1) & ~i) + if (bits[j]) + ans = fmax(ans, bits[i] * bits[j]); + return ans; +} + +int main() { + char *s1 = "leetcodecom", *s2 = "bb", *s3 = "accbcaxxcxx"; + printf("%d\n", maxProduct(s1)); // expect: 9 + printf("%d\n", maxProduct(s2)); // expect: 1 + printf("%d\n", maxProduct(s3)); // expect: 25 +} diff --git a/max_product_len_palindrome_subseq.py b/max_product_len_palindrome_subseq.py new file mode 100644 index 0000000..52ecafc --- /dev/null +++ b/max_product_len_palindrome_subseq.py @@ -0,0 +1,46 @@ +# 2002. Maximum Product of the Length of Two Palindromic Subsequences + +""" +given a string 's', find two disjoint palindromic subsequences of 's' such +that the product of their lengths is maximised. the two subsequences are +disjoint if they do not both pick a character at the same index. return the +maximum possible product of the lengths of the two palindromic subsequences. +a subsequence is a string that can be derived from another string by deleting +some or none of its characters without changing the ordering of the remaining +characters. a string is palindromic if it reads the same forward and backward +""" + + +class Solution(object): + def maxProduct(self, s): + """ + :type s: str + :rtype: int + """ + n = len(s) + first, last = [0] * (1 << n), [0] * (1 << n) + for i in range(n): + for j in range(1 << i, 1 << (i + 1)): + first[j] = i + for i in range(n): + for j in range(1 << i, 1 << n, 1 << (i + 1)): + last[j] = i + + def dp(m): + if m & (m - 1) == 0: + return m != 0 + f, l = first[m], last[m] + fb, lb = 1 << f, 1 << l + return max(dp(m - lb), dp(m - fb), dp(m - lb - fb) + (s[l] == s[f]) * 2) + + ans = 0 + for i in range(1, 1 << n): + ans = max(ans, dp(i) * dp((1 << n) - 1 - i)) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxProduct(s="leetcodecom")) + print(obj.maxProduct(s="bb")) + print(obj.maxProduct(s="accbcaxxcxx")) diff --git a/rabbits_in_forest.c b/rabbits_in_forest.c new file mode 100644 index 0000000..caf618f --- /dev/null +++ b/rabbits_in_forest.c @@ -0,0 +1,36 @@ +// 781. Rabbits in Forest +#include "leetcode.h" + +/* + * there is a forest with an unknown number of rabbits. we asked 'n' rabbits + * "how many rabbithave the same colour as you?" and collected the answers in an + * integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit. + * given the array 'answers', return the minimum number of rabbits that could be + * in the forest. + */ + +int numRabbits(int *answers, int answersSize) { + int ans = 0; + for (int i = 0; i < answersSize - 1; i++) { + int freq = 0; + if (answers[i] != -1 && answers[i]) + for (int j = i + 1; j < answersSize; j++) { + if (answers[i] == answers[j]) { + answers[j] = -1; + freq++; + } + if (freq == answers[i]) + break; + } + } + for (int i = 0; i < answersSize; i++) + if (answers[i] != -1) + ans += (answers[i] + 1); + return ans; +} + +int main() { + int a1[] = {1, 1, 2}, a2[] = {10, 10, 10}; + printf("%d\n", numRabbits(a1, ARRAY_SIZE(a1))); // expect: 5 + printf("%d\n", numRabbits(a2, ARRAY_SIZE(a2))); // expect: 11 +} diff --git a/rabbits_in_forest.py b/rabbits_in_forest.py new file mode 100644 index 0000000..7d91e99 --- /dev/null +++ b/rabbits_in_forest.py @@ -0,0 +1,30 @@ +# 781. Rabbits in Forest +from collections import Counter + +""" +there is a forest with an unknown number of rabbits. we asked 'n' rabbits +"how many rabbithave the same colour as you?" and collected the answers in an +integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit. +given the array 'answers', return the minimum number of rabbits that could be +in the forest. +""" + + +class Solution(object): + def numRabbits(self, answers): + """ + :type answers: List[int] + :rtype: int + """ + ans, freq = 0, Counter() + for i in answers: + if freq[i] % (i + 1) == 0: + ans += i + 1 + freq[i] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.numRabbits(answers=[1, 1, 2])) + print(obj.numRabbits(answers=[10, 10, 10])) 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); +} diff --git a/substring_xor_queries.py b/substring_xor_queries.py new file mode 100644 index 0000000..4e40a1c --- /dev/null +++ b/substring_xor_queries.py @@ -0,0 +1,43 @@ +# 2564. Substring XOR Queries +from collections import defaultdict + +""" +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. +""" + + +class Solution(object): + def substringXorQueries(self, s, queries): + """ + :type s: str + :type queries: List[List[int]] + :rtype: List[List[int]] + """ + n = len(s) + vis = defaultdict(lambda: [-1, -1]) + for i in range(n - 1, -1, -1): + if s[i] == "0": + vis[0] = [i, i] + continue + curr = 0 + for j in range(i, n): + curr = curr * 2 + int(s[j]) + if curr > 2**32: + break + vis[curr] = [i, j] + return [vis[a ^ b] for b, a in queries] + + +if __name__ == "__main__": + obj = Solution() + print(obj.substringXorQueries(s="101101", queries=[[0, 5], [1, 2]])) + print(obj.substringXorQueries(s="0101", queries=[[12, 8]])) + print(obj.substringXorQueries(s="1", queries=[[4, 5]])) |