commit 9e1a05c53bcca0dc1695d8f61189dade4b80d2f6
parent cd8e8100fb7f90a1e8e1ae519be6a47079a3399e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 6 Sep 2023 15:09:53 +0200
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 178 insertions(+), 0 deletions(-)
diff --git a/Problems/0609.cpp b/Problems/0609.cpp
@@ -0,0 +1,30 @@
+#pragma GCC optimize("fast")
+static auto _ = []() {
+ ios_base::sync_with_stdio(false);
+ cin.tie(nullptr);
+ cout.tie(nullptr);
+ return 0;
+}();
+
+class Solution {
+ public:
+ vector<vector<string>> findDuplicate(const vector<string> &paths) {
+ unordered_map<string, vector<string>> um;
+ vector<vector<string>> res;
+
+ string path, file;
+ for (const string &entry : paths) {
+ stringstream ss(entry);
+ ss >> path;
+ path += '/';
+ while (ss >> file) {
+ int idx = file.find('(');
+ um[file.substr(idx)].push_back(path + file.substr(0, idx));
+ }
+ }
+
+ for (const auto &[_, v] : um)
+ if (v.size() > 1) res.push_back(v);
+ return res;
+ }
+};
diff --git a/Problems/0647.cpp b/Problems/0647.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ int countSubstrings(const string &s) {
+ const int size = s.size();
+ int res = size, low, high;
+ for (int i = 0; i < size; i++) {
+ low = i - 1, high = i + 1;
+ while (low >= 0 && high < size) {
+ if (s[low--] != s[high++]) break;
+ res++;
+ }
+
+ low = i - 1, high = i;
+ while (low >= 0 && high < size) {
+ if (s[low--] != s[high++]) break;
+ res++;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0725.cpp b/Problems/0725.cpp
@@ -0,0 +1,34 @@
+class Solution {
+ public:
+ vector<ListNode *> splitListToParts(ListNode *head, int k) {
+ int size = 0, part, extra;
+
+ for (ListNode *tmp = head; tmp; tmp = tmp->next)
+ size++;
+ if (k >= size) {
+ part = 1;
+ extra = 0;
+ } else {
+ part = size / k;
+ extra = size - (part * k);
+ }
+
+ vector<ListNode *> res;
+ ListNode *crnt = head, *tmp;
+ while (size >= part) {
+ res.push_back(crnt);
+ for (int i = 1; i < part; i++)
+ crnt = crnt->next;
+ if (extra-- > 0) crnt = crnt->next, size--;
+ size -= part;
+ tmp = crnt->next;
+ crnt->next = nullptr;
+ crnt = tmp;
+ }
+
+ while (res.size() < k)
+ res.push_back(nullptr);
+
+ return res;
+ }
+};
diff --git a/Problems/1457.cpp b/Problems/1457.cpp
@@ -0,0 +1,23 @@
+
+class Solution {
+ int count[10] = {0};
+
+ public:
+ int pseudoPalindromicPaths(TreeNode *root) {
+ int res = 0;
+
+ count[root->val]++;
+ if (!root->left && !root->right) {
+ int odd = 0;
+ for (int i = 1; i <= 9; i++)
+ if (count[i] % 2 && odd++) break;
+ res = odd <= 1;
+ } else {
+ if (root->left) res += pseudoPalindromicPaths(root->left);
+ if (root->right) res += pseudoPalindromicPaths(root->right);
+ }
+ count[root->val]--;
+
+ return res;
+ }
+};
diff --git a/Problems/1752.cpp b/Problems/1752.cpp
@@ -0,0 +1,30 @@
+
+// Simulation
+class Solution {
+ public:
+ int maximumScore(int a, int b, int c) {
+ priority_queue<int> pq;
+ pq.push(a), pq.push(b), pq.push(c);
+
+ int res = 0;
+ while (pq.size() >= 2) {
+ int a = pq.top();
+ pq.pop();
+ int b = pq.top();
+ pq.pop();
+ if (a > 1) pq.push(a - 1);
+ if (b > 1) pq.push(b - 1);
+ res++;
+ }
+ return res;
+ }
+};
+
+// Math
+class Solution {
+ public:
+ int maximumScore(const int a, const int b, const int c) const {
+ const int total = a + b + c;
+ return min(total / 2, total - max({a, b, c}));
+ }
+};
diff --git a/Problems/1905.cpp b/Problems/1905.cpp
@@ -0,0 +1,34 @@
+
+class Solution {
+ public:
+ int countSubIslands(const vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
+ static constexpr const int offset_x[] = {0, 0, 1, -1};
+ static constexpr const int offset_y[] = {1, -1, 0, 0};
+ const int n = grid1.size(), m = grid1[0].size();
+ const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
+
+ int res = 0;
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ if (!grid2[i][j] || !grid1[i][j]) continue;
+ grid2[i][j] = 0;
+ queue<pair<int, int>> q({{i, j}});
+ bool sub = true;
+ while (!q.empty()) {
+ const auto [i, j] = q.front();
+ q.pop();
+ for (int k = 0; k < 4; k++) {
+ const int x = i + offset_x[k];
+ const int y = j + offset_y[k];
+ if (!valid(x, y) || !grid2[x][y]) continue;
+ if (!grid1[x][y]) sub = false;
+ grid2[x][y] = 0;
+ q.push({x, y});
+ }
+ }
+ res += sub;
+ }
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -333,10 +333,12 @@ for solving problems.
| 0590 | Easy | [N-ary Tree Postorder Traversal](Problems/0590.cpp) |
| 0605 | Easy | [Can Place Flowers](Problems/0605.cpp) |
| 0606 | Easy | [Construct String from Binary Tree ](Problems/0606.cpp) |
+| 0609 | Medium | [Find Duplicate File in System](Problems/0609.cpp) |
| 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) |
+| 0647 | Medium | [Palindromic Substrings](Problems/0647.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) |
@@ -361,6 +363,7 @@ for solving problems.
| 0713 | Medium | [Subarray Product Less Than K](Problems/0713.cpp) |
| 0714 | Medium | [Best Time to Buy and Sell Stock with Transaction Fee](Problems/0714.cpp) |
| 0724 | Easy | [Find Pivot Index](Problems/0724.cpp) |
+| 0725 | Medium | [Split Linked List in Parts](Problems/0725.cpp) |
| 0733 | Easy | [Flood Fill](Problems/0733.cpp) |
| 0735 | Medium | [Asteroid Collision](Problems/0735.cpp) |
| 0739 | Medium | [Daily Temperatures](Problems/0739.cpp) |
@@ -551,6 +554,7 @@ for solving problems.
| 1444 | Hard | [Number of Ways of Cutting a Pizza](Problems/1444.cpp) |
| 1448 | Medium | [Count Good Nodes in Binary Tree](Problems/1448.cpp) |
| 1456 | Medium | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp) |
+| 1457 | Medium | [Pseudo-Palindromic Paths in a Binary Tree](Problems/1457.cpp) |
| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
| 1470 | Easy | [Shuffle the Array](Problems/1470.cpp) |
@@ -605,6 +609,7 @@ for solving problems.
| 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) |
+| 1753 | Medium | [Maximum Score From Removing Stones](Problems/1753.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) |
| 1786 | Medium | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp) |
@@ -625,6 +630,7 @@ for solving problems.
| 1870 | Medium | [Minimum Speed to Arrive on Time](Problems/1870.cpp) |
| 1877 | Medium | [Minimize Maximum Pair Sum in Array](Problems/1877.cpp) |
| 1884 | Medium | [Egg Drop With 2 Eggs and N Floors](Problems/1884.cpp) |
+| 1905 | Medium | [Count Sub Islands](Problems/1905.cpp) |
| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
| 1962 | Medium | [Remove Stones to Minimize the Total](Problems/1962.cpp) |
