commit a110587fb3bfc8a57fbdd26af6a80d9a6ded1753
parent 76b661e78fd65641191a5f53200da0d64c0b608e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 19 Aug 2023 13:53:01 +0200
5 Random Problems
Diffstat:
6 files changed, 98 insertions(+), 0 deletions(-)
diff --git a/Problems/1261.cpp b/Problems/1261.cpp
@@ -0,0 +1,25 @@
+class FindElements {
+ TreeNode *root;
+ unordered_set<int> all;
+
+public:
+ FindElements(TreeNode *root) : root(root) {
+ queue<TreeNode *> q({root});
+ root->val = 0;
+ while (!q.empty()) {
+ TreeNode *root = q.front();
+ q.pop();
+ all.insert(root->val);
+ if (root->left) {
+ root->left->val = 2 * root->val + 1;
+ q.push(root->left);
+ }
+ if (root->right) {
+ root->right->val = 2 * root->val + 2;
+ q.push(root->right);
+ }
+ }
+ }
+
+ bool find(int target) { return all.count(target); }
+};
diff --git a/Problems/1442.cpp b/Problems/1442.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+ int countTriplets(const vector<int> &arr) {
+ static int left[301];
+ left[0] = 0;
+ int n = arr.size(), res = 0;
+
+ for (int i = 0, acc = 0; i < n; i++) left[i + 1] = acc ^= arr[i];
+
+ for (int i = 0; i < n; i++) {
+ for (int j = i + 1; j < n; j++) {
+ if (left[i] == left[j + 1]) res += j - i;
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1605.cpp b/Problems/1605.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ vector<vector<int>> restoreMatrix(vector<int> &row, vector<int> &col) {
+ int m = row.size(), n = col.size();
+ vector<vector<int>> res(m, vector<int>(n, 0));
+ for (int i = 0; i < m; ++i) {
+ for (int j = 0; j < n; ++j) {
+ res[i][j] = min(row[i], col[j]);
+ row[i] -= res[i][j], col[j] -= res[i][j];
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/2044.cpp b/Problems/2044.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ int rec(const vector<int> &nums, const int maxi, int crnt = 0, int idx = 0) {
+ if (idx == nums.size()) return crnt == maxi;
+ if (crnt == maxi) return 1 << (nums.size() - idx);
+ return rec(nums, maxi, crnt, idx + 1) +
+ rec(nums, maxi, crnt | nums[idx], idx + 1);
+ }
+
+public:
+ int countMaxOrSubsets(const vector<int> &nums) {
+ int maxi = 0;
+ for (int n : nums) maxi |= n;
+ return rec(nums, maxi);
+ }
+};
diff --git a/Problems/2785.cpp b/Problems/2785.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ static constexpr bool isvowel(char c) {
+ return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
+ };
+
+public:
+ string &sortVowels(string &s) {
+ vector<char> vowels;
+ for (char c : s) {
+ if (isvowel(tolower(c))) vowels.push_back(c);
+ }
+
+ sort(vowels.begin(), vowels.end());
+
+ for (int i = 0, j = 0; i < s.size(); i++) {
+ if (isvowel(tolower(s[i]))) s[i] = vowels[j++];
+ }
+
+ return s;
+ }
+};
diff --git a/README.md b/README.md
@@ -460,6 +460,7 @@ for solving problems.
| 1232 | Easy | [Check If It Is a Straight Line](Problems/1232.cpp) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |
+| 1261 | Medium | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp) |
| 1282 | Medium | [Group the People Given the Group Size They Belong To](Problems/1282.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
@@ -497,6 +498,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) |
+| 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) |
| 1456 | Medium | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp) |
@@ -528,6 +530,7 @@ for solving problems.
| 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |
| 1601 | Hard | [Maximum Number of Achievable Transfer Requests](Problems/1601.cpp) |
| 1603 | Easy | [Design Parking System](Problems/1603.cpp) |
+| 1605 | Medium | [Find Valid Matrix Given Row and Column Sums](Problems/1605.cpp) |
| 1609 | Medium | [Even Odd Tree](Problems/1609.cpp) |
| 1615 | Medium | [Maximal Network Rank](Problems/1615.cpp) |
| 1626 | Medium | [Best Team With No Conflicts](Problems/1626.cpp) |
@@ -574,6 +577,7 @@ for solving problems.
| 1991 | Easy | [Find the Middle Index in Array](Problems/1991.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) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
| 2079 | Medium | [Watering Plants](Problems/2079.cpp) |
| 2085 | Easy | [Count Common Words With One Occurrence](Problems/2085.cpp) |
@@ -664,4 +668,5 @@ for solving problems.
| 2666 | Easy | [Allow One Function Call](Problems/2666.js) |
| 2667 | Easy | [Create Hello World Function](Problems/2667.js) |
| 2676 | Medium | [Throttle](Problems/2676.js) |
+| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
| 2807 | Medium | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp) |
