commit 3faa33aef172e429db053f3151951507106163d4
parent a0d3ce4aff8b642353244e3dc4c053ee84c5fef0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 28 Sep 2023 17:55:28 +0000
5 Random Problems
Diffstat:
6 files changed, 108 insertions(+), 0 deletions(-)
diff --git a/Problems/0636.cpp b/Problems/0636.cpp
@@ -0,0 +1,23 @@
+class Solution {
+ public:
+ vector<int> exclusiveTime(int n, const vector<string> &logs) {
+ stack<pair<int, int>> st;
+ vector<int> res(n, 0);
+ int time, id;
+ char op[6];
+
+ for (const string &log : logs) {
+ sscanf(log.c_str(), "%d:%[^:]:%d", &id, op, &time);
+ if (!strcmp(op, "start"))
+ st.push({id, time});
+ else {
+ const int added = time - st.top().second + 1;
+ res[id] += added;
+ st.pop();
+
+ if (!st.empty()) res[st.top().first] -= added;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0789.cpp b/Problems/0789.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ int distance(const vector<int> &a, const vector<int> &b) const {
+ return abs(a[0] - b[0]) + abs(a[1] - b[1]);
+ }
+
+ public:
+ bool escapeGhosts(const vector<vector<int>> &ghosts, const vector<int> &target) const {
+ const int pm = distance(target, {0, 0});
+ for (const auto &ghost : ghosts)
+ if (pm >= distance(target, ghost)) return false;
+ return true;
+ }
+};
diff --git a/Problems/1023.cpp b/Problems/1023.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ public:
+ vector<bool> camelMatch(const vector<string> &queries, const string &pattern) {
+ vector<bool> res(queries.size(), false);
+ for (int k = 0; k < queries.size(); k++) {
+ const string &query = queries[k];
+ int i = 0, j = 0;
+ while (i < query.size()) {
+ if (!isupper(query[i])) {
+ if (query[i] == pattern[j]) j++;
+ i++;
+ } else {
+ if (j == pattern.size() || query[i] != pattern[j]) goto next;
+ i++, j++;
+ }
+ }
+ if (j == pattern.size()) res[k] = true;
+ next:;
+ }
+ return res;
+ }
+};
diff --git a/Problems/1291.cpp b/Problems/1291.cpp
@@ -0,0 +1,36 @@
+class Solution {
+ public:
+ vector<int> sequentialDigits(const int low, const int high) {
+ vector<int> res;
+ for (int i = 1; i <= 9; i++) {
+ int crnt = i;
+ for (int j = i + 1; j <= 9; j++) {
+ crnt = crnt * 10 + j;
+ if (crnt > high) break;
+ if (crnt >= low) res.push_back(crnt);
+ }
+ }
+ sort(begin(res), end(res));
+ return res;
+ }
+};
+
+// BFS, without sort
+class Solution {
+ public:
+ vector<int> sequentialDigits(const int low, const int high) {
+ queue<int> q;
+ vector<int> res;
+ for (int i = 1; i <= 9; i++)
+ q.push(i);
+ while (!q.empty()) {
+ const int crnt = q.front();
+ q.pop();
+ if (crnt > high) continue;
+ if (crnt >= low) res.push_back(crnt);
+ if (crnt % 10 == 9) continue;
+ q.push(crnt * 10 + crnt % 10 + 1);
+ }
+ return res;
+ }
+};
diff --git a/Problems/2498.cpp b/Problems/2498.cpp
@@ -0,0 +1,9 @@
+class Solution {
+ public:
+ int maxJump(const vector<int> &stones) {
+ int res = stones[1];
+ for (int i = 2; i < stones.size(); i++)
+ res = max(res, stones[i] - stones[i - 2]);
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -350,6 +350,7 @@ for solving problems.
| 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) |
+| 0636 | Medium | [Exclusive Time of Functions](Problems/0636.cpp) |
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
| 0643 | Easy | [Maximum Average Subarray I](Problems/0643.cpp) |
| 0646 | Medium | [Maximum Length of Pair Chain](Problems/0646.cpp) |
@@ -397,6 +398,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) |
+| 0789 | Medium | [Escape The Ghosts](Problems/0789.cpp) |
| 0791 | Medium | [Custom Sort String](Problems/0791.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
| 0799 | Medium | [Champagne Tower](Problems/0799.cpp) |
@@ -489,6 +491,7 @@ for solving problems.
| 1019 | Medium | [Next Greater Node In Linked List](Problems/1019.cpp) |
| 1020 | Medium | [Number of Enclaves](Problems/1020.cpp) |
| 1022 | Easy | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp) |
+| 1023 | Medium | [Camelcase Matching](Problems/1023.cpp) |
| 1026 | Medium | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp) |
| 1027 | Medium | [Longest Arithmetic Subsequence](Problems/1027.cpp) |
| 1029 | Medium | [Two City Scheduling](Problems/1029.cpp) |
@@ -548,6 +551,7 @@ for solving problems.
| 1282 | Medium | [Group the People Given the Group Size They Belong To](Problems/1282.cpp) |
| 1286 | Medium | [Iterator for Combination](Problems/1286.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
+| 1291 | Medium | [Sequential Digits](Problems/1291.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
| 1306 | Medium | [Jump Game III](Problems/1306.cpp) |
@@ -814,6 +818,7 @@ for solving problems.
| 2487 | Medium | [Remove Nodes From Linked List](Problems/2487.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) |
+| 2498 | Medium | [Frog Jump II](Problems/2498.cpp) |
| 2517 | Medium | [Maximum Tastiness of Candy Basket](Problems/2517.cpp) |
| 2527 | Medium | [Find Xor-Beauty of Array](Problems/2527.cpp) |
| 2542 | Medium | [Maximum Subsequence Score](Problems/2542.cpp) |
