commit 98caf468181173e545668a85e597fccfe207b532
parent 7bffd2324dabd44143ba0d6bdc94ab34d27a6094
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 26 Aug 2023 12:17:48 +0200
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 121 insertions(+), 0 deletions(-)
diff --git a/Problems/0646.cpp b/Problems/0646.cpp
@@ -0,0 +1,32 @@
+// DP, O(n^2)
+class Solution {
+public:
+ int findLongestChain(vector<vector<int>> &pairs) {
+ sort(begin(pairs), end(pairs));
+ const int n = pairs.size();
+ int res = 1, count[1001] = {0};
+ for (int i = n - 1; i >= 0; i--) {
+ for (int j = i + 1; j < n; j++) {
+ if (pairs[i][1] < pairs[j][0]) count[i] = max(count[i], count[j]);
+ }
+ res = max(res, ++count[i]);
+ }
+
+ return res;
+ }
+};
+
+// Greedy, O(nlogn)
+class Solution {
+public:
+ int findLongestChain(vector<vector<int>> &pairs) {
+ sort(pairs.begin(), pairs.end(),
+ [](const auto &a, const auto &b) { return a[1] < b[1]; });
+
+ int curr = INT_MIN, ans = 0;
+ for (const auto &pair : pairs) {
+ if (pair[0] > curr) curr = pair[1], ans++;
+ }
+ return ans;
+ }
+};
diff --git a/Problems/0814.cpp b/Problems/0814.cpp
@@ -0,0 +1,32 @@
+class Solution {
+public:
+ TreeNode *pruneTree(TreeNode *root) {
+ TreeNode dummy(1, root, nullptr);
+ unordered_set<TreeNode *> has;
+ stack<TreeNode *> st;
+ st.push(&dummy);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ if (!root) {
+ st.pop();
+ root = st.top(), st.pop();
+ if (has.count(root->left))
+ has.insert(root);
+ else
+ root->left = nullptr;
+
+ if (has.count(root->right))
+ has.insert(root);
+ else
+ root->right = nullptr;
+
+ if (root->val == 1) has.insert(root);
+ continue;
+ }
+ st.push(nullptr);
+ if (root->left) st.push(root->left);
+ if (root->right) st.push(root->right);
+ }
+ return dummy.left;
+ }
+};
diff --git a/Problems/1111.cpp b/Problems/1111.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+ vector<int> maxDepthAfterSplit(const string &seq) {
+ vector<int> res;
+ res.reserve(seq.size());
+ for (int i = 0, count = 0; i < seq.size(); i++) {
+ if (seq[i] == '(') count++;
+ res.push_back(count % 2);
+ if (seq[i] == ')') count--;
+ }
+ return res;
+ }
+};
diff --git a/Problems/1441.cpp b/Problems/1441.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ vector<string> buildArray(vector<int> &target, int n) {
+ vector<string> res;
+ int stream = 1;
+ for (int t : target) {
+ while (stream++ != t) {
+ res.push_back("Push");
+ res.push_back("Pop");
+ }
+ res.push_back("Push");
+ }
+ return res;
+ }
+};
diff --git a/Problems/1529.cpp b/Problems/1529.cpp
@@ -0,0 +1,12 @@
+class Solution {
+public:
+ int minFlips(const string &target) {
+ int res = 0, looking = 1;
+ for (const char c : target) {
+ if ((c & 1) != looking) continue;
+ looking = !looking;
+ res++;
+ }
+ return res;
+ }
+};
diff --git a/Problems/2275.cpp b/Problems/2275.cpp
@@ -0,0 +1,11 @@
+class Solution {
+public:
+ int largestCombination(const vector<int> &candidates) {
+ int res = 0, maxi = *max_element(begin(candidates), end(candidates));
+ for (int mask = 1, cnt = 0; mask <= maxi; mask <<= 1, cnt = 0) {
+ for (int n : candidates) cnt += (n & mask) > 0;
+ res = max(res, cnt);
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -332,6 +332,7 @@ for solving problems.
| 0617 | Easy | [Merge Two Binary Trees](Problems/0617.cpp) |
| 0621 | Medium | [Task Scheduler](Problems/0621.cpp) |
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
+| 0646 | Medium | [Maximum Length of Pair Chain](Problems/0646.cpp) |
| 0649 | Medium | [Dota2 Senate](Problems/0649.cpp) |
| 0652 | Medium | [Find Duplicate Subtrees](Problems/0652.cpp) |
| 0653 | Easy | [Two Sum IV - Input is a BST](Problems/0653.cpp) |
@@ -376,6 +377,7 @@ for solving problems.
| 0807 | Medium | [Max Increase to Keep City Skyline](Problems/0807.cpp) |
| 0808 | Medium | [Soup Servings](Problems/0808.cpp) |
| 0811 | Medium | [Subdomain Visit Count](Problems/0811.cpp) |
+| 0814 | Medium | [Binary Tree Pruning](Problems/0814.cpp) |
| 0815 | Hard | [Bus Routes](Problems/0815.cpp) |
| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
| 0837 | Medium | [New 21 Game](Problems/0837.cpp) |
@@ -457,6 +459,7 @@ for solving problems.
| 1095 | Easy | [Find Numbers with Even Number of Digits](Problems/1095.cpp) |
| 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) |
| 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) |
@@ -516,6 +519,7 @@ for solving problems.
| 1431 | Easy | [Kids With the Greatest Number of Candies](Problems/1431.cpp) |
| 1436 | Easy | [Destination City](Problems/1436.cpp) |
| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/1438.cpp) |
+| 1441 | Medium | [Build an Array With Stack Operations](Problems/1441.cpp) |
| 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) |
@@ -535,6 +539,7 @@ for solving problems.
| 1514 | Medium | [Path with Maximum Probability](Problems/1514.cpp) |
| 1519 | Medium | [Number of Nodes in the Sub-Tree With the Same Label](Problems/1519.cpp) |
| 1523 | Easy | [Count Odd Numbers in an Interval Range](Problems/1523.cpp) |
+| 1529 | Medium | [Minimum Suffix Flips](Problems/1529.cpp) |
| 1539 | Easy | [Kth Missing Positive Number](Problems/1539.cpp) |
| 1544 | Easy | [Make The String Great](Problems/1544.cpp) |
| 1547 | Hard | [Minimum Cost to Cut a Stick](Problems/1547.cpp) |
@@ -628,6 +633,7 @@ for solving problems.
| 2246 | Hard | [Longest Path With Different Adjacent Characters](Problems/2246.cpp) |
| 2265 | Medium | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp) |
| 2272 | Hard | [Substring With Largest Variance](Problems/2272.cpp) |
+| 2275 | Medium | [Largest Combination With Bitwise AND Greater Than Zero](Problems/2275.cpp) |
| 2279 | Medium | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp) |
| 2285 | Medium | [Maximum Total Importance of Roads](Problems/2285.cpp) |
| 2294 | Medium | [Partition Array Such That Maximum Difference Is K](Problems/2294.cpp) |
