commit e2e132c5429dbcaf48d671ec44ac0cc52c051f05
parent 37001bb0f0d8f22b999cef91bac4cd8d8b34e035
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 25 Jan 2023 01:16:15 +0100
Random problems, and orphaned file removal
Diffstat:
7 files changed, 116 insertions(+), 57 deletions(-)
diff --git a/Problems/0084.cpp b/Problems/0084.cpp
@@ -0,0 +1,31 @@
+class Solution {
+public:
+ int largestRectangleArea(vector<int> &heights) {
+ int n = heights.size();
+ vector<int> left(n), right(n);
+ stack<int> st;
+
+ for (int i = 0; i < n; i++) {
+ left[i] = i;
+ while (!st.empty() && heights[st.top()] >= heights[i]) {
+ left[i] = left[st.top()];
+ st.pop();
+ };
+ st.push(i);
+ }
+
+ for (int i = n - 1; i >= 0; i--) {
+ right[i] = i;
+ while (!st.empty() && heights[st.top()] >= heights[i]) {
+ right[i] = right[st.top()];
+ st.pop();
+ };
+ st.push(i);
+ }
+
+ int res = 0;
+ for (int i = 0; i < n; i++)
+ res = max(res, (right[i] - left[i] + 1) * heights[i]);
+ return res;
+ }
+};
diff --git a/Problems/0143.cpp b/Problems/0143.cpp
@@ -1,18 +1,42 @@
class Solution {
+ ListNode *reverseList(ListNode *head) {
+ ListNode *p, *q, *r;
+
+ p = head, q = nullptr;
+ while (p) {
+ r = q;
+ q = p;
+ p = p->next;
+ q->next = r;
+ }
+
+ return q;
+ }
+
+ ListNode *bmiddleNode(ListNode *head) {
+ ListNode *fast, *slow;
+ fast = slow = head;
+ while (fast->next && fast->next->next) {
+ fast = fast->next->next;
+ slow = slow->next;
+ }
+
+ return slow;
+ }
+
public:
- int longestSubarray(vector<int> &nums, int limit) {
- deque<int> maxd, mind;
- int i = 0, j;
- for (j = 0; j < nums.size(); ++j) {
- while (!maxd.empty() && nums[j] > maxd.back()) maxd.pop_back();
- while (!mind.empty() && nums[j] < mind.back()) mind.pop_back();
- maxd.push_back(nums[j]), mind.push_back(nums[j]);
- if (maxd.front() - mind.front() > limit) {
- if (maxd.front() == nums[i]) maxd.pop_front();
- if (mind.front() == nums[i]) mind.pop_front();
- i++;
- }
+ void reorderList(ListNode *head) {
+ ListNode *bmid = bmiddleNode(head);
+ ListNode *rev = reverseList(bmid->next);
+ bmid->next = nullptr;
+
+ ListNode top, *tmp = &top, *a, *b, *an;
+ for (a = head, b = rev; b; b = b->next, a = an) {
+ an = a->next;
+ tmp = tmp->next = a;
+ tmp = tmp->next = b;
}
- return j - i;
+ if (a) tmp = tmp->next = a;
+ tmp->next = nullptr;
}
};
diff --git a/Problems/0853.cpp b/Problems/0853.cpp
@@ -0,0 +1,44 @@
+class Solution {
+public:
+ int carFleet(int target, vector<int> &position, vector<int> &speed) {
+ int n = position.size();
+ if (!n) return 0;
+ vector<pair<int, double>> vp(n + 1);
+
+ for (int i = 0; i < n; i++)
+ vp[i] = {position[i], (double)(target - position[i]) / speed[i]};
+ sort(vp.rbegin(), vp.rend());
+
+ int res = 0;
+ double ct = 0;
+ for (int i = 0; i < n; i++) {
+ auto [_, time] = vp[i];
+ if (time > ct) {
+ res++;
+ ct = time;
+ }
+ }
+ return res;
+ }
+};
+
+// Using map for the heavy lifting
+class Solution {
+public:
+ int carFleet(int target, vector<int> &position, vector<int> &speed) {
+ map<int, double> mp;
+
+ for (int i = 0; i < speed.size(); i++)
+ mp[-position[i]] = (double)(target - position[i]) / speed[i];
+
+ int res = 0;
+ double ct = 0;
+ for (auto [_, time] : mp) {
+ if (time > ct) {
+ res++;
+ ct = time;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/102.cpp b/Problems/102.cpp
@@ -1,22 +0,0 @@
-class Solution {
-public:
- vector<vector<int>> levelOrder(TreeNode *root) {
- if (!root) return {};
-
- vector<vector<int>> res;
- queue<TreeNode *> q;
-
- q.push(root);
- for (int lvl = 0; !q.empty(); lvl++) {
- res.push_back(vector<int>());
- for (int t = q.size(); t > 0; t--) {
- TreeNode *root = q.front();
- q.pop();
- res[lvl].push_back(root->val);
- if (root->left) q.push(root->left);
- if (root->right) q.push(root->right);
- }
- }
- return res;
- }
-};
diff --git a/Problems/0143.cpp b/Problems/1438.cpp
diff --git a/Problems/841.cpp b/Problems/841.cpp
@@ -1,21 +0,0 @@
-class Solution {
-public:
- bool canVisitAllRooms(vector<vector<int>> &rooms) {
- unordered_set<int> us;
- queue<int> q;
-
- q.push(0);
- us.insert(0);
- while (!q.empty()) {
- int room = q.front();
- q.pop();
- for (int key : rooms[room]) {
- if (!us.count(key)) {
- us.insert(key);
- q.push(key);
- }
- }
- }
- return us.size() == rooms.size();
- }
-};
diff --git a/README.md b/README.md
@@ -58,6 +58,7 @@ for solving problems.
| 0067 | Easy | [Add Binary](Problems/0067.cpp) |
| 0070 | Easy | [Climbing Stairs](Problems/0070.cpp) |
| 0083 | Easy | [Remove Duplicates from Sorted List](Problems/0083.cpp) |
+| 0084 | Hard | [Largest Rectangle in Histogram](Problems/0084.cpp) |
| 0088 | Easy | [Merge Sorted Array](Problems/0088.cpp) |
| 0093 | Medium | [Restore IP Addresses](Problems/0093.cpp) |
| 0094 | Easy | [Binary Tree Inorder Traversal](Problems/0094.cpp) |
@@ -92,6 +93,7 @@ for solving problems.
| 0138 | Medium | [Copy List with Random Pointer](Problems/0138.cpp) |
| 0141 | Easy | [Linked List Cycle](Problems/0141.cpp) |
| 0142 | Medium | [Linked List Cycle II](Problems/0142.cpp) |
+| 0143 | Medium | [Reorder List](Problems/0143.cpp) |
| 0144 | Medium | [Binary Tree Preorder Traversal](Problems/0144.cpp) |
| 0145 | Easy | [Binary Tree Postorder Traversal](Problems/0145.cpp) |
| 0149 | Hard | [Max Points on a Line](Problems/0149.cpp) |
@@ -216,6 +218,7 @@ for solving problems.
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
| 0851 | Medium | [Loud and Rich](Problems/0851.cpp) |
+| 0853 | Medium | [Car Fleet](Problems/0853.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
| 0876 | Easy | [Middle of the Linked List](Problems/0876.cpp) |
| 0884 | Easy | [Uncommon Words from Two Sentences](Problems/0884.cpp) |
@@ -276,7 +279,7 @@ for solving problems.
| 1379 | Easy | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp) |
| 1382 | Medium | [Balance a Binary Search Tree](Problems/1382.cpp) |
| 1425 | Hard | [Constrained Subsequence Sum](Problems/1425.cpp) |
-| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/0143.cpp) |
+| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/1438.cpp) |
| 1443 | Medium | [Minimum Time to Collect All Apples in a Tree](Problems/1443.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) |
