commit ff69f22747db5464711d5a3e8f8184a9fbe189c4
parent e5acd3a1f703f9796029c62d754d875c27b92ae1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 24 Aug 2023 15:21:02 +0200
5 Random Problems
Diffstat:
6 files changed, 130 insertions(+), 0 deletions(-)
diff --git a/Problems/0885.cpp b/Problems/0885.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+ vector<vector<int>> spiralMatrixIII(const int rows, const int cols, int x,
+ int y) {
+ static const int8_t offset_x[4] = {0, 1, 0, -1};
+ static const int8_t offset_y[4] = {1, 0, -1, 0};
+ vector<vector<int>> res;
+ res.reserve(rows * cols);
+ int dir = 0, cnt = 1, len = 1;
+
+ while (res.size() < rows * cols) {
+ for (int i = 0; i < len; i++) {
+ if (x >= 0 && x < rows && y >= 0 && y < cols) res.push_back({x, y});
+ x += offset_x[dir], y += offset_y[dir];
+ }
+ len += dir & 1;
+ dir = (dir + 1) & 0x3;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1325.cpp b/Problems/1325.cpp
@@ -0,0 +1,32 @@
+class Solution {
+public:
+ TreeNode *removeLeafNodes(TreeNode *root, int target) {
+ TreeNode dummy(-1, root, nullptr);
+ unordered_map<TreeNode *, TreeNode *> um = {
+ {root, &dummy}
+ };
+ stack<TreeNode *> st({root});
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ if (root->val < 0) {
+ st.pop();
+ root->val = -root->val;
+ if (!root->left && !root->right && root->val == target) {
+ TreeNode *parent = um[root];
+ (parent->left == root ? parent->left : parent->right) = nullptr;
+ }
+ continue;
+ }
+ root->val = -root->val;
+ if (root->left) {
+ um[root->left] = root;
+ st.push(root->left);
+ }
+ if (root->right) {
+ um[root->right] = root;
+ st.push(root->right);
+ }
+ }
+ return dummy.left;
+ }
+};
diff --git a/Problems/1418.cpp b/Problems/1418.cpp
@@ -0,0 +1,34 @@
+class Solution {
+public:
+ vector<vector<string>> displayTable(vector<vector<string>> &orders) {
+ map<int, vector<string>> tables;
+ vector<vector<string>> res;
+ set<string> foods;
+
+ for (const auto &order : orders) {
+ tables[stoi(order[1])].push_back(order[2]);
+ foods.insert(order[2]);
+ }
+
+ unordered_map<string, int> pos;
+
+ int j = 1;
+ res.push_back({{"Table"}});
+ for (auto &food : foods) {
+ res[0].push_back(food);
+ pos[food] = j++;
+ }
+
+ for (auto &[table, foods] : tables) {
+ vector<int> row(res[0].size(), 0);
+ vector<string> rows;
+ rows.reserve(res[0].size());
+ for (const auto &food : foods) row[pos[food]]++;
+ row[0] = table;
+ for (int r : row) rows.push_back(to_string(r));
+ res.push_back(rows);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1448.cpp b/Problems/1448.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+ int goodNodes(TreeNode *root) {
+ queue<pair<TreeNode *, int>> q({
+ {root, INT_MIN}
+ });
+ int res = 0;
+
+ while (!q.empty()) {
+ const auto [root, maxi] = q.front();
+ q.pop();
+ if (root->val >= maxi) res++;
+ if (root->left) q.push({root->left, max(maxi, root->val)});
+ if (root->right) q.push({root->right, max(maxi, root->val)});
+
+ // For some reason it increases runtime and decreases memory usage
+ // Must be leetcode error...
+ root->left = root->right = nullptr;
+ }
+ return res;
+ }
+};
diff --git a/Problems/2023.cpp b/Problems/2023.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ int numOfPairs(const vector<string> &nums, const string target) {
+ unordered_map<string, int> um;
+ for (const auto &s : nums) um[s]++;
+
+ int res = 0;
+ for (int i = 0; i < target.size(); i++) {
+ const string s1 = target.substr(0, i);
+ const string s2 = target.substr(i);
+ res += (s1 != s2) ? um[s1] * um[s2] : um[s1] * (um[s1] - 1);
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -392,6 +392,7 @@ for solving problems.
| 0879 | Hard | [Profitable Schemes](Problems/0879.cpp) |
| 0881 | Medium | [Boats to Save People](Problems/0881.cpp) |
| 0884 | Easy | [Uncommon Words from Two Sentences](Problems/0884.cpp) |
+| 0885 | Medium | [Spiral Matrix III](Problems/0885.cpp) |
| 0886 | Medium | [Possible Bipartition](Problems/0886.cpp) |
| 0890 | Medium | [Find and Replace Pattern](Problems/0890.cpp) |
| 0894 | Medium | [All Possible Full Binary Trees](Problems/0894.cpp) |
@@ -482,6 +483,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) |
+| 1325 | Medium | [Delete Leaves With a Given Value](Problems/1325.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) |
@@ -504,6 +506,7 @@ for solving problems.
| 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) |
+| 1418 | Medium | [Display Table of Food Orders in a Restaurant](Problems/1418.cpp) |
| 1425 | Hard | [Constrained Subsequence Sum](Problems/1425.cpp) |
| 1431 | Easy | [Kids With the Greatest Number of Candies](Problems/1431.cpp) |
| 1436 | Easy | [Destination City](Problems/1436.cpp) |
@@ -511,6 +514,7 @@ for solving problems.
| 1442 | Medium | [Count Triplets That Can Form Two Arrays of Equal XOR](Problems/1442.cpp) |
| 1443 | Medium | [Minimum Time to Collect All Apples in a Tree](Problems/1443.cpp) |
| 1444 | Hard | [Number of Ways of Cutting a Pizza](Problems/1444.cpp) |
+| 1448 | Medium | [Count Good Nodes in Binary Tree](Problems/1448.cpp) |
| 1456 | Medium | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp) |
| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
@@ -586,6 +590,7 @@ for solving problems.
| 1971 | Easy | [Find if Path Exists in Graph](Problems/1971.cpp) |
| 1976 | Medium | [Number of Ways to Arrive at Destination](Problems/1976.cpp) |
| 1991 | Easy | [Find the Middle Index in Array](Problems/1991.cpp) |
+| 2023 | Medium | [Number of Pairs of Strings With Concatenation Equal to Target](Problems/2023.cpp) |
| 2024 | Medium | [Maximize the Confusion of an Exam](Problems/2024.cpp) |
| 2039 | Medium | [The Time When the Network Becomes Idle](Problems/2039.cpp) |
| 2044 | Medium | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp) |
