commit f62b544a342a9931356afc695891df152b86bebb
parent 63482570ce27238d350bf5ffbc472981ccf45eb8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 22 Oct 2024 15:38:06 +0200
5 Random Problems
Diffstat:
6 files changed, 120 insertions(+), 0 deletions(-)
diff --git a/Problems/0154.cpp b/Problems/0154.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ int findMin(const vector<int> &nums) const {
+ int low = 0, high = nums.size() - 1;
+
+ while (low < high) {
+ const int mid = low + (high - low) / 2;
+ if (nums[mid] > nums[high])
+ low = mid + 1;
+ else if (nums[mid] < nums[high])
+ high = mid;
+ else
+ high--;
+ }
+
+ return nums[low];
+ }
+};
diff --git a/Problems/0166.cpp b/Problems/0166.cpp
@@ -0,0 +1,31 @@
+class Solution {
+ public:
+ string fractionToDecimal(long long n, long long d) const {
+ if (n == 0) return "0";
+ string res;
+
+ if (n < 0 ^ d < 0) res += '-';
+ n = abs(n), d = abs(d);
+
+ res += to_string(n / d);
+ if ((n %= d) == 0) return res;
+ res += '.';
+
+ unordered_map<int, int> um;
+ while (n) {
+ if (um.count(n)) {
+ res.insert(um[n], 1, '(');
+ res += ')';
+ break;
+ }
+
+ um[n] = size(res);
+
+ n *= 10;
+ res += to_string(n / d);
+ n %= d;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0174.cpp b/Problems/0174.cpp
@@ -0,0 +1,17 @@
+class Solution {
+ public:
+ int calculateMinimumHP(const vector<vector<int>> &dungeon) const {
+ const int n = size(dungeon), m = size(dungeon[0]);
+ vector<int> dp(n + 1, INT_MAX);
+
+ dp[n - 1] = 1;
+ for (int j = m - 1; j >= 0; j--) {
+ for (int i = n - 1; i >= 0; i--) {
+ const int need = min(dp[i], dp[i + 1]) - dungeon[i][j];
+ dp[i] = max(need, 1);
+ }
+ }
+
+ return dp[0];
+ }
+};
diff --git a/Problems/0218.cpp b/Problems/0218.cpp
@@ -0,0 +1,33 @@
+class Solution {
+ public:
+ vector<vector<int>> getSkyline(const vector<vector<int>> &buildings) const {
+ using type_t = tuple<int, int>;
+ vector<type_t> vec;
+ vec.reserve(2 * size(buildings) + 1);
+
+ for (const auto &building : buildings) {
+ vec.emplace_back(building[0], +building[2]);
+ vec.emplace_back(building[1], -building[2]);
+ }
+ sort(begin(vec), end(vec));
+ vec.emplace_back(-1, -1);
+
+ multiset<int> st = {{0}};
+ vector<vector<int>> res;
+ for (int i = 0; i < size(vec) - 1; i++) {
+ const auto [x, h] = vec[i];
+
+ if (h > 0)
+ st.insert(h);
+ else
+ st.extract(-h);
+
+ if (x != get<0>(vec[i + 1])) {
+ const int height = *st.rbegin(); // 0 will always be there
+ if (res.empty() || res.back()[1] != height) res.push_back({x, height});
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0220.cpp b/Problems/0220.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ bool containsNearbyAlmostDuplicate(const vector<int> &nums, int indexDiff, int valueDiff) const {
+ multiset<int> st;
+
+ for (int i = 0; i < size(nums); i++) {
+ const auto it = st.insert(nums[i]);
+ if (it != begin(st) && nums[i] - *prev(it) <= valueDiff) return true;
+ if (next(it) != end(st) && *next(it) - nums[i] <= valueDiff) return true;
+
+ if (size(st) > indexDiff) st.extract(nums[i - indexDiff]);
+ }
+
+ return false;
+ }
+};
diff --git a/README.md b/README.md
@@ -177,17 +177,20 @@ for solving problems.
| 0151 | Medium | [Reverse Words in a String](Problems/0151.cpp) |
| 0152 | Medium | [Maximum Product Subarray](Problems/0152.cpp) |
| 0153 | Medium | [Find Minimum in Rotated Sorted Array](Problems/0153.cpp) |
+| 0154 | Hard | [Find Minimum in Rotated Sorted Array II](Problems/0154.cpp) |
| 0155 | Medium | [Min Stack](Problems/0155.cpp) |
| 0160 | Easy | [Intersection of Two Linked Lists](Problems/0160.cpp) |
| 0162 | Medium | [Find Peak Element](Problems/0162.cpp) |
| 0164 | Hard | [Maximum Gap](Problems/0164.cpp) |
| 0165 | Medium | [Compare Version Numbers](Problems/0165.cpp) |
+| 0166 | Medium | [Fraction to Recurring Decimal](Problems/0166.cpp) |
| 0167 | Medium | [Two Sum II - Input Array Is Sorted](Problems/0167.cpp) |
| 0168 | Easy | [Excel Sheet Column Title](Problems/0168.cpp) |
| 0169 | Easy | [Majority Element](Problems/0169.cpp) |
| 0171 | Easy | [Excel Sheet Column Number](Problems/0171.cpp) |
| 0172 | Medium | [Factorial Trailing Zeroes](Problems/0172.cpp) |
| 0173 | Medium | [Binary Search Tree Iterator](Problems/0173.cpp) |
+| 0174 | Hard | [Dungeon Game](Problems/0174.cpp) |
| 0175 | Easy | [Combine Two Tables](Problems/0175.cpp) |
| 0176 | Medium | [Second Highest Salary](Problems/0176.cpp) |
| 0177 | Medium | [Nth Highest Salary](Problems/0177.cpp) |
@@ -230,7 +233,9 @@ for solving problems.
| 0215 | Medium | [Kth Largest Element in an Array](Problems/0215.cpp) |
| 0216 | Medium | [Combination Sum III](Problems/0216.cpp) |
| 0217 | Easy | [Contains Duplicate](Problems/0217.cpp) |
+| 0218 | Hard | [The Skyline Problem](Problems/0218.cpp) |
| 0219 | Easy | [Contains Duplicate II](Problems/0219.cpp) |
+| 0220 | Hard | [Contains Duplicate III](Problems/0220.cpp) |
| 0221 | Medium | [Maximal Square](Problems/0221.cpp) |
| 0222 | Medium | [Count Complete Tree Nodes](Problems/0222.cpp) |
| 0223 | Medium | [Rectangle Area](Problems/0223.cpp) |
