commit a0d50931c2456237b75f86e5d2f4a0fe8f780025
parent e12dcc224c11a4be2b290d84e7cbc89826a28a13
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 31 Oct 2024 18:17:42 +0100
Daily Problem, 3 Random, 1 Update
Diffstat:
6 files changed, 152 insertions(+), 8 deletions(-)
diff --git a/Problems/0075.cpp b/Problems/0075.cpp
@@ -1,12 +1,14 @@
class Solution {
public:
- void sortColors(vector<int> &nums) {
- array<int, 3> arr;
- for (int n : nums)
- arr[n]++;
- int count = 0;
- for (int i = 0; i < 3; i++)
- while (arr[i]--)
- nums[count++] = i;
+ void sortColors(vector<int> &nums) const {
+ int i = 0, j = 0, k = size(nums) - 1;
+ while (j <= k) {
+ if (nums[j] < 1)
+ swap(nums[i++], nums[j++]);
+ else if (nums[j] > 1)
+ swap(nums[j], nums[k--]);
+ else
+ j++;
+ }
}
};
diff --git a/Problems/0324.cpp b/Problems/0324.cpp
@@ -0,0 +1,22 @@
+class Solution {
+
+ public:
+ void wiggleSort(vector<int> &nums) const {
+ const int n = size(nums);
+
+ const auto midptr = begin(nums) + n / 2;
+ nth_element(begin(nums), midptr, end(nums));
+ const int mid = *midptr;
+
+#define map(i) nums[(2 * (i) + 1) % (n | 1)]
+ int i = 0, j = 0, k = n - 1;
+ while (j <= k) {
+ if (map(j) > mid)
+ swap(map(i++), map(j++));
+ else if (map(j) < mid)
+ swap(map(j), map(k--));
+ else
+ j++;
+ }
+ }
+};
diff --git a/Problems/0329.cpp b/Problems/0329.cpp
@@ -0,0 +1,64 @@
+class Solution {
+ public:
+ int longestIncreasingPath(const vector<vector<int>> &matrix) const {
+ const int n = size(matrix), m = size(matrix[0]);
+
+ static const int offset[] = {-1, 0, 1, 0, -1};
+ const auto valid = [&](int i, int j) { return i >= 0 && i < n && j >= 0 && j < m; };
+
+ static int dp[201][201];
+ memset(dp, 0xFF, sizeof(dp));
+
+ int res = 0;
+ stack<tuple<int, int>> st;
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ if (dp[i][j] != -1) continue;
+
+ st.emplace(i, j);
+ while (!st.empty()) {
+ if (get<0>(st.top()) != -1) {
+ const auto [i, j] = st.top();
+ if (dp[i][j] != -1) {
+ st.pop();
+ continue;
+ }
+
+ dp[i][j] = -3;
+ st.emplace(-1, -1);
+ for (int k = 0; k < 4; k++) {
+ const int a = i + offset[k + 1];
+ const int b = j + offset[k];
+
+ if (!valid(a, b) || matrix[i][j] >= matrix[a][b]) continue;
+ if (dp[a][b] != -1) continue;
+ st.emplace(a, b);
+ dp[i][j] = -2;
+ }
+
+ continue;
+ }
+
+ st.pop();
+ const auto [i, j] = st.top();
+ st.pop();
+
+ int res = 0;
+ for (int k = 0; k < 4; k++) {
+ const int a = i + offset[k + 1];
+ const int b = j + offset[k];
+
+ if (!valid(a, b) || matrix[i][j] >= matrix[a][b]) continue;
+ res = max(res, dp[a][b]);
+ }
+
+ dp[i][j] = res + 1;
+ }
+
+ res = max(res, dp[i][j]);
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0331.cpp b/Problems/0331.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ bool isValidSerialization(const string &preorder) const {
+ const int n = size(preorder);
+ int size = 1;
+
+ for (int i = 0; i < n; i++) {
+ if (preorder[i] == ',') continue;
+ size--;
+ if (size < 0) return false;
+ if (preorder[i] != '#') {
+ while (i < n && preorder[i + 1] != ',')
+ i++;
+ size += 2;
+ }
+ }
+
+ return size == 0;
+ }
+};
diff --git a/Problems/2463.cpp b/Problems/2463.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ public:
+ long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory) const {
+ sort(begin(factory), end(factory));
+ sort(begin(robot), end(robot));
+
+ vector<int> positions;
+ for (const auto &f : factory) {
+ for (int i = 0; i < f[1]; i++) {
+ positions.push_back(f[0]);
+ }
+ }
+
+ const int n = size(robot), m = size(positions);
+ static long long dp[10001];
+
+ memset(dp, 0x00, sizeof(dp));
+ dp[m] = 1e12;
+ for (int i = n - 1; i >= 0; i--) {
+ long long prev = i != n - 1 ? 1e12 : 0;
+ for (int j = m - 1; j >= 0; j--) {
+ long long assign = abs(robot[i] - positions[j]) + prev;
+ long long skip = dp[j + 1];
+
+ prev = dp[j];
+ dp[j] = min(assign, skip);
+ }
+ }
+
+ return dp[0];
+ }
+};
diff --git a/README.md b/README.md
@@ -298,10 +298,13 @@ reference and a base for solving problems.
| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
| 0321 | Hard | [Create Maximum Number](Problems/0321.cpp) |
| 0322 | Medium | [Coin Change](Problems/0322.cpp) |
+| 0324 | Medium | [Wiggle Sort II](Problems/0324.cpp) |
| 0326 | Easy | [Power of Three](Problems/0326.cpp) |
| 0327 | Hard | [Count of Range Sum](Problems/0327.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
+| 0329 | Hard | [Longest Increasing Path in a Matrix](Problems/0329.cpp) |
| 0330 | Hard | [Patching Array](Problems/0330.cpp) |
+| 0331 | Medium | [Verify Preorder Serialization of a Binary Tree](Problems/0331.cpp) |
| 0332 | Hard | [Reconstruct Itinerary](Problems/0332.cpp) |
| 0334 | Medium | [Increasing Triplet Subsequence](Problems/0334.cpp) |
| 0337 | Medium | [House Robber III](Problems/0337.cpp) |
@@ -1271,6 +1274,7 @@ reference and a base for solving problems.
| 2458 | Hard | [Height of Binary Tree After Subtree Removal Queries](Problems/2458.cpp) |
| 2461 | Medium | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp) |
| 2462 | Medium | [Total Cost to Hire K Workers](Problems/2462.cpp) |
+| 2463 | Medium | [Minimum Total Distance Traveled](Problems/2463.cpp) |
| 2465 | Easy | [Number of Distinct Averages](Problems/2465.cpp) |
| 2466 | Medium | [Count Ways To Build Good Strings](Problems/2466.cpp) |
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
