commit 2018fb87bfa7dbb80a368653cd87cb2ee0f881bd
parent cf327982d05967334ca414492d16b3e4ec7ea9f2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 24 Nov 2023 20:57:18 +0000
6 Random Problems
Diffstat:
7 files changed, 147 insertions(+), 0 deletions(-)
diff --git a/Problems/1366.cpp b/Problems/1366.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ string rankTeams(const vector<string> &votes) const {
+ static int count[27][27];
+ memset(count, 0x00, sizeof(count));
+
+ const int n = votes.size(), m = votes[0].size();
+ for (const auto &vote : votes) {
+ for (int i = 0; i < m; i++) {
+ count[vote[i] & 0x1F][i]++;
+ }
+ }
+
+ string s = votes[0];
+ sort(s.begin(), s.end(), [&](char a, char b) {
+ const int i = a & 0x1F, j = b & 0x1F;
+ for (int k = 0; k < m; k++) {
+ if (count[i][k] == count[j][k]) continue;
+ return count[i][k] > count[j][k];
+ }
+ return a < b;
+ });
+ return s;
+ }
+};
diff --git a/Problems/1545.cpp b/Problems/1545.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ char findKthBit(int n, int k) const {
+ int flip = 0, l = (1 << n) - 1;
+ while (k > 1) {
+ if (k == l / 2 + 1) return '1' - flip;
+ if (k > l / 2) {
+ k = l + 1 - k;
+ flip = !flip;
+ }
+ l /= 2;
+ }
+ return '0' + flip;
+ }
+};
diff --git a/Problems/1653.cpp b/Problems/1653.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ int minimumDeletions(const string &s) const {
+ static int acount[100001];
+
+ const int n = s.size();
+ acount[n] = 0;
+ for (int i = n - 1; i >= 0; i--) {
+ acount[i] = acount[i + 1] + (s[i] == 'a');
+ }
+
+ int acnt = 0, bcnt = 0, res = acount[0];
+ for (int i = 0; i < n; i++) {
+ s[i] == 'a' ? acnt++ : bcnt++;
+ res = min(res, bcnt + acount[i] - 1);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2385.cpp b/Problems/2385.cpp
@@ -0,0 +1,53 @@
+class Solution {
+ public:
+ int amountOfTime(TreeNode *root, int start) const {
+ unordered_map<TreeNode *, TreeNode *> parent;
+ queue<TreeNode *> q;
+ TreeNode *infected;
+
+ q.push(root);
+ while (!q.empty()) {
+ TreeNode *root = q.front();
+ q.pop();
+ if (root->val == start) {
+ infected = root;
+ break;
+ }
+
+ if (root->left) {
+ parent.insert({root->left, root});
+ q.push(root->left);
+ }
+
+ if (root->right) {
+ parent.insert({root->right, root});
+ q.push(root->right);
+ }
+ }
+
+ int depth = -1;
+ q = queue<TreeNode *>();
+ q.push(infected);
+ while (!q.empty()) {
+ depth++;
+ for (int k = q.size(); k > 0; k--) {
+ TreeNode *root = q.front();
+ q.pop();
+ if (parent.count(root)) {
+ TreeNode *prnt = parent[root];
+ (prnt->left == root ? prnt->left : prnt->right) = nullptr;
+ q.push(parent[root]);
+ }
+ if (root->left) {
+ q.push(root->left);
+ parent.erase(root->left);
+ }
+ if (root->right) {
+ q.push(root->right);
+ parent.erase(root->right);
+ }
+ }
+ }
+ return depth;
+ }
+};
diff --git a/Problems/2673.cpp b/Problems/2673.cpp
@@ -0,0 +1,12 @@
+class Solution {
+ public:
+ int minIncrements(int n, vector<int> &cost) const {
+ int res = 0;
+ for (int i = n / 2 - 1; i >= 0; i--) {
+ const int next = i << 1;
+ res += abs(cost[next + 1] - cost[next + 2]);
+ cost[i] += max(cost[next + 1], cost[next + 2]);
+ }
+ return res;
+ }
+};
diff --git a/Problems/2679.cpp b/Problems/2679.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ int matrixSum(const vector<vector<int>> &nums) const {
+ static int maxi[501];
+ memset(maxi, 0x00, sizeof(maxi));
+
+ const int m = nums[0].size();
+ for (auto row : nums) {
+ sort(row.begin(), row.end());
+ for (int i = 0; i < m; i++)
+ maxi[i] = max(maxi[i], row[i]);
+ }
+
+ return accumulate(begin(maxi), begin(maxi) + m, 0);
+ }
+};
diff --git a/README.md b/README.md
@@ -605,6 +605,7 @@ for solving problems.
| 1358 | Medium | [Number of Substrings Containing All Three Characters](Problems/1358.cpp) |
| 1359 | Hard | [Count All Valid Pickup and Delivery Options](Problems/1359.cpp) |
| 1361 | Medium | [Validate Binary Tree Nodes](Problems/1361.cpp) |
+| 1366 | Medium | [Rank Teams by Votes](Problems/1366.cpp) |
| 1367 | Medium | [Linked List in Binary Tree ](Problems/1367.cpp) |
| 1371 | Medium | [Find the Longest Substring Containing Vowels in Even Counts](Problems/1371.cpp) |
| 1372 | Medium | [Longest ZigZag Path in a Binary Tree](Problems/1372.cpp) |
@@ -666,6 +667,7 @@ for solving problems.
| 1535 | Medium | [Find the Winner of an Array Game](Problems/1535.cpp) |
| 1539 | Easy | [Kth Missing Positive Number](Problems/1539.cpp) |
| 1544 | Easy | [Make The String Great](Problems/1544.cpp) |
+| 1545 | Medium | [Find Kth Bit in Nth Binary String](Problems/1545.cpp) |
| 1547 | Hard | [Minimum Cost to Cut a Stick](Problems/1547.cpp) |
| 1551 | Medium | [Minimum Operations to Make Array Equal](Problems/1551.cpp) |
| 1552 | Medium | [Magnetic Force Between Two Balls](Problems/1552.cpp) |
@@ -696,6 +698,7 @@ for solving problems.
| 1641 | Medium | [Count Sorted Vowel Strings](Problems/1641.cpp) |
| 1646 | Easy | [Get Maximum in Generated Array](Problems/1646.cpp) |
| 1647 | Medium | [Minimum Deletions to Make Character Frequencies Unique](Problems/1647.cpp) |
+| 1653 | Medium | [Minimum Deletions to Make String Balanced](Problems/1653.cpp) |
| 1657 | Medium | [Determine if Two Strings Are Close](Problems/1657.cpp) |
| 1658 | Medium | [Minimum Operations to Reduce X to Zero](Problems/1658.cpp) |
| 1663 | Medium | [Smallest String With A Given Numeric Value](Problems/1663.cpp) |
@@ -844,6 +847,7 @@ for solving problems.
| 2369 | Medium | [Check if There is a Valid Partition For The Array](Problems/2369.cpp) |
| 2374 | Medium | [Node With Highest Edge Score](Problems/2374.cpp) |
| 2375 | Medium | [Construct Smallest Number From DI String](Problems/2375.cpp) |
+| 2385 | Medium | [Amount of Time for Binary Tree to Be Infected](Problems/2385.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
| 2391 | Medium | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp) |
| 2396 | Medium | [Strictly Palindromic Number](Problems/2396.cpp) |
@@ -900,7 +904,9 @@ for solving problems.
| 2665 | Easy | [Counter II](Problems/2665.js) |
| 2666 | Easy | [Allow One Function Call](Problems/2666.js) |
| 2667 | Easy | [Create Hello World Function](Problems/2667.js) |
+| 2673 | Medium | [Make Costs of Paths Equal in a Binary Tree](Problems/2673.cpp) |
| 2676 | Medium | [Throttle](Problems/2676.js) |
+| 2679 | Medium | [Sum in a Matrix](Problems/2679.cpp) |
| 2683 | Medium | [Neighboring Bitwise XOR](Problems/2683.cpp) |
| 2685 | Medium | [Count the Number of Complete Components](Problems/2685.cpp) |
| 2698 | Medium | [Find the Punishment Number of an Integer](Problems/2698.cpp) |
