diff options
-rw-r--r-- | count_subarr_max_elem_k.c | 20 | ||||
-rw-r--r-- | count_subarr_max_elem_k.py | 16 | ||||
-rw-r--r-- | count_subarr_score_less_k.c | 26 | ||||
-rw-r--r-- | count_subarr_score_less_k.py | 31 | ||||
-rw-r--r-- | find_num_even_digit.c | 27 | ||||
-rw-r--r-- | find_num_even_digit.py | 21 | ||||
-rw-r--r-- | max_num_tasks_assign.py | 64 | ||||
-rw-r--r-- | min_ops_make_int_zero.c | 36 | ||||
-rw-r--r-- | min_ops_make_int_zero.py | 39 |
9 files changed, 260 insertions, 20 deletions
diff --git a/count_subarr_max_elem_k.c b/count_subarr_max_elem_k.c index e6bf5ad..4768843 100644 --- a/count_subarr_max_elem_k.c +++ b/count_subarr_max_elem_k.c @@ -9,19 +9,15 @@ */ long long countSubarrays(int *nums, int numsSize, int k) { - int max = 0, cnt = 0, idx[numsSize]; + int max = -1, curr = 0; long long ans = 0; - for (int i = 0; i < numsSize; i++) - max = max > nums[i]; - for (int i = 0; i < numsSize; i++) - if (nums[i] == max) - idx[cnt++] = i; - for (int i = 0; i <= cnt - k; i++) { - long long left = idx[i], right = idx[i + k - 1], - bound = i - 1 >= 0 ? idx[i - 1] : -1; - if (!i) - bound = -1; - ans += (left - bound) * (numsSize - right); + for (int i = 0; i < numsSize; ++i) + max = nums[i] > max ? nums[i] : max; + for (int l = 0, r = 0; r < numsSize; r++) { + curr += nums[r] == max; + while (curr >= k) + curr -= nums[l++] == max; + ans += l; } return ans; } diff --git a/count_subarr_max_elem_k.py b/count_subarr_max_elem_k.py index 8f734f2..7852d49 100644 --- a/count_subarr_max_elem_k.py +++ b/count_subarr_max_elem_k.py @@ -15,18 +15,18 @@ class Solution(object): :type k: int :rtype: int """ + ans, curr, l = 0, 0, 0 m = max(nums) - ans, curr, i = 0, 0, 0 - for j in range(len(nums)): - curr += nums[j] == m + for r in range(len(nums)): + curr += nums[r] == m while curr >= k: - curr -= nums[i] == m - i += 1 - ans += i + curr -= nums[l] == m + l += 1 + ans += l return ans if __name__ == "__main__": obj = Solution() - print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2)) # expect: 6 - print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3)) # expect: 0 + print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2)) + print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3)) diff --git a/count_subarr_score_less_k.c b/count_subarr_score_less_k.c new file mode 100644 index 0000000..5c454d1 --- /dev/null +++ b/count_subarr_score_less_k.c @@ -0,0 +1,26 @@ +// 2302. Count Subarrays With Score Less Than K +#include "leetcode.h" + +/* + * the score of an array is defined as the product of its sum and its length. + * given a positive integer array 'nums' and an integer 'k', return the number + * of non-empty subarrays of 'nums' whose score is strictly less than 'k'. a + * subarray is a contiguous sequence of elements within an array. + */ + +long long countSubarrays(int *nums, int numsSize, long long k) { + long long ans = 0, curr = 0; + for (int j = 0, i = 0; j < numsSize; ++j) { + curr += nums[j]; + while (curr * (j - i + 1) >= k) + curr -= nums[i++]; + ans += j - i + 1; + } + return ans; +} + +int main() { + int n1[] = {2, 1, 4, 3, 5}, n2[] = {1, 1, 1}; + printf("%lld\n", countSubarrays(n1, ARRAY_SIZE(n1), 10)); // expect: 6 + printf("%lld\n", countSubarrays(n2, ARRAY_SIZE(n2), 5)); // expect: 5 +} diff --git a/count_subarr_score_less_k.py b/count_subarr_score_less_k.py new file mode 100644 index 0000000..d60cb4b --- /dev/null +++ b/count_subarr_score_less_k.py @@ -0,0 +1,31 @@ +# 2302. Count Subarrays With Score Less Than K + +""" +the score of an array is defined as the product of its sum and its length. +given a positive integer array 'nums' and an integer 'k', return the number +of non-empty subarrays of 'nums' whose score is strictly less than 'k'. a +subarray is a contiguous sequence of elements within an array. +""" + + +class Solution(object): + def countSubarrays(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ans, curr, i = 0, 0, 0 + for j in range(len(nums)): + curr += nums[j] + while curr * (j - i + 1) >= k: + curr -= nums[i] + i += 1 + ans += j - i + 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countSubarrays(nums=[2, 1, 4, 3, 5], k=10)) + print(obj.countSubarrays(nums=[1, 1, 1], k=5)) diff --git a/find_num_even_digit.c b/find_num_even_digit.c new file mode 100644 index 0000000..351896f --- /dev/null +++ b/find_num_even_digit.c @@ -0,0 +1,27 @@ +// 1295. Find Numbers with Even Number of Digits +#include "leetcode.h" + +/* + * given an array 'nums' of integers, return how many of them contain an even + * number of digits. + */ + +int findNumbers(int *nums, int numsSize) { + int cnt = 0; + for (int i = 0; i < numsSize; i++) { + int curr = 0; + while (nums[i]) { + curr++; + nums[i] /= 10; + } + if (!(curr & 1)) + cnt++; + } + return cnt; +} + +int main() { + int n1[] = {12, 345, 2, 6, 7896}, n2[] = {555, 901, 482, 1771}; + printf("%d\n", findNumbers(n1, ARRAY_SIZE(n1))); // expect: 2 + printf("%d\n", findNumbers(n2, ARRAY_SIZE(n2))); // expect: 1 +} diff --git a/find_num_even_digit.py b/find_num_even_digit.py new file mode 100644 index 0000000..5cdb9e3 --- /dev/null +++ b/find_num_even_digit.py @@ -0,0 +1,21 @@ +# 1295. Find Numbers with Even Number of Digits + +""" +given an array 'nums' of integers, return how many of them contain an even +number of digits. +""" + + +class Solution(object): + def findNumbers(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + return sum(1 for i in nums if (len(str(i)) & 1) == 0) + + +if __name__ == "__main__": + obj = Solution() + print(obj.findNumbers(nums=[12, 345, 2, 6, 7896])) + print(obj.findNumbers(nums=[555, 901, 482, 1771])) diff --git a/max_num_tasks_assign.py b/max_num_tasks_assign.py new file mode 100644 index 0000000..4c2fbf5 --- /dev/null +++ b/max_num_tasks_assign.py @@ -0,0 +1,64 @@ +# 2071. Maximum Number of Tasks You Can Assign +from bisect import bisect_left + +""" +you have 'n' tasks and 'm' workers. each task has a strength requirement +stored in a 0-indexed integer array 'tasks', with the i'th task requiring +'tasks[i]' strength to complete. the strength of each worker is stored in a +0-indexed array 'workers' with the j'th worker having 'workers[j]' strength. +each worker can only be assigned to a single task and must have a strength +greather than or equal to the task's strength requirement. additionally, you +have 'pills' magic pills that will increase a workers strength by 'strength'. +you can decide which workers receive the pills, however, you may only give +each worker at most one magical pill. given the 0-indexed integer arrays +'tasks' and 'workers' and the integers 'pills' and 'strength', return the +maximum number of tasks that can be completed. +""" + + +class Solution(object): + def maxTaskAssign(self, tasks, workers, pills, strength): + """ + :type tasks: List[int] + :type workers: List[int] + :type pills: int + :type strength: int + :rtype: int + """ + + def check(k): + w, tries = workers[-k:], pills + for i in tasks[:k][::-1]: + idx = bisect_left(w, i) + if idx < len(w): + w.pop(idx) + elif tries > 0: + idx = bisect_left(w, i - strength) + if idx < len(w): + w.pop(idx) + tries -= 1 + else: + return False + return len(w) == 0 + + tasks = sorted(tasks) + workers = sorted(workers) + l, r = 0, min(len(workers), len(tasks)) + 1 + while l + 1 < r: + m = l + (r - l) // 2 + if check(m): + l = m + else: + r = m + return l + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxTaskAssign(tasks=[3, 2, 1], workers=[0, 3, 3], pills=1, strength=1)) + print(obj.maxTaskAssign(tasks=[5, 4], workers=[0, 0, 0], pills=1, strength=5)) + print( + obj.maxTaskAssign( + tasks=[10, 15, 30], workers=[0, 10, 10, 10, 10], pills=3, strength=10 + ) + ) diff --git a/min_ops_make_int_zero.c b/min_ops_make_int_zero.c new file mode 100644 index 0000000..95d7255 --- /dev/null +++ b/min_ops_make_int_zero.c @@ -0,0 +1,36 @@ +// 2749. Minimum Operations to Make the Integer Zero +#include "leetcode.h" + +/* + * you are given two integers 'nums1' and 'nums2'. in one operation you can + * choose integer 'i' in the range '[0, 60]' and subtract '2^i + num2' from + * 'num1'. return the integer denoting the minimum number of operations needed + * to make 'nums1' equal to 0. if it is impossible to make 'nums1' equal to 0, + * return -1. + */ + +int bit_cnt(long long num) { + int cnt = 0; + while (num > 0) { + cnt += num & 1; + num >>= 1; + } + return cnt; +} + +int makeTheIntegerZero(int num1, int num2) { + if (num1 < num2) + return -1; + for (int i = 0; i <= 100; i++) { + long long diff = num1 - 1LL * num2 * i; + int bits = bit_cnt(diff); + if (bits <= i && i <= diff) + return i; + } + return -1; +} + +int main() { + printf("%d\n", makeTheIntegerZero(3, -2)); // expect: 3 + printf("%d\n", makeTheIntegerZero(5, 7)); // expect: -1 +} diff --git a/min_ops_make_int_zero.py b/min_ops_make_int_zero.py new file mode 100644 index 0000000..096921a --- /dev/null +++ b/min_ops_make_int_zero.py @@ -0,0 +1,39 @@ +# 2749. Minimum Operations to Make the Integer Zero + +""" +you are given two integers 'nums1' and 'nums2'. in one operation you can +choose integer 'i' in the range '[0, 60]' and subtract '2^i + num2' from +'num1'. return the integer denoting the minimum number of operations needed +to make 'nums1' equal to 0. if it is impossible to make 'nums1' equal to 0, +return -1. +""" + + +class Solution(object): + def bit_cnt(self, num): + cnt = 0 + while num > 0: + cnt += num & 1 + num >>= 1 + return cnt + + def makeTheIntegerZero(self, num1, num2): + """ + :type num1: int + :type num2: int + :rtype: int + """ + if num1 < num2: + return -1 + for i in range(101): + diff = num1 - 1 * num2 * i + bits = self.bit_cnt(diff) + if bits <= i and i <= diff: + return i + return -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.makeTheIntegerZero(num1=3, num2=-2)) + print(obj.makeTheIntegerZero(num1=5, num2=7)) |