commit c8b9faa10b3c927f6e46964851629562d419fdda
parent 54acc06d144ad32abdb7e43a6ddc1f1d69a02545
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 21 Sep 2023 18:05:31 +0000
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 128 insertions(+), 0 deletions(-)
diff --git a/Problems/0004.cpp b/Problems/0004.cpp
@@ -0,0 +1,29 @@
+class Solution {
+ public:
+ double findMedianSortedArrays(const vector<int> &nums1, const vector<int> &nums2) {
+ const int n1 = nums1.size(), n2 = nums2.size(), n = n1 + n2;
+ if (n % 2)
+ return binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1);
+ else
+ return (binary(nums1, nums2, n / 2 - 1, 0, n1 - 1, 0, n2 - 1) +
+ binary(nums1, nums2, n / 2, 0, n1 - 1, 0, n2 - 1)) /
+ 2.0;
+ }
+
+ double binary(const vector<int> &nums1, const vector<int> &nums2, int k, int s1, int e1, int s2, int e2) {
+ if (s1 > e1) return nums2[k - s1];
+ if (s2 > e2) return nums1[k - s2];
+
+ const int m1 = s1 + (e1 - s1) / 2;
+ const int m2 = s2 + (e2 - s2) / 2;
+
+ if (m1 + m2 < k) {
+ return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, e1, m2 + 1, e2)
+ : binary(nums1, nums2, k, m1 + 1, e1, s2, e2);
+ } else {
+ return nums1[m1] > nums2[m2] ? binary(nums1, nums2, k, s1, m1 - 1, s2, e2)
+ : binary(nums1, nums2, k, s1, e1, s2, e2 - 1);
+ }
+ return -1;
+ }
+};
diff --git a/Problems/0922.cpp b/Problems/0922.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ int atMost(const vector<int> &nums, int k) {
+ static int seen[20001] = {0};
+ memset(seen, 0x00, sizeof(seen));
+
+ int res = 0, j = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ if (!seen[nums[i]]++) k--;
+ while (k < 0)
+ if (!--seen[nums[j++]]) k++;
+ res += i - j + 1;
+ }
+ return res;
+ }
+
+ public:
+ int subarraysWithKDistinct(const vector<int> &nums, int k) {
+ return atMost(nums, k) - atMost(nums, k - 1);
+ }
+};
diff --git a/Problems/1248.cpp b/Problems/1248.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ int atMost(const vector<int> &nums, int k) {
+ int res = 0, j = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ if (nums[i] % 2) k--;
+ while (k < 0)
+ if (nums[j++] % 2) k++;
+ res += i - j + 1;
+ }
+ return res;
+ }
+
+ public:
+ int numberOfSubarrays(const vector<int> &nums, int k) { return atMost(nums, k) - atMost(nums, k - 1); }
+};
diff --git a/Problems/1578.cpp b/Problems/1578.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ public:
+ int minCost(const string &colors, const vector<int> &neededTime) {
+ int res = 0, prev = neededTime[0];
+ for (int i = 1; i < colors.size(); i++) {
+ if (colors[i] != colors[i - 1]) {
+ prev = neededTime[i];
+ continue;
+ }
+ if (neededTime[i] < prev)
+ res += neededTime[i];
+ else {
+ res += prev;
+ prev = neededTime[i];
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/1664.cpp b/Problems/1664.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ public:
+ int waysToMakeFair(const vector<int> &nums) {
+ const int n = nums.size();
+ int sodd = 0, seven = 0;
+ for (int i = n - 1; i >= 0; i--)
+ (i % 2 ? sodd : seven) += nums[i];
+
+ int res = 0;
+ for (int i = 0, odd = 0, even = 0; i < n; i++) {
+ const int codd = odd + seven - even + (i % 2 ? nums[i] : 0);
+ const int ceven = even + sodd - odd + (i % 2 ? 0 : nums[i]);
+ if (codd == ceven) res++;
+ (i % 2 ? odd : even) += nums[i];
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1781.cpp b/Problems/1781.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ int beautySum(const string &s) {
+ int res = 0;
+ for (auto i = 0; i < s.size(); i++) {
+ int cnt[27] = {0}, maxi = 0, mini = 0;
+ for (auto j = i; j < s.size(); j++) {
+ const int idx = s[j] & 0x1F;
+ maxi = max(maxi, ++cnt[idx]);
+ if (mini >= cnt[idx] - 1) {
+ mini = cnt[idx];
+ for (int k = 1; k <= 26; ++k)
+ mini = min(mini, cnt[k] == 0 ? INT_MAX : cnt[k]);
+ }
+ res += maxi - mini;
+ }
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -28,6 +28,7 @@ for solving problems.
| 0001 | Easy | [Two Sum](Problems/0001.cpp) |
| 0002 | Medium | [Add Two Numbers](Problems/0002.cpp) |
| 0003 | Medium | [Longest Substring Without Repeating Characters](Problems/0003.cpp) |
+| 0004 | Hard | [Median of Two Sorted Arrays](Problems/0004.cpp) |
| 0005 | Medium | [Longest Palindromic Substring](Problems/0005.cpp) |
| 0006 | Medium | [Zigzag Conversion](Problems/0006.cpp) |
| 0007 | Medium | [Reverse Integer](Problems/0007.cpp) |
@@ -463,6 +464,7 @@ for solving problems.
| 0986 | Medium | [Interval List Intersections](Problems/0986.cpp) |
| 0989 | Easy | [Add to Array-Form of Integer](Problems/0989.cpp) |
| 0990 | Medium | [Satisfiability of Equality Equations](Problems/0990.cpp) |
+| 0992 | Hard | [Subarrays with K Different Integers](Problems/0992.cpp) |
| 0993 | Easy | [Cousins in Binary Tree](Problems/0993.cpp) |
| 0994 | Medium | [Rotting Oranges](Problems/0994.cpp) |
| 0997 | Easy | [Find the Town Judge](Problems/0997.cpp) |
@@ -519,6 +521,7 @@ for solving problems.
| 1233 | Medium | [Remove Sub-Folders from the Filesystem](Problems/1233.cpp) |
| 1237 | Medium | [Find Positive Integer Solution for a Given Equation](Problems/1237.cpp) |
| 1247 | Medium | [Minimum Swaps to Make Strings Equal](Problems/1247.cpp) |
+| 1248 | Medium | [Count Number of Nice Subarrays](Problems/1248.cpp) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |
| 1261 | Medium | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp) |
@@ -617,6 +620,7 @@ for solving problems.
| 1569 | Hard | [Number of Ways to Reorder Array to Get Same BST](Problems/1569.cpp) |
| 1572 | Easy | [Matrix Diagonal Sum](Problems/1572.cpp) |
| 1575 | Medium | [Count All Possible Routes](Problems/1575.cpp) |
+| 1578 | Medium | [Minimum Time to Make Rope Colorful](Problems/1578.cpp) |
| 1579 | Hard | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp) |
| 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |
| 1600 | Medium | [Throne Inheritance](Problems/1600.cpp) |
@@ -638,6 +642,7 @@ for solving problems.
| 1657 | Medium | [Determine if Two Strings Are Close](Problems/1657.cpp) |
| 1658 | Medium | [Minimum Operations to Reduce X to Zero](Problems/1658.cpp) |
| 1663 | Medium | [Smallest String With A Given Numeric Value](Problems/1663.cpp) |
+| 1664 | Medium | [Ways to Make a Fair Array](Problems/1664.cpp) |
| 1669 | Medium | [Merge In Between Linked Lists](Problems/1669.cpp) |
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
| 1675 | Hard | [Minimize Deviation in Array](Problems/1675.cpp) |
@@ -658,6 +663,7 @@ for solving problems.
| 1768 | Easy | [Merge Strings Alternately](Problems/1768.cpp) |
| 1769 | Medium | [Minimum Number of Operations to Move All Balls to Each Box](Problems/1769.cpp) |
| 1780 | Medium | [Check if Number is a Sum of Powers of Three](Problems/1780.cpp) |
+| 1781 | Medium | [Sum of Beauty of All Substrings](Problems/1781.cpp) |
| 1786 | Medium | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp) |
| 1791 | Easy | [Find Center of Star Graph](Problems/1791.cpp) |
| 1799 | Medium | [Maximize Score After N Operations](Problems/1799.cpp) |
