commit 1efab4bbb1279f3e413b636a3f73f8ae62c84ada
parent efcdbeb12bf1d09be98e127d8a154c4049797fb2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 3 Sep 2023 21:14:04 +0200
5 Random Problems
Diffstat:
6 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/Problems/0791.cpp b/Problems/0791.cpp
@@ -0,0 +1,10 @@
+class Solution {
+ public:
+ string customSortString(const string &order, string &s) {
+ uint8_t index[27] = {0};
+ for (int i = 0; i < order.size(); i++)
+ index[order[i] & 0x1F] = i;
+ sort(begin(s), end(s), [&](const char a, const char b) { return index[a & 0x1F] < index[b & 0x1F]; });
+ return s;
+ }
+};
diff --git a/Problems/1110.cpp b/Problems/1110.cpp
@@ -0,0 +1,35 @@
+class Solution {
+ public:
+ vector<TreeNode *> delNodes(TreeNode *root, const vector<int> &to_delete) {
+ const unordered_set<int> us(begin(to_delete), end(to_delete));
+ vector<TreeNode *> res;
+
+ queue<TreeNode *> q;
+ q.push(root);
+ while (!q.empty()) {
+ TreeNode *crnt = q.front();
+ q.pop();
+
+ bool root = crnt->val > 0;
+ crnt->val = abs(crnt->val);
+ bool deleted = us.count(crnt->val);
+ if (root && !deleted) res.push_back(crnt);
+
+ if (crnt->left) {
+ int val = crnt->left->val;
+ if (!deleted) crnt->left->val = -val;
+ q.push(crnt->left);
+ if (us.count(val)) crnt->left = nullptr;
+ }
+
+ if (crnt->right) {
+ int val = crnt->right->val;
+ if (!deleted) crnt->right->val = -val;
+ q.push(crnt->right);
+ if (us.count(val)) crnt->right = nullptr;
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1338.cpp b/Problems/1338.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ int minSetSize(vector<int> &arr) {
+ sort(begin(arr), end(arr));
+
+ vector<int> count;
+ int n = arr.size() / 2, crnt = 1, res = 0;
+ for (int i = 1; i < arr.size(); i++) {
+ if (arr[i] == arr[i - 1])
+ crnt++;
+ else {
+ count.push_back(crnt);
+ crnt = 1;
+ }
+ }
+
+ count.push_back(crnt);
+ sort(rbegin(count), rend(count));
+
+ for (int i = 0; n > 0; i++)
+ n -= count[i], res++;
+ return res;
+ }
+};
diff --git a/Problems/1743.cpp b/Problems/1743.cpp
@@ -0,0 +1,27 @@
+class Solution {
+ public:
+ vector<int> restoreArray(const vector<vector<int>> &adjacentPairs) {
+ const int n = adjacentPairs.size() + 1;
+ unordered_map<int, vector<int>> um;
+
+ for (const auto &p : adjacentPairs) {
+ um[p[0]].push_back(p[1]);
+ um[p[1]].push_back(p[0]);
+ }
+
+ int start = -1;
+ for (const auto &[k, v] : um) {
+ if (v.size() == 1) {
+ start = k;
+ break;
+ }
+ }
+
+ vector<int> res(n);
+ res[0] = start, res[1] = um[start][0];
+ for (int i = 2; i < n; i++) {
+ res[i] = um[res[i - 1]][0] != res[i - 2] ? um[res[i - 1]][0] : um[res[i - 1]][1];
+ }
+ return res;
+ }
+};
diff --git a/Problems/2527.cpp b/Problems/2527.cpp
@@ -0,0 +1,9 @@
+class Solution {
+ public:
+ int xorBeauty(const vector<int> &nums) {
+ int res = 0;
+ for (const int n : nums)
+ res ^= n;
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -374,6 +374,7 @@ for solving problems.
| 0784 | Medium | [Letter Case Permutation](Problems/0784.cpp) |
| 0785 | Medium | [Is Graph Bipartite?](Problems/0785.cpp) |
| 0787 | Medium | [Cheapest Flights Within K Stops](Problems/0787.cpp) |
+| 0791 | Medium | [Custom Sort String](Problems/0791.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
| 0807 | Medium | [Max Increase to Keep City Skyline](Problems/0807.cpp) |
@@ -468,6 +469,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) |
+| 1110 | Medium | [Delete Nodes And Return Forest](Problems/1110.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) |
@@ -508,6 +510,7 @@ for solving problems.
| 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) |
+| 1338 | Medium | [Reduce Array Size to The Half](Problems/1338.cpp) |
| 1339 | Medium | [Maximum Product of Splitted Binary Tree](Problems/1339.cpp) |
| 1342 | Easy | [Number of Steps to Reduce a Number to Zero](Problems/1342.cpp) |
| 1345 | Hard | [Jump Game IV](Problems/1345.cpp) |
@@ -593,6 +596,7 @@ for solving problems.
| 1721 | Medium | [Swapping Nodes in a Linked List](Problems/1721.cpp) |
| 1722 | Medium | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp) |
| 1732 | Easy | [Find the Highest Altitude](Problems/1732.cpp) |
+| 1743 | Medium | [Restore the Array From Adjacent Pairs](Problems/1743.cpp) |
| 1751 | Hard | [Maximum Number of Events That Can Be Attended II](Problems/1751.cpp) |
| 1768 | Easy | [Merge Strings Alternately](Problems/1768.cpp) |
| 1769 | Medium | [Minimum Number of Operations to Move All Balls to Each Box](Problems/1769.cpp) |
@@ -704,6 +708,7 @@ for solving problems.
| 2483 | Medium | [Minimum Penalty for a Shop](Problems/2483.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
+| 2527 | Medium | [Find Xor-Beauty of Array](Problems/2527.cpp) |
| 2542 | Medium | [Maximum Subsequence Score](Problems/2542.cpp) |
| 2545 | Medium | [Sort the Students by Their Kth Score](Problems/2545.cpp) |
| 2551 | Hard | [Put Marbles in Bags](Problems/2551.cpp) |
