commit 1827090201cbe1958739682b78b1764783ae02c7
parent a958ff5dc52c59f758b36477694d692b4e3b3b61
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 31 Jan 2024 22:46:32 +0000
5 Random Problems
Diffstat:
6 files changed, 133 insertions(+), 0 deletions(-)
diff --git a/Problems/0447.cpp b/Problems/0447.cpp
@@ -0,0 +1,27 @@
+class Solution {
+ static int distance(const vector<int> &a, const vector<int> &b) {
+ return pow(b[0] - a[0], 2) + pow(b[1] - a[1], 2);
+ }
+
+ public:
+ int numberOfBoomerangs(const vector<vector<int>> &points) const {
+ const int n = size(points);
+ int res = 0;
+
+ for (int i = 0; i < n; i++) {
+ unordered_map<int, int> um;
+
+ for (int j = 0; j < n; j++) {
+ if (i == j) continue;
+ um[distance(points[i], points[j])]++;
+ }
+
+ for (const auto [_, cnt] : um) {
+ if (cnt == 1) continue;
+ res += cnt * (cnt - 1);
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1041.cpp b/Problems/1041.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ bool isRobotBounded(const string &instructions) const {
+ static const int offset_x[] = {0, -1, 0, 1};
+ static const int offset_y[] = {1, 0, -1, 0};
+
+ int x = 0, y = 0, dir = 0;
+ for (const char instruction : instructions) {
+ switch (instruction) {
+ case 'G':
+ x += offset_x[dir];
+ y += offset_y[dir];
+ break;
+ case 'L': dir = dir == 3 ? 0 : dir + 1; break;
+ case 'R': dir = dir == 0 ? 3 : dir - 1; break;
+ }
+ }
+
+ return (x == 0 && y == 0) || (dir != 0);
+ }
+};
diff --git a/Problems/1080.cpp b/Problems/1080.cpp
@@ -0,0 +1,45 @@
+class Solution {
+ public:
+ TreeNode *sufficientSubset(TreeNode *root, int limit) const {
+ stack<pair<TreeNode *, int>> st;
+ unordered_set<TreeNode *> deleted;
+
+ st.emplace(root, root->val);
+ while (!st.empty()) {
+ if (st.top().first) {
+ auto [root, sum] = st.top();
+ st.emplace(nullptr, 0);
+ if (root->left) st.emplace(root->left, sum + root->left->val);
+ if (root->right) st.emplace(root->right, sum + root->right->val);
+ continue;
+ }
+
+ st.pop();
+ auto [root, sum] = st.top();
+ st.pop();
+
+ if (!root->left && !root->right) {
+ if (sum < limit) deleted.insert(root);
+ } else {
+ int children = 0, del = 0;
+ if (root->left) {
+ children++;
+ if (deleted.count(root->left)) {
+ root->left = nullptr;
+ del++;
+ }
+ }
+ if (root->right) {
+ children++;
+ if (deleted.count(root->right)) {
+ root->right = nullptr;
+ del++;
+ }
+ }
+ if (children == del) deleted.insert(root);
+ }
+ }
+
+ return !deleted.count(root) ? root : nullptr;
+ }
+};
diff --git a/Problems/1509.cpp b/Problems/1509.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ int minDifference(vector<int> &nums) const {
+ const int n = size(nums);
+ if (n <= 4) return 0;
+ partial_sort(begin(nums), begin(nums) + 4, end(nums));
+ nth_element(begin(nums) + 4, end(nums) - 4, end(nums));
+ sort(end(nums) - 4, end(nums));
+ return min({
+ nums[n - 1] - nums[3],
+ nums[n - 2] - nums[2],
+ nums[n - 3] - nums[1],
+ nums[n - 4] - nums[0],
+ });
+ }
+};
diff --git a/Problems/2840.cpp b/Problems/2840.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ public:
+ bool checkStrings(const string &s1, const string &s2) const {
+ int count1[27] = {0}, count2[27] = {0};
+
+ for (int i = 0; i < size(s1); i += 2) {
+ count1[s1[i] & 0x1F]++;
+ count1[s2[i] & 0x1F]--;
+ count2[s1[i + 1] & 0x1F]++;
+ count2[s2[i + 1] & 0x1F]--;
+ }
+
+ for (int i = 1; i <= 26; i++) {
+ if (count1[i] || count2[i]) return false;
+ }
+
+ return true;
+ }
+};
diff --git a/README.md b/README.md
@@ -326,6 +326,7 @@ for solving problems.
| 0443 | Medium | [String Compression](Problems/0443.cpp) |
| 0445 | Medium | [Add Two Numbers II](Problems/0445.cpp) |
| 0446 | Hard | [Arithmetic Slices II - Subsequence](Problems/0446.cpp) |
+| 0447 | Medium | [Number of Boomerangs](Problems/0447.cpp) |
| 0448 | Easy | [Find All Numbers Disappeared in an Array](Problems/0448.cpp) |
| 0449 | Medium | [Serialize and Deserialize BST](Problems/0449.cpp) |
| 0450 | Medium | [Delete Node in a BST](Problems/0450.cpp) |
@@ -587,6 +588,7 @@ for solving problems.
| 1038 | Medium | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp) |
| 1039 | Medium | [Minimum Score Triangulation of Polygon](Problems/1039.cpp) |
| 1040 | Medium | [Moving Stones Until Consecutive II](Problems/1040.cpp) |
+| 1041 | Medium | [Robot Bounded In Circle](Problems/1041.cpp) |
| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |
| 1043 | Medium | [Partition Array for Maximum Sum](Problems/1043.cpp) |
| 1045 | Medium | [Customers Who Bought All Products](Problems/1045.cpp) |
@@ -604,6 +606,7 @@ for solving problems.
| 1074 | Hard | [Number of Submatrices That Sum to Target](Problems/1074.cpp) |
| 1075 | Easy | [Project Employees I](Problems/1075.cpp) |
| 1079 | Medium | [Letter Tile Possibilities](Problems/1079.cpp) |
+| 1080 | Medium | [Insufficient Nodes in Root to Leaf Paths](Problems/1080.cpp) |
| 1081 | Medium | [Smallest Subsequence of Distinct Characters](Problems/1081.cpp) |
| 1084 | Easy | [Sales Analysis III](Problems/1084.cpp) |
| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |
@@ -779,6 +782,7 @@ for solving problems.
| 1503 | Medium | [Last Moment Before All Ants Fall Out of a Plank](Problems/1503.cpp) |
| 1504 | Medium | [Count Submatrices With All Ones](Problems/1504.cpp) |
| 1508 | Medium | [Range Sum of Sorted Subarray Sums](Problems/1508.cpp) |
+| 1509 | Medium | [Minimum Difference Between Largest and Smallest Value in Three Moves](Problems/1509.cpp) |
| 1512 | Easy | [Number of Good Pairs](Problems/1512.cpp) |
| 1514 | Medium | [Path with Maximum Probability](Problems/1514.cpp) |
| 1517 | Easy | [Find Users With Valid E-Mails](Problems/1517.cpp) |
@@ -1103,6 +1107,7 @@ for solving problems.
| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
| 2799 | Medium | [Count Complete Subarrays in an Array](Problems/2799.cpp) |
| 2807 | Medium | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp) |
+| 2840 | Medium | [Check if Strings Can be Made Equal With Operations II](Problems/2840.cpp) |
| 2849 | Medium | [Determine if a Cell Is Reachable at a Given Time](Problems/2849.cpp) |
| 2856 | Medium | [Minimum Array Length After Pair Removals](Problems/2856.cpp) |
| 2870 | Medium | [Minimum Number of Operations to Make Array Empty](Problems/2870.cpp) |
