commit 013369eedc52341ac18f47bf0d31613b7c9c35e4
parent 67c9967c0b935971bc4c330ad95cb06c4f0e67ec
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 19 Nov 2023 23:26:02 +0000
2 Random Problems
Diffstat:
3 files changed, 63 insertions(+), 1 deletion(-)
diff --git a/Problems/1003.cpp b/Problems/1003.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ bool isValid(const string &s) const {
+ static char st[20001];
+ int n = 0;
+ for (const char c : s) {
+ if (c != 'c')
+ st[n++] = c;
+ else {
+ if (n < 2) return false;
+ if (st[n - 1] != 'b') return false;
+ if (st[n - 2] != 'a') return false;
+ n -= 2;
+ }
+ }
+ return n == 0;
+ }
+};
diff --git a/Problems/1838.cpp b/Problems/1838.cpp
@@ -0,0 +1,43 @@
+static const auto _ = [] {
+ cin.tie(0);
+ ios::sync_with_stdio(0);
+ return 0;
+}();
+class Solution {
+ public:
+ int maxFrequency(vector<int> &nums, int k) const {
+ static long long prefix[100001];
+ const int n = nums.size();
+
+ memset(prefix, 0x00, sizeof(prefix));
+ for (int i = 0; i < n; i++)
+ prefix[nums[i]]++;
+
+ for (int i = 0, j = 0; i <= 100000; i++) {
+ while (prefix[i] > 0) {
+ nums[j++] = i, prefix[i]--;
+ }
+ }
+
+ prefix[0] = 0;
+ for (int i = 1; i < n; i++)
+ prefix[i] = nums[i - 1] + prefix[i - 1];
+
+ int res = 0;
+ for (int crnt = 0; crnt < n; crnt++) {
+ int low = 0, high = crnt - 1;
+ while (low <= high) {
+ const int mid = low + (high - low) / 2;
+ const long long left = crnt - mid;
+ const long long sum = prefix[crnt] - prefix[mid];
+ if (left * nums[crnt] - sum <= k)
+ high = mid - 1;
+ else
+ low = mid + 1;
+ }
+ res = max(res, crnt - high);
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -25,7 +25,6 @@ for solving problems.
| Number | Difficulty | Solution |
|:------:|:----------:|----------------------------------------------------------------------------------------------------|
-| 0000 | Medium | [](Problems/0000.cpp) |
| 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) |
@@ -497,6 +496,7 @@ for solving problems.
| 0994 | Medium | [Rotting Oranges](Problems/0994.cpp) |
| 0997 | Easy | [Find the Town Judge](Problems/0997.cpp) |
| 0998 | Medium | [Maximum Binary Tree II](Problems/0998.cpp) |
+| 1003 | Medium | [Check If Word Is Valid After Substitutions](Problems/1003.cpp) |
| 1004 | Medium | [Max Consecutive Ones III](Problems/1004.cpp) |
| 1008 | Medium | [Construct Binary Search Tree from Preorder Traversal](Problems/1008.cpp) |
| 1011 | Medium | [Capacity To Ship Packages Within D Days](Problems/1011.cpp) |
@@ -742,6 +742,7 @@ for solving problems.
| 1829 | Medium | [Maximum XOR for Each Query](Problems/1829.cpp) |
| 1833 | Medium | [Maximum Ice Cream Bars](Problems/1833.cpp) |
| 1834 | Medium | [Single-Threaded CPU](Problems/1834.cpp) |
+| 1838 | Medium | [Frequency of the Most Frequent Element](Problems/1838.cpp) |
| 1845 | Medium | [Seat Reservation Manager](Problems/1845.cpp) |
| 1846 | Medium | [Maximum Element After Decreasing and Rearranging](Problems/1846.cpp) |
| 1850 | Medium | [Minimum Adjacent Swaps to Reach the Kth Smallest Number](Problems/1850.cpp) |
