commit 0370016abe1a5256cf42af36524c0c0ce2724aa9
parent 4262d450c26845dfa95cf1bae83b5eb1f8810b17
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 21 Jan 2024 22:51:58 +0000
5 Random Problems
Diffstat:
6 files changed, 123 insertions(+), 0 deletions(-)
diff --git a/Problems/0284.cpp b/Problems/0284.cpp
@@ -0,0 +1,22 @@
+class PeekingIterator : public Iterator {
+ int l_next = -1;
+ bool has_next = false;
+
+ public:
+ PeekingIterator(const vector<int> &nums) : Iterator(nums) {
+ if (!Iterator::hasNext()) return;
+ l_next = Iterator::next();
+ has_next = true;
+ }
+
+ int peek() { return l_next; }
+
+ int next() {
+ const int crnt = l_next;
+ has_next = Iterator::hasNext();
+ if (has_next) l_next = Iterator::next();
+ return crnt;
+ }
+
+ bool hasNext() const { return has_next; }
+};
diff --git a/Problems/0539.cpp b/Problems/0539.cpp
@@ -0,0 +1,48 @@
+class Solution {
+ static const int day = 24 * 60;
+
+ static inline int val(const char *time) { return (time[0] & 0xF) * 10 + (time[1] & 0xF); }
+
+ static inline int val(const string &time) { return val(time.c_str()) * 60 + val(time.c_str() + 3); }
+
+ public:
+ int findMinDifference(const vector<string> &timePoints) {
+ const int n = size(timePoints);
+ vector<int> time(n);
+
+ for (int i = 0; i < n; i++)
+ time[i] = val(timePoints[i]);
+ sort(begin(time), end(time));
+
+ int res = day - time.back() + time.front();
+ for (int i = 1; i < n; i++)
+ res = min(res, time[i] - time[i - 1]);
+
+ return res;
+ }
+};
+
+// No extra memory, little bit slower
+class Solution {
+ static const int day = 24 * 60;
+
+ static inline int val(const char *time) { return (time[0] & 0xF) * 10 + (time[1] & 0xF); }
+
+ static inline int val(const string &time) { return val(time.c_str()) * 60 + val(time.c_str() + 3); }
+
+ public:
+ int findMinDifference(vector<string> &timePoints) {
+ const int n = size(timePoints);
+ sort(begin(timePoints), end(timePoints));
+
+ int res = INT_MAX;
+ int first = val(timePoints[0]), prev = first;
+ for (int i = 1; i < n; i++) {
+ const int crnt = val(timePoints[i]);
+ res = min(res, crnt - prev);
+ prev = crnt;
+ }
+
+ return min(res, first + (day - prev));
+ }
+};
diff --git a/Problems/0729.cpp b/Problems/0729.cpp
@@ -0,0 +1,19 @@
+class MyCalendar {
+ typedef pair<int, int> record;
+ set<record> st;
+
+ public:
+ bool book(int estart, int eend) {
+ const record event(estart, eend);
+ const auto next = st.lower_bound(event);
+
+ if (next != end(st) && next->first < eend) return false;
+ if (next != begin(st)) {
+ const auto prv = prev(next);
+ if (prv->second > estart) return false;
+ }
+
+ st.insert(event);
+ return true;
+ }
+};
diff --git a/Problems/1006.cpp b/Problems/1006.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ static int other(int n) {
+ if (n <= 0) return 0;
+ int res = n;
+ if (n > 1) res *= n - 1;
+ if (n > 2) res /= n - 2;
+ if (n > 3) res -= n - 3;
+ return res + other(n - 4);
+ }
+
+ public:
+ int clumsy(int n) const {
+ int res = n;
+ if (n > 1) res *= n - 1;
+ if (n > 2) res /= n - 2;
+ if (n > 3) res += n - 3;
+ return res - other(n - 4);
+ }
+};
diff --git a/Problems/1362.cpp b/Problems/1362.cpp
@@ -0,0 +1,10 @@
+class Solution {
+ public:
+ vector<int> closestDivisors(const int num) const {
+ for (int i = sqrt(num + 2); i > 0; i--) {
+ if ((num + 1) % i == 0) return {i, (num + 1) / i};
+ if ((num + 2) % i == 0) return {i, (num + 2) / i};
+ }
+ return {};
+ }
+};
diff --git a/README.md b/README.md
@@ -254,6 +254,7 @@ for solving problems.
| 0278 | Easy | [First Bad Version](Problems/0278.cpp) |
| 0279 | Medium | [Perfect Squares](Problems/0279.cpp) |
| 0283 | Easy | [Move Zeroes](Problems/0283.cpp) |
+| 0284 | Medium | [Peeking Iterator](Problems/0284.cpp) |
| 0287 | Medium | [Find the Duplicate Number](Problems/0287.cpp) |
| 0289 | Medium | [Game of Life](Problems/0289.cpp) |
| 0290 | Easy | [Word Pattern](Problems/0290.cpp) |
@@ -362,6 +363,7 @@ for solving problems.
| 0535 | Medium | [Encode and Decode TinyURL](Problems/0535.cpp) |
| 0537 | Medium | [Complex Number Multiplication](Problems/0537.cpp) |
| 0538 | Medium | [Convert BST to Greater Tree](Problems/0538.cpp) |
+| 0539 | Medium | [Minimum Time Difference](Problems/0539.cpp) |
| 0540 | Medium | [Single Element in a Sorted Array](Problems/0540.cpp) |
| 0542 | Medium | [01 Matrix](Problems/0542.cpp) |
| 0543 | Easy | [Diameter of Binary Tree](Problems/0543.cpp) |
@@ -440,6 +442,7 @@ for solving problems.
| 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) |
+| 0729 | Medium | [My Calendar I](Problems/0729.cpp) |
| 0733 | Easy | [Flood Fill](Problems/0733.cpp) |
| 0735 | Medium | [Asteroid Collision](Problems/0735.cpp) |
| 0739 | Medium | [Daily Temperatures](Problems/0739.cpp) |
@@ -556,6 +559,7 @@ for solving problems.
| 0998 | Medium | [Maximum Binary Tree II](Problems/0998.cpp) |
| 1003 | Medium | [Check If Word Is Valid After Substitutions](Problems/1003.cpp) |
| 1004 | Medium | [Max Consecutive Ones III](Problems/1004.cpp) |
+| 1006 | Medium | [Clumsy Factorial](Problems/1006.cpp) |
| 1008 | Medium | [Construct Binary Search Tree from Preorder Traversal](Problems/1008.cpp) |
| 1011 | Medium | [Capacity To Ship Packages Within D Days](Problems/1011.cpp) |
| 1014 | Medium | [Best Sightseeing Pair](Problems/1014.cpp) |
@@ -692,6 +696,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) |
+| 1362 | Medium | [Closest Divisors](Problems/1362.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) |
