diff options
-rw-r--r-- | count_num_arr_k_match_elem.c | 48 | ||||
-rw-r--r-- | count_num_arr_k_match_elem.py | 28 | ||||
-rw-r--r-- | divide_array_max_diff.c | 69 | ||||
-rw-r--r-- | divide_array_max_diff.py | 17 | ||||
-rw-r--r-- | partition_arr_max_diff_k.c | 32 | ||||
-rw-r--r-- | partition_arr_max_diff_k.py | 34 |
6 files changed, 205 insertions, 23 deletions
diff --git a/count_num_arr_k_match_elem.c b/count_num_arr_k_match_elem.c new file mode 100644 index 0000000..dd8838e --- /dev/null +++ b/count_num_arr_k_match_elem.c @@ -0,0 +1,48 @@ +// 3405. Count the Number of Arrays with K Matching Adjacent Elements +#include "leetcode.h" + +/* + * you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size + * 'n' is defined as follows: each element in 'arr' is in inclusive range '[1, + * m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition + * 'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. + * since the answer may be very large, return it modulo 10^9+7. + */ + +const int mod = 1e9 + 7; + +long long mult(long long n, long long m) { return (n * m) % mod; } + +long long power(long long n, long long m) { + long long res = 1, base = n; + while (m > 0) { + if (m & 1) + res = mult(res, base); + base = mult(base, base); + m >>= 1; + } + return res; +} + +long long inv(long long n) { return power(n, mod - 2); } + +long long factorial(long long n) { + long long res = 1; + for (long long i = 2; i <= n; ++i) + res = mult(res, i); + return res; +} + +long long combine(long long n, long long m) { + return mult(factorial(n), inv(mult(factorial(m), factorial(n - m)))); +} + +int countGoodArrays(int n, int m, int k) { + return mult(mult(combine(n - 1, n - 1 - k), m), power(m - 1, n - 1 - k)); +} + +int main() { + printf("%d\n", countGoodArrays(3, 2, 1)); // expect: 4 + printf("%d\n", countGoodArrays(4, 2, 2)); // expect: 6 + printf("%d\n", countGoodArrays(5, 2, 0)); // expect: 2 +} diff --git a/count_num_arr_k_match_elem.py b/count_num_arr_k_match_elem.py new file mode 100644 index 0000000..a3bc73f --- /dev/null +++ b/count_num_arr_k_match_elem.py @@ -0,0 +1,28 @@ +# 3405. Count the Number of Arrays with K Matching Adjacent Elements +from math import comb + +""" +you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size +'n' is defined as follows: each element in 'arr' is in inclusive range '[1, +m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition +'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. +since the answer may be very large, return it modulo 10^9+7. +""" + + +class Solution(object): + def countGoodArrays(self, n, m, k): + """ + :type n: int + :type m: int + :type k: int + :rtype: int + """ + return m * pow(m - 1, n - k - 1, mod := 1**9 + 7) * comb(n - 1, k) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.countGoodArrays(n=3, m=2, k=1)) + print(obj.countGoodArrays(n=4, m=2, k=2)) + print(obj.countGoodArrays(n=5, m=2, k=0)) diff --git a/divide_array_max_diff.c b/divide_array_max_diff.c index 72e8648..8c510b3 100644 --- a/divide_array_max_diff.c +++ b/divide_array_max_diff.c @@ -11,25 +11,66 @@ * return any of them */ -int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); } +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int **divideArray(int *nums, int numsSize, int k, int *returnSize, int **returnColumnSizes) { - int num_arr = numsSize / 3; - int **ans = (int **)calloc(num_arr, sizeof(int *)); - *returnColumnSizes = (int *)calloc(num_arr, sizeof(int)); - *returnSize = 0; qsort(nums, numsSize, sizeof(int), cmp); - for (int i = 0; i < num_arr; i++) { - ans[i] = (int *)calloc(3, sizeof(int)); - (*returnColumnSizes)[i] = 3; - for (int j = 0; j < 3; j++) { - int idx = i * 3 + j; - if (j && nums[idx] - nums[i * 3] > k) - return ans; - ans[i][j] = nums[idx]; + int **ans = (int **)malloc((numsSize / 3) * sizeof(int *)), rs = 0; + for (int i = 2; i < numsSize; i += 3) { + if (nums[i] - nums[i - 2] > k) { + *returnSize = 0; + return NULL; } + ans[rs] = (int *)malloc(3 * sizeof(int)); + ans[rs][0] = nums[i - 2]; + ans[rs][1] = nums[i - 1]; + ans[rs][2] = nums[i]; + rs++; } - *returnSize = num_arr; + *returnSize = rs; + *returnColumnSizes = (int *)malloc(rs * sizeof(int)); + for (int i = 0; i < rs; i++) + (*returnColumnSizes)[i] = 3; return ans; } + +int main() { + int n1[] = {1, 3, 4, 8, 7, 9, 3, 5, 1}, rs1, *rcs1; + int n2[] = {2, 4, 2, 2, 5, 2}, rs2, *rcs2; + int n3[] = {4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11}, rs3, + *rcs3; + int **da1 = divideArray(n1, ARRAY_SIZE(n1), 2, &rs1, &rcs1); + int **da2 = divideArray(n2, ARRAY_SIZE(n2), 2, &rs2, &rcs2); + int **da3 = divideArray(n3, ARRAY_SIZE(n3), 14, &rs3, &rcs3); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", da1[i][j]); // expect: [[1,1,3],[3,4,5],[7,8,9]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", da2[i][j]); // expect: null + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs3; i++) { + for (int j = 0; j < rcs3[i]; j++) + printf( + "%d ", + da3[i][j]); // expect: + // [[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(da1[i]), free(rcs1); + free(da1); + for (int i = 0; i < rs2; i++) + free(da2[i]), free(rcs2); + free(da1); + for (int i = 0; i < rs3; i++) + free(da3[i]), free(rcs3); + free(da1); +} diff --git a/divide_array_max_diff.py b/divide_array_max_diff.py index 41a2a22..3bdf682 100644 --- a/divide_array_max_diff.py +++ b/divide_array_max_diff.py @@ -18,18 +18,12 @@ class Solution(object): :type k: int :rtype: List[List[int]] """ - size = len(nums) - if size % 3 != 0: - return [] nums.sort() ans = [] - group_idx = 0 - for i in range(0, size, 3): - if i + 2 < size and nums[i + 2] - nums[i] <= k: - ans.append([nums[i], nums[i + 1], nums[i + 2]]) - group_idx += 1 - else: + for i in range(2, len(nums), 3): + if nums[i] - nums[i - 2] > k: return [] + ans.append([nums[i - 2], nums[i - 1], nums[i]]) return ans @@ -37,3 +31,8 @@ if __name__ == "__main__": obj = Solution() print(obj.divideArray(nums=[1, 3, 4, 8, 7, 9, 3, 5, 1], k=2)) print(obj.divideArray(nums=[1, 3, 3, 2, 7, 3], k=3)) + print( + obj.divideArray( + nums=[4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11], k=14 + ) + ) diff --git a/partition_arr_max_diff_k.c b/partition_arr_max_diff_k.c new file mode 100644 index 0000000..4a1e3aa --- /dev/null +++ b/partition_arr_max_diff_k.c @@ -0,0 +1,32 @@ +// 2294. Partition Array Such That Maximum Difference Is K +#include "leetcode.h" + +/* + * you are given an integer array 'nums' and an integer 'k'. you may partition + * 'nums' into one or more subsequences such that each element in 'nums' appears + * in exactly one of the subsequences. return the minimum number of subsequences + * needed such that the difference between the maximum and minimum values in + * each subsequence is at most 'k'. a subsequence is a sequence that can be + * derived from another sequence by deleting some or no elements without + * changing the order of the remaining elements. + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +int partitionArray(int *nums, int numsSize, int k) { + qsort(nums, numsSize, sizeof(int), cmp); + int ans = 1, j = 0; + for (int i = 1; i < numsSize; i++) + if (nums[i] - nums[j] > k) { + ans++; + j = i; + } + return ans; +} + +int main() { + int n1[] = {3, 6, 1, 2, 5}, n2[] = {1, 2, 3}, n3[] = {2, 2, 4, 5}; + printf("%d\n", partitionArray(n1, ARRAY_SIZE(n1), 2)); // expect: 2 + printf("%d\n", partitionArray(n2, ARRAY_SIZE(n2), 1)); // expect: 2 + printf("%d\n", partitionArray(n3, ARRAY_SIZE(n3), 0)); // expect: 3 +} diff --git a/partition_arr_max_diff_k.py b/partition_arr_max_diff_k.py new file mode 100644 index 0000000..555cdf9 --- /dev/null +++ b/partition_arr_max_diff_k.py @@ -0,0 +1,34 @@ +# 2294. Partition Array Such That Maximum Difference Is K + +""" +you are given an integer array 'nums' and an integer 'k'. you may partition +'nums' into one or more subsequences such that each element in 'nums' appears +in exactly one of the subsequences. return the minimum number of subsequences +needed such that the difference between the maximum and minimum values in +each subsequence is at most 'k'. a subsequence is a sequence that can be +derived from another sequence by deleting some or no elements without +changing the order of the remaining elements. +""" + + +class Solution(object): + def partitionArray(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + nums.sort() + ans, j = 1, 0 + for i in range(len(nums)): + if nums[i] - nums[j] > k: + ans += 1 + j = i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.partitionArray(nums=[3, 6, 1, 2, 5], k=2)) + print(obj.partitionArray(nums=[1, 2, 3], k=1)) + print(obj.partitionArray(nums=[2, 2, 4, 5], k=0)) |