commit 295259ef940d3588a7933f524438680fab828f61
parent c35d611a2230cbf4ee0da919689d3aface3301f5
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 29 Oct 2024 16:39:18 +0100
1 Daily Problem, 2 Random
Diffstat:
4 files changed, 133 insertions(+), 0 deletions(-)
diff --git a/Problems/0321.cpp b/Problems/0321.cpp
@@ -0,0 +1,43 @@
+class Solution {
+ static bool greater(const vector<int> &nums1, const vector<int> &nums2, int i, int j) {
+ while (i < size(nums1) && j < size(nums2) && nums1[i] == nums2[j])
+ i++, j++;
+ return j == size(nums2) || (i < size(nums1) && nums1[i] > nums2[j]);
+ }
+
+ static vector<int> merge(const vector<int> &nums1, const vector<int> &nums2, int k) {
+ vector<int> res(k);
+
+ for (int i = 0, j = 0, l = 0; l < k; l++) {
+ res[l] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];
+ }
+
+ return res;
+ }
+
+ static vector<int> maxArr(const vector<int> &nums, int k) {
+ const int n = size(nums);
+ vector<int> res(k);
+
+ for (int i = 0, j = 0; i < n; i++) {
+ while (n - i + j > k && j > 0 && res[j - 1] < nums[i])
+ j--;
+ if (j < k) res[j++] = nums[i];
+ }
+
+ return res;
+ }
+
+ public:
+ vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2, int k) const {
+ const int n = size(nums1), m = size(nums2);
+ vector<int> res(k);
+
+ for (int i = max(0, k - m); i <= k && i <= n; i++) {
+ const auto candid = merge(maxArr(nums1, i), maxArr(nums2, k - i), k);
+ res = max(res, candid);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0715.cpp b/Problems/0715.cpp
@@ -0,0 +1,66 @@
+class SegmentTree {
+ struct Node {
+ Node *left = nullptr;
+ Node *right = nullptr;
+ int low;
+ int high;
+ int value;
+
+ Node(int low, int high, int value) : low(low), high(high), value(value) {}
+ } root;
+
+ void update(Node *root, int l, int r, int val) {
+ if (root->low == l && root->high == r) {
+ root->value = val;
+ root->left = root->right = NULL; // memory leak;
+ return;
+ }
+
+ const int mid = root->low + (root->high - root->low) / 2;
+
+ if (!root->left) {
+ root->left = new Node(root->low, mid, root->value);
+ root->right = new Node(mid + 1, root->high, root->value);
+ }
+
+ if (r <= mid)
+ update(root->left, l, r, val);
+ else if (l > mid)
+ update(root->right, l, r, val);
+ else
+ update(root->left, l, mid, val), update(root->right, mid + 1, r, val);
+ root->value = root->left->value && root->right->value;
+ }
+
+ bool query(const Node *root, int l, int r) const {
+ if (!root->left) return root->value;
+ if (root->low == l && root->high == r) return root->value;
+
+ const int mid = root->low + (root->high - root->low) / 2;
+
+ if (r <= mid)
+ return query(root->left, l, r);
+ else if (l > mid)
+ return query(root->right, l, r);
+ return query(root->left, l, mid) && query(root->right, mid + 1, r);
+ }
+
+ public:
+ SegmentTree(int l, int r, int val) : root(l, r, val) {}
+
+ void update(int l, int r, int val) { return update(&root, l, r, val); }
+ bool query(int l, int r) const { return query(&root, l, r); }
+};
+
+class RangeModule {
+ SegmentTree seg;
+
+ public:
+ RangeModule() : seg(0, 1e9, 0) {}
+
+ void addRange(int left, int right) { seg.update(left, right - 1, 1); }
+
+ bool queryRange(int left, int right) { return seg.query(left, right - 1); }
+
+ void removeRange(int left, int right) { seg.update(left, right - 1, 0); }
+};
diff --git a/Problems/2684.cpp b/Problems/2684.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ int maxMoves(const vector<vector<int>> &grid) const {
+ const int n = size(grid), m = size(grid[0]);
+ static int dp[1001];
+
+ memset(dp, 0x00, sizeof(dp));
+ for (int j = m - 2; j >= 0; j--) {
+ for (int i = 0, prev; i < n; i++) {
+ int crnt = 0;
+ if (i > 0 && grid[i][j] < grid[i - 1][j + 1]) crnt = max(crnt, prev + 1);
+ if (grid[i][j] < grid[i][j + 1]) crnt = max(crnt, dp[i] + 1);
+ if (i < n - 1 && grid[i][j] < grid[i + 1][j + 1]) crnt = max(crnt, dp[i + 1] + 1);
+ prev = dp[i];
+ dp[i] = crnt;
+ }
+ }
+
+ return *max_element(dp, dp + n);
+ }
+};
diff --git a/README.md b/README.md
@@ -296,6 +296,7 @@ reference and a base for solving problems.
| 0316 | Medium | [Remove Duplicate Letters](Problems/0316.cpp) |
| 0318 | Medium | [Maximum Product of Word Lengths](Problems/0318.cpp) |
| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
+| 0321 | Hard | [Create Maximum Number](Problems/0321.cpp) |
| 0322 | Medium | [Coin Change](Problems/0322.cpp) |
| 0326 | Easy | [Power of Three](Problems/0326.cpp) |
| 0327 | Hard | [Count of Range Sum](Problems/0327.cpp) |
@@ -512,6 +513,7 @@ reference and a base for solving problems.
| 0712 | Medium | [Minimum ASCII Delete Sum for Two Strings](Problems/0712.cpp) |
| 0713 | Medium | [Subarray Product Less Than K](Problems/0713.cpp) |
| 0714 | Medium | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp) |
+| 0715 | Hard | [Range Module](Problems/0715.cpp) |
| 0718 | Medium | [Maximum Length of Repeated Subarray](Problems/0718.cpp) |
| 0719 | Hard | [Find K-th Smallest Pair Distance](Problems/0719.cpp) |
| 0720 | Medium | [Longest Word in Dictionary](Problems/0720.cpp) |
@@ -1337,6 +1339,7 @@ reference and a base for solving problems.
| 2678 | Easy | [Number of Senior Citizens](Problems/2678.cpp) |
| 2679 | Medium | [Sum in a Matrix](Problems/2679.cpp) |
| 2683 | Medium | [Neighboring Bitwise XOR](Problems/2683.cpp) |
+| 2684 | Medium | [Maximum Number of Moves in a Grid](Problems/2684.cpp) |
| 2685 | Medium | [Count the Number of Complete Components](Problems/2685.cpp) |
| 2696 | Easy | [Minimum String Length After Removing Substrings](Problems/2696.cpp) |
| 2698 | Medium | [Find the Punishment Number of an Integer](Problems/2698.cpp) |
