commit 3931c0cafe32664d0a12f032bf85812739bfa962
parent 23b471439c768422719febcd8b75a4c8f9e995ce
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 28 Aug 2023 11:50:30 +0200
5 Random Problems
Diffstat:
6 files changed, 92 insertions(+), 0 deletions(-)
diff --git a/Problems/0979.cpp b/Problems/0979.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ int distributeCoins(TreeNode *root) {
+ TreeNode dummy(0);
+ stack<pair<TreeNode *, TreeNode *>> q({{root, &dummy}});
+
+ int res = 0;
+ while (!q.empty()) {
+ auto [root, parent] = q.top();
+ if (root) {
+ q.push({nullptr, nullptr});
+ if (root->left) q.push({root->left, root});
+ if (root->right) q.push({root->right, root});
+ continue;
+ }
+ q.pop();
+ tie(root, parent) = q.top();
+ q.pop();
+ parent->val += root->val - 1;
+ res += abs(root->val - 1);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1043.cpp b/Problems/1043.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ int dp[501];
+
+ public:
+ Solution() { memset(dp, 0xFF, sizeof(dp)); }
+ int maxSumAfterPartitioning(const vector<int> &arr, const int k, int idx = 0) {
+ if (idx == arr.size()) return 0;
+ if (dp[idx] != -1) return dp[idx];
+
+ int maxi = arr[idx];
+ int res = maxi + maxSumAfterPartitioning(arr, k, idx + 1);
+ for (int i = idx + 1; i < idx + k && i < arr.size(); i++) {
+ maxi = max(maxi, arr[i]);
+ res = max(res, (i - idx + 1) * maxi + maxSumAfterPartitioning(arr, k, i + 1));
+ }
+
+ return dp[idx] = res;
+ }
+};
diff --git a/Problems/1310.cpp b/Problems/1310.cpp
@@ -0,0 +1,12 @@
+class Solution {
+ public:
+ vector<int> xorQueries(const vector<int> &arr, const vector<vector<int>> &q) {
+ const int n = arr.size(), m = q.size();
+ vector<int> sum(n + 1), res(m);
+ for (int i = 0, acc = 0; i < n; i++)
+ sum[i + 1] = acc ^= arr[i];
+ for (int i = 0; i < m; i++)
+ res[i] = sum[q[i][1] + 1] ^ sum[q[i][0]];
+ return res;
+ }
+};
diff --git a/Problems/1806.cpp b/Problems/1806.cpp
@@ -0,0 +1,11 @@
+class Solution {
+ public:
+ int reinitializePermutation(int n) {
+ int res = 0, i = 1;
+ while (res == 0 || i > 1) {
+ i = i * 2 % (n - 1);
+ res++;
+ }
+ return res;
+ }
+};
diff --git a/Problems/2196.cpp b/Problems/2196.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ TreeNode *createBinaryTree(const vector<vector<int>> &descriptions) {
+ vector<bool> child(100001, false);
+ TreeNode *um[100001] = {0};
+
+ for (const auto &desc : descriptions) {
+ if (!um[desc[0]]) um[desc[0]] = new TreeNode(desc[0]);
+ if (!um[desc[1]]) um[desc[1]] = new TreeNode(desc[1]);
+ (desc[2] ? um[desc[0]]->left : um[desc[0]]->right) = um[desc[1]];
+ child[desc[1]] = true;
+ }
+
+ for (const auto &desc : descriptions) {
+ if (!child[desc[0]]) return um[desc[0]];
+ }
+
+ return nullptr;
+ }
+};
diff --git a/README.md b/README.md
@@ -430,6 +430,7 @@ for solving problems.
| 0973 | Medium | [K Closest Points to Origin](Problems/0973.cpp) |
| 0974 | Medium | [Subarray Sums Divisible by K](Problems/0974.cpp) |
| 0977 | Easy | [Squares of a Sorted Array](Problems/0977.cpp) |
+| 0979 | Medium | [Distribute Coins in Binary Tree](Problems/0979.cpp) |
| 0980 | Hard | [Unique Paths III](Problems/0980.cpp) |
| 0983 | Medium | [Minimum Cost For Tickets](Problems/0983.cpp) |
| 0986 | Medium | [Interval List Intersections](Problems/0986.cpp) |
@@ -449,6 +450,7 @@ for solving problems.
| 1035 | Medium | [Uncrossed Lines](Problems/1035.cpp) |
| 1038 | Medium | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp) |
| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |
+| 1043 | Medium | [Partition Array for Maximum Sum](Problems/1043.cpp) |
| 1046 | Easy | [Last Stone Weight](Problems/1046.cpp) |
| 1047 | Easy | [Remove All Adjacent Duplicates In String](Problems/1047.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
@@ -484,6 +486,7 @@ for solving problems.
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
+| 1310 | Medium | [XOR Queries of a Subarray](Problems/1310.cpp) |
| 1311 | Medium | [Get Watched Videos by Your Friends](Problems/1311.cpp) |
| 1312 | Hard | [Minimum Insertion Steps to Make a String Palindrome](Problems/1312.cpp) |
| 1314 | Medium | [Matrix Block Sum](Problems/1314.cpp) |
@@ -583,6 +586,7 @@ for solving problems.
| 1791 | Easy | [Find Center of Star Graph](Problems/1791.cpp) |
| 1799 | Medium | [Maximize Score After N Operations](Problems/1799.cpp) |
| 1802 | Medium | [Maximum Value at a Given Index in a Bounded Array](Problems/1802.cpp) |
+| 1806 | Medium | [Minimum Number of Operations to Reinitialize a Permutation](Problems/1806.cpp) |
| 1817 | Medium | [Finding the Users Active Minutes](Problems/1817.cpp) |
| 1822 | Easy | [Sign of the Product of an Array](Problems/1822.cpp) |
| 1823 | Medium | [Find the Winner of the Circular Game](Problems/1823.cpp) |
@@ -624,6 +628,7 @@ for solving problems.
| 2181 | Medium | [Merge Nodes in Between Zeros](Problems/2181.cpp) |
| 2187 | Medium | [Minimum Time to Complete Trips](Problems/2187.cpp) |
| 2192 | Medium | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp) |
+| 2196 | Medium | [Create Binary Tree From Descriptions](Problems/2196.cpp) |
| 2215 | Easy | [Find the Difference of Two Arrays](Problems/2215.cpp) |
| 2218 | Hard | [Maximum Value of K Coins From Piles](Problems/2218.cpp) |
| 2221 | Medium | [Find Triangular Sum of an Array](Problems/2221.cpp) |
