commit 76b661e78fd65641191a5f53200da0d64c0b608e
parent e07bdc47dda3dd941caa6dd0c302dc6d9c0b3da0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 18 Aug 2023 14:27:58 +0200
Improved Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 107 insertions(+), 9 deletions(-)
diff --git a/Problems/0890.cpp b/Problems/0890.cpp
@@ -0,0 +1,28 @@
+class Solution {
+public:
+ vector<string> findAndReplacePattern(const vector<string> &words,
+ const string &pattern) {
+ vector<string> res;
+ static int um[27] = {0};
+ static bool used[27] = {0};
+ for (const auto &word : words) {
+ for (int i = 0; i < pattern.size(); i++) {
+ const uint8_t w = word[i] & 0x1F;
+ const uint8_t p = pattern[i] & 0x1F;
+ if (um[w]) {
+ if (um[w] != p) goto next;
+ continue;
+ }
+ if (used[p]) goto next;
+ used[p] = true;
+ um[w] = p;
+ }
+ res.push_back(word);
+ next:;
+ memset(um, 0x00, sizeof(um));
+ memset(used, 0x00, sizeof(used));
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1381.cpp b/Problems/1381.cpp
@@ -0,0 +1,21 @@
+class CustomStack {
+ vector<int> st;
+ int size = 0;
+
+public:
+ CustomStack(int maxSize) : st(maxSize) {}
+
+ void push(int x) {
+ if (size == st.size()) return;
+ st[size++] = x;
+ }
+
+ int pop() {
+ if (size == 0) return -1;
+ return st[--size];
+ }
+
+ void increment(int k, int val) {
+ for (int i = 0; i < min(k, size); i++) st[i] += val;
+ }
+};
diff --git a/Problems/1615.cpp b/Problems/1615.cpp
@@ -1,17 +1,20 @@
class Solution {
public:
int maximalNetworkRank(int n, vector<vector<int>> &roads) {
- vector<unordered_set<int>> adj(n, unordered_set<int>());
- for (auto &p : roads) {
- adj[p[0]].insert(p[1]);
- adj[p[1]].insert(p[0]);
- }
-
+ int mat[101][101] = {0}, degree[101] = {0};
int res = 0;
- for (int i = 0; i < n; i++)
- for (int j = i + 1; j < n; j++)
- res = max(res, (int)(adj[i].size() + adj[j].size() - adj[i].count(j)));
+ for (int i = 0; i < roads.size(); i++) {
+ int u = roads[i][0], v = roads[i][1];
+ degree[u]++, degree[v]++;
+ mat[u][v] = mat[v][u] = 1;
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = i + 1; j < n; j++) {
+ res = max(res, degree[i] + degree[j] - mat[i][j]);
+ }
+ }
return res;
}
};
diff --git a/Problems/1641.cpp b/Problems/1641.cpp
@@ -0,0 +1,10 @@
+class Solution {
+public:
+ int countVowelStrings(int n) {
+ int vec[5] = {1, 1, 1, 1, 1};
+ for (int i = 1; i <= n; i++) {
+ for (int i = 4, sum = 0; i >= 0; i--) vec[i] = sum += vec[i];
+ }
+ return vec[0];
+ }
+};
diff --git a/Problems/1829.cpp b/Problems/1829.cpp
@@ -0,0 +1,12 @@
+class Solution {
+public:
+ vector<int> getMaximumXor(vector<int> &nums, int maximumBit) {
+ const int n = nums.size(), mask = (1 << maximumBit) - 1;
+ vector<int> res(n);
+ for (int i = 0, acc = 0; i < n; i++) {
+ nums[i] = acc ^= nums[i];
+ res[n - i - 1] = nums[i] ^ mask;
+ }
+ return res;
+ }
+};
diff --git a/Problems/2415.cpp b/Problems/2415.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+ TreeNode *reverseOddLevels(TreeNode *root) {
+ static vector<TreeNode *> vec(8192);
+ queue<TreeNode *> q({root});
+ for (int lvl = 0; !q.empty(); lvl++) {
+ for (int k = q.size() - 1; k >= 0; k--) {
+ vec[k] = q.front();
+ q.pop();
+ if (vec[k]->left) q.push(vec[k]->left);
+ if (vec[k]->right) q.push(vec[k]->right);
+ }
+ if (lvl % 2 == 0) continue;
+ int i = 0, j = (1 << lvl) - 1;
+ while (i < j) swap(vec[i++]->val, vec[j--]->val);
+ }
+ return root;
+ }
+};
diff --git a/README.md b/README.md
@@ -388,6 +388,7 @@ for solving problems.
| 0881 | Medium | [Boats to Save People](Problems/0881.cpp) |
| 0884 | Easy | [Uncommon Words from Two Sentences](Problems/0884.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) |
| 0897 | Easy | [Increasing Order Search Tree](Problems/0897.cpp) |
| 0901 | Medium | [Online Stock Span](Problems/0901.cpp) |
@@ -485,6 +486,7 @@ for solving problems.
| 1373 | Hard | [Maximum Sum BST in Binary Tree](Problems/1373.cpp) |
| 1376 | Medium | [Time Needed to Inform All Employees](Problems/1376.cpp) |
| 1379 | Easy | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp) |
+| 1381 | Medium | [Design a Stack With Increment Operation](Problems/1381.cpp) |
| 1382 | Medium | [Balance a Binary Search Tree](Problems/1382.cpp) |
| 1396 | Medium | [Design Underground System](Problems/1396.cpp) |
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
@@ -532,6 +534,7 @@ for solving problems.
| 1630 | Medium | [Arithmetic Subarrays](Problems/1630.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) |
+| 1641 | Medium | [Count Sorted Vowel Strings](Problems/1641.cpp) |
| 1646 | Easy | [Get Maximum in Generated Array](Problems/1646.cpp) |
| 1669 | Medium | [Merge In Between Linked Lists](Problems/1669.cpp) |
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
@@ -556,6 +559,7 @@ for solving problems.
| 1822 | Easy | [Sign of the Product of an Array](Problems/1822.cpp) |
| 1823 | Medium | [Find the Winner of the Circular Game](Problems/1823.cpp) |
| 1828 | Medium | [Queries on Number of Points Inside a Circle](Problems/1828.cpp) |
+| 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) |
| 1857 | Hard | [Largest Color Value in a Directed Graph](Problems/1857.cpp) |
@@ -622,6 +626,7 @@ for solving problems.
| 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) |
+| 2415 | Medium | [Reverse Odd Levels of Binary Tree](Problems/2415.cpp) |
| 2421 | Medium | [Number of Good Paths](Problems/2421.cpp) |
| 2433 | Medium | [Find The Original Array of Prefix Xor](Problems/2433.cpp) |
| 2439 | Medium | [Minimize Maximum of Array](Problems/2439.cpp) |
