commit 588fe94ef913e9ca4cd59527c6da461b4ee96bb7
parent 1c1e890065425bb80206a0e5615e79ec4772e04d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 31 Aug 2023 15:50:25 +0200
Daily Problem and 5 Random Problems
Diffstat:
8 files changed, 190 insertions(+), 0 deletions(-)
diff --git a/Problems/0865.cpp b/Problems/0865.cpp
@@ -0,0 +1,46 @@
+class Solution {
+ public:
+ TreeNode *subtreeWithAllDeepest(TreeNode *root) {
+ int8_t height[1001] = {0};
+ stack<TreeNode *> s({root});
+
+ TreeNode *res;
+ int maxi = INT_MIN;
+ while (!s.empty()) {
+ TreeNode *root = s.top();
+ if (root->val >= 0) {
+ if (root->left) {
+ height[root->left->val] = height[root->val] + 1;
+ s.push(root->left);
+ }
+ if (root->right) {
+ height[root->right->val] = height[root->val] + 1;
+ s.push(root->right);
+ }
+ root->val = -root->val - 1;
+ continue;
+ }
+ s.pop();
+ root->val = -(root->val + 1);
+
+ if (!root->left && !root->right) {
+ if (height[root->val] > maxi) {
+ maxi = height[root->val];
+ res = root;
+ }
+ continue;
+ }
+
+ int8_t l = 0, r = 0;
+ if (root->left) l = height[root->left->val];
+ if (root->right) r = height[root->right->val];
+
+ if (l || r) height[root->val] = max(l, r);
+ if (height[root->val] >= maxi && l == r) {
+ maxi = height[root->val];
+ res = root;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0877.cpp b/Problems/0877.cpp
@@ -0,0 +1,15 @@
+
+// Return true works as Alice is always the winner
+class Solution {
+ int dp[501][501];
+ int score(const vector<int> &piles, int i, int j, int crnt) {
+ if (j < i) return 0;
+ if (dp[i][j] != -1) return dp[i][j];
+ return dp[i][j] = max(score(piles, i + 1, j, -(crnt + piles[i])),
+ score(piles, i, j - 1, -(crnt + piles[j])));
+ }
+
+ public:
+ Solution() { memset(dp, 0xFF, sizeof(dp)); }
+ bool stoneGame(const vector<int> &piles) { return score(piles, 0, piles.size() - 1, 0) <= 0; }
+};
diff --git a/Problems/0969.cpp b/Problems/0969.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ vector<int> pancakeSort(vector<int> &arr) {
+ vector<int> res;
+
+ for (int i = arr.size() - 1, low, high; i >= 0; i--) {
+ if (arr[i] == i + 1) continue;
+
+ low = 0, high = 0;
+ while (arr[high] != i + 1)
+ high++;
+
+ res.push_back(high + 1);
+ while (low < high)
+ swap(arr[low++], arr[high--]);
+
+ low = 0, high = i;
+ res.push_back(high + 1);
+ while (low < high)
+ swap(arr[low++], arr[high--]);
+ }
+ return res;
+ }
+};
diff --git a/Problems/1123.cpp b/Problems/1123.cpp
@@ -0,0 +1,46 @@
+class Solution {
+ public:
+ TreeNode *lcaDeepestLeaves(TreeNode *root) {
+ int8_t height[1001] = {0};
+ stack<TreeNode *> s({root});
+
+ TreeNode *res;
+ int maxi = INT_MIN;
+ while (!s.empty()) {
+ TreeNode *root = s.top();
+ if (root->val >= 0) {
+ if (root->left) {
+ height[root->left->val] = height[root->val] + 1;
+ s.push(root->left);
+ }
+ if (root->right) {
+ height[root->right->val] = height[root->val] + 1;
+ s.push(root->right);
+ }
+ root->val = -root->val - 1;
+ continue;
+ }
+ s.pop();
+ root->val = -(root->val + 1);
+
+ if (!root->left && !root->right) {
+ if (height[root->val] > maxi) {
+ maxi = height[root->val];
+ res = root;
+ }
+ continue;
+ }
+
+ int8_t l = 0, r = 0;
+ if (root->left) l = height[root->left->val];
+ if (root->right) r = height[root->right->val];
+
+ if (l || r) height[root->val] = max(l, r);
+ if (height[root->val] >= maxi && l == r) {
+ maxi = height[root->val];
+ res = root;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/1326.cpp b/Problems/1326.cpp
@@ -0,0 +1,23 @@
+class Solution {
+ public:
+ int minTaps(int n, const vector<int> &ranges) {
+ vector<int> reach(n + 1);
+ for (int i = 0; i < ranges.size(); i++) {
+ int start = max(i - ranges[i], 0);
+ int end = min(n, i + ranges[i]);
+ reach[start] = max(reach[start], end);
+ }
+
+ int res = 0, crnt = 0, next = 0;
+ for (int i = 0; i <= n; i++) {
+ if (i > next) return -1;
+ if (i > crnt) {
+ res++;
+ crnt = next;
+ }
+ next = max(next, reach[i]);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1638.cpp b/Problems/1638.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ int countSubstrings(const string &s, const string &t) {
+ int res = 0;
+ for (int i = 0; i < s.size(); ++i) {
+ for (int j = 0; j < t.size(); ++j) {
+ for (int pos = 0, miss = 0; i + pos < s.size() && j + pos < t.size(); ++pos) {
+ if (s[i + pos] != t[j + pos] && ++miss > 1) break;
+ res += miss;
+ }
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/2640.cpp b/Problems/2640.cpp
@@ -0,0 +1,14 @@
+class Solution {
+ public:
+ vector<long long> findPrefixScore(const vector<int> &nums) {
+ ios_base::sync_with_stdio(false);
+ cin.tie(NULL);
+
+ vector<long long> res(nums.size());
+ for (long long i = 0, acc = 0, maxi = 0; i < nums.size(); i++) {
+ maxi = max(maxi, (long long)nums[i]);
+ res[i] = acc += nums[i] + maxi;
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -393,9 +393,11 @@ for solving problems.
| 0861 | Medium | [Score After Flipping Matrix](Problems/0861.cpp) |
| 0863 | Medium | [All Nodes Distance K in Binary Tree](Problems/0863.cpp) |
| 0864 | Hard | [Shortest Path to Get All Keys](Problems/0864.cpp) |
+| 0865 | Medium | [Smallest Subtree with all the Deepest Nodes](Problems/0865.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
| 0875 | Medium | [Koko Eating Bananas](Problems/0875.cpp) |
| 0876 | Easy | [Middle of the Linked List](Problems/0876.cpp) |
+| 0877 | Medium | [Stone Game](Problems/0877.cpp) |
| 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) |
@@ -430,6 +432,7 @@ for solving problems.
| 0958 | Medium | [Check Completeness of a Binary Tree](Problems/0958.cpp) |
| 0959 | Medium | [Regions Cut By Slashes](Problems/0959.cpp) |
| 0965 | Easy | [Univalued Binary Tree](Problems/0965.cpp) |
+| 0969 | Medium | [Pancake Sorting](Problems/0969.cpp) |
| 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) |
@@ -466,6 +469,7 @@ for solving problems.
| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |
| 1104 | Medium | [Path In Zigzag Labelled Binary Tree](Problems/1104.cpp) |
| 1111 | Medium | [Maximum Nesting Depth of Two Valid Parentheses Strings](Problems/1111.cpp) |
+| 1123 | Medium | [Lowest Common Ancestor of Deepest Leaves](Problems/1123.cpp) |
| 1125 | Hard | [Smallest Sufficient Team](Problems/1125.cpp) |
| 1129 | Medium | [Shortest Path with Alternating Colors](Problems/1129.cpp) |
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
@@ -499,6 +503,7 @@ for solving problems.
| 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) |
+| 1326 | Hard | [Minimum Number of Taps to Open to Water a Garden](Problems/1326.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) |
@@ -568,6 +573,7 @@ for solving problems.
| 1626 | Medium | [Best Team With No Conflicts](Problems/1626.cpp) |
| 1630 | Medium | [Arithmetic Subarrays](Problems/1630.cpp) |
| 1637 | Medium | [Widest Vertical Area Between Two Points Containing No Points](Problems/1637.cpp) |
+| 1638 | Medium | [Count Substrings That Differ by One Character](Problems/1638.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) |
@@ -710,6 +716,7 @@ for solving problems.
| 2635 | Easy | [Apply Transform Over Each Element in Array](Problems/2635.js) |
| 2636 | Medium | [Promise Pool ](Problems/2636.js) |
| 2637 | Easy | [Promise Time Limit](Problems/2637.js) |
+| 2640 | Medium | [Find the Score of All Prefixes of an Array](Problems/2640.cpp) |
| 2657 | Medium | [Find the Prefix Common Array of Two Arrays](Problems/2657.cpp) |
| 2665 | Easy | [Counter II](Problems/2665.js) |
| 2666 | Easy | [Allow One Function Call](Problems/2666.js) |
