commit cb02c694ef6ee3085b85a51774b0cf95cc39504c
parent e5b048bd4ec4008a684679475dd8c16edc323e42
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 22 Aug 2023 22:14:33 +0200
5 Random Problems
Diffstat:
6 files changed, 95 insertions(+), 0 deletions(-)
diff --git a/Problems/0811.cpp b/Problems/0811.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+ vector<string> subdomainVisits(const vector<string> &cpdomains) {
+ unordered_map<string, int> um;
+ for (const auto &s : cpdomains) {
+ int start, pos;
+ pos = start = s.find(' ');
+ int value = stoi(s.substr(0, pos));
+ while (pos != string::npos) {
+ um[s.substr(pos + 1)] += value;
+ pos = s.find('.', pos + 1);
+ }
+ }
+ vector<string> res;
+ res.reserve(um.size());
+ for (const auto &[s, n] : um) res.push_back(to_string(n) + " " + s);
+ return res;
+ }
+};
diff --git a/Problems/0921.cpp b/Problems/0921.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ int minAddToMakeValid(const string &s) {
+ int res = 0, cnt = 0;
+ for (char c : s) {
+ if (c == '(')
+ cnt++;
+ else if (c == ')') {
+ if (cnt > 0)
+ cnt--;
+ else
+ res++;
+ }
+ }
+ return res + cnt;
+ }
+};
diff --git a/Problems/1079.cpp b/Problems/1079.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ unordered_set<string> us;
+ bool used[8] = {false};
+ string crnt;
+
+ void rec(const string &tiles) {
+ us.insert(crnt);
+ if (crnt.size() == tiles.size()) return;
+
+ for (int i = 0; i < tiles.size(); i++) {
+ if (used[i]) continue;
+ used[i] = true;
+ crnt.push_back(tiles[i]);
+ rec(tiles);
+ crnt.pop_back();
+ used[i] = false;
+ }
+ }
+
+public:
+ int numTilePossibilities(const string tiles) {
+ rec(tiles);
+ return us.size() - 1;
+ }
+};
diff --git a/Problems/1104.cpp b/Problems/1104.cpp
@@ -0,0 +1,21 @@
+#define LOG2(X) ((unsigned)(8 * sizeof(int) - __builtin_clz((X)) - 1))
+
+class Solution {
+ int flip(int label) {
+ int log = LOG2(label), floor = 1 << log, ceil = (1 << log + 1) - 1;
+ return floor + ceil - label;
+ }
+
+public:
+ vector<int> pathInZigZagTree(int label) {
+ bool rev = LOG2(label) % 2;
+ vector<int> res({label});
+ if (rev) label = flip(label);
+ while ((label /= 2) > 0) {
+ rev = !rev;
+ res.push_back(!rev ? label : flip(label));
+ }
+ reverse(res.begin(), res.end());
+ return res;
+ }
+};
diff --git a/Problems/1910.cpp b/Problems/1910.cpp
@@ -0,0 +1,8 @@
+class Solution {
+public:
+ string removeOccurrences(string s, const string &part) {
+ for (int pos = s.find(part); pos != string::npos; pos = s.find(part))
+ s.erase(pos, part.size());
+ return s;
+ }
+};
diff --git a/README.md b/README.md
@@ -370,6 +370,7 @@ for solving problems.
| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
| 0807 | Medium | [Max Increase to Keep City Skyline](Problems/0807.cpp) |
| 0808 | Medium | [Soup Servings](Problems/0808.cpp) |
+| 0811 | Medium | [Subdomain Visit Count](Problems/0811.cpp) |
| 0815 | Hard | [Bus Routes](Problems/0815.cpp) |
| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
| 0837 | Medium | [New 21 Game](Problems/0837.cpp) |
@@ -400,6 +401,7 @@ for solving problems.
| 0915 | Medium | [Partition Array into Disjoint Intervals](Problems/0915.cpp) |
| 0918 | Medium | [Maximum Sum Circular Subarray](Problems/0918.cpp) |
| 0920 | Hard | [Number of Music Playlists](Problems/0920.cpp) |
+| 0921 | Medium | [Minimum Add to Make Parentheses Valid](Problems/0921.cpp) |
| 0926 | Medium | [Flip String to Monotone Increasing](Problems/0926.cpp) |
| 0931 | Medium | [Minimum Falling Path Sum](Problems/0931.cpp) |
| 0933 | Easy | [Number of Recent Calls](Problems/0933.cpp) |
@@ -442,10 +444,12 @@ for solving problems.
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
| 1061 | Medium | [Lexicographically Smallest Equivalent String](Problems/1061.cpp) |
| 1071 | Easy | [Greatest Common Divisor of Strings](Problems/1071.cpp) |
+| 1079 | Medium | [Letter Tile Possibilities](Problems/1079.cpp) |
| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |
| 1091 | Medium | [Shortest Path in Binary Matrix](Problems/1091.cpp) |
| 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) |
| 1125 | Hard | [Smallest Sufficient Team](Problems/1125.cpp) |
| 1129 | Medium | [Shortest Path with Alternating Colors](Problems/1129.cpp) |
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
@@ -570,6 +574,7 @@ for solving problems.
| 1857 | Hard | [Largest Color Value in a Directed Graph](Problems/1857.cpp) |
| 1870 | Medium | [Minimum Speed to Arrive on Time](Problems/1870.cpp) |
| 1877 | Medium | [Minimize Maximum Pair Sum in Array](Problems/1877.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) |
| 1964 | Hard | [Find the Longest Valid Obstacle Course at Each Position](Problems/1964.cpp) |
