commit 8592c2f4edacb5e90959d7230415fdbe4f60c63e
parent 556b8dd23c9d9f9e397d21470ce94d1bb23b33d4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 14 Aug 2023 11:28:19 +0200
5 Random Problems
Diffstat:
6 files changed, 111 insertions(+), 0 deletions(-)
diff --git a/Problems/1329.cpp b/Problems/1329.cpp
@@ -0,0 +1,44 @@
+class Solution {
+public:
+ vector<vector<int>> diagonalSort(vector<vector<int>> &mat) {
+ unordered_map<int, priority_queue<int, vector<int>, greater<int>>> um;
+ int n = mat.size(), m = mat[0].size();
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) { um[i - j].push(mat[i][j]); }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ mat[i][j] = um[i - j].top();
+ um[i - j].pop();
+ }
+ }
+
+ return mat;
+ }
+};
+
+// No extra memory
+class Solution {
+public:
+ vector<vector<int>> diagonalSort(vector<vector<int>> &mat) {
+ int n = mat.size(), m = mat[0].size();
+ for (int k = 0; k < m; k++) {
+ for (int i = 0, ik = k; i < n && ik < m; i++, ik++) {
+ for (int j = 0, jk = k; j < n && jk < m; j++, jk++) {
+ if (mat[i][ik] < mat[j][jk]) swap(mat[i][ik], mat[j][jk]);
+ }
+ }
+ }
+
+ for (int k = 0; k < n; k++) {
+ for (int i = 0, ik = k; i < m && ik < n; i++, ik++) {
+ for (int j = 0, jk = k; j < m && jk < n; j++, jk++) {
+ if (mat[ik][i] < mat[jk][j]) swap(mat[ik][i], mat[jk][j]);
+ }
+ }
+ }
+
+ return mat;
+ }
+};
diff --git a/Problems/1409.cpp b/Problems/1409.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ vector<int> processQueries(const vector<int> &queries, int m) {
+ vector<int> vec(m), res;
+ res.reserve(queries.size());
+ iota(vec.begin(), vec.end(), 1);
+ for (const int query : queries) {
+ int i = 0, tmp = query;
+ while (vec[i] != query) swap(tmp, vec[i++]);
+ vec[i] = tmp;
+ res.push_back(i);
+ }
+ return res;
+ }
+};
diff --git a/Problems/1637.cpp b/Problems/1637.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+ int maxWidthOfVerticalArea(const vector<vector<int>> &points) {
+ vector<int> v;
+ v.reserve(points.size());
+ for (int i = 0; i < points.size(); i++) v.push_back(points[i][0]);
+ sort(v.begin(), v.end());
+
+ int maxi = 0;
+ for (int k = 1; k < v.size(); k++) maxi = max(maxi, v[k] - v[k - 1]);
+ return maxi;
+ }
+};
diff --git a/Problems/2161.cpp b/Problems/2161.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ vector<int> pivotArray(vector<int> &nums, int pivot) {
+ vector<int> tmp;
+ tmp.reserve(nums.size());
+ int count = 0, idx = 0;
+ for (int num : nums) {
+ if (num == pivot)
+ count++;
+ else if (num > pivot)
+ tmp.push_back(num);
+ else
+ nums[idx++] = num;
+ }
+
+ for (int i = 0; i < count; i++) nums[idx++] = pivot;
+ for (int num : tmp) nums[idx++] = num;
+ return nums;
+ }
+};
diff --git a/Problems/2391.cpp b/Problems/2391.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ int garbageCollection(const vector<string> &garbage,
+ const vector<int> &travel) {
+ int truck[4] = {0}, sum = 0, total = 0, i = 0;
+ while (true) {
+ total += garbage[i].size();
+ for (char c : garbage[i]) truck[c & 3] = sum;
+ if (i == garbage.size() - 1) break;
+ sum += travel[i++];
+ }
+ return total + truck[0] + truck[1] + truck[3];
+ }
+};
diff --git a/README.md b/README.md
@@ -470,6 +470,7 @@ for solving problems.
| 1318 | Medium | [Minimum Flips to Make a OR b Equal to c](Problems/1318.cpp) |
| 1319 | Medium | [Number of Operations to Make Network Connected](Problems/1319.cpp) |
| 1323 | Easy | [Maximum 69 Number](Problems/1323.cpp) |
+| 1329 | Medium | [Sort the Matrix Diagonally](Problems/1329.cpp) |
| 1334 | Medium | [Find the City With the Smallest Number of Neighbors at a Threshold Distance](Problems/1334.cpp) |
| 1337 | Easy | [The K Weakest Rows in a Matrix](Problems/1337.cpp) |
| 1339 | Medium | [Maximum Product of Splitted Binary Tree](Problems/1339.cpp) |
@@ -487,6 +488,7 @@ for solving problems.
| 1396 | Medium | [Design Underground System](Problems/1396.cpp) |
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
| 1406 | Hard | [Stone Game III](Problems/1406.cpp) |
+| 1409 | Medium | [Queries on a Permutation With Key](Problems/1409.cpp) |
| 1416 | Hard | [Restore The Array](Problems/1416.cpp) |
| 1425 | Hard | [Constrained Subsequence Sum](Problems/1425.cpp) |
| 1431 | Easy | [Kids With the Greatest Number of Candies](Problems/1431.cpp) |
@@ -524,6 +526,7 @@ for solving problems.
| 1609 | Medium | [Even Odd Tree](Problems/1609.cpp) |
| 1615 | Medium | [Maximal Network Rank](Problems/1615.cpp) |
| 1626 | Medium | [Best Team With No Conflicts](Problems/1626.cpp) |
+| 1637 | Medium | [Widest Vertical Area Between Two Points Containing No Points](Problems/1637.cpp) |
| 1639 | Hard | [Number of Ways to Form a Target String Given a Dictionary](Problems/1639.cpp) |
| 1646 | Easy | [Get Maximum in Generated Array](Problems/1646.cpp) |
| 1669 | Medium | [Merge In Between Linked Lists](Problems/1669.cpp) |
@@ -571,6 +574,7 @@ for solving problems.
| 2131 | Medium | [Longest Palindrome by Concatenating Two Letter Words](Problems/2131.cpp) |
| 2140 | Medium | [Solving Questions With Brainpower](Problems/2140.cpp) |
| 2141 | Hard | [Maximum Running Time of N Computers](Problems/2141.cpp) |
+| 2161 | Medium | [Partition Array According to Given Pivot](Problems/2161.cpp) |
| 2177 | Medium | [Find Three Consecutive Integers That Sum to a Given Number](Problems/2177.cpp) |
| 2181 | Medium | [Merge Nodes in Between Zeros](Problems/2181.cpp) |
| 2187 | Medium | [Minimum Time to Complete Trips](Problems/2187.cpp) |
@@ -603,6 +607,7 @@ for solving problems.
| 2369 | Medium | [Check if There is a Valid Partition For The Array](Problems/2369.cpp) |
| 2374 | Medium | [Node With Highest Edge Score](Problems/2374.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
+| 2391 | Medium | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp) |
| 2396 | Medium | [Strictly Palindromic Number](Problems/2396.cpp) |
| 2405 | Medium | [Optimal Partition of String](Problems/2405.cpp) |
| 2421 | Medium | [Number of Good Paths](Problems/2421.cpp) |
