commit f2e918f3684a265f6b472bc153f172595c55c5be
parent 5df9f6b9d33ce1eb0775b5f3a73e1c73bcf4e22b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 26 Dec 2022 19:09:49 +0100
Mix of various problems
Diffstat:
18 files changed, 339 insertions(+), 4 deletions(-)
diff --git a/Problems/0023.cpp b/Problems/0023.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+ ListNode *mergeKLists(vector<ListNode *> &lists) {
+ ListNode *dummy, *tmp;
+ tmp = dummy = new ListNode;
+
+ while (true) {
+ int mini = INT_MAX, index = -1;
+ for (int i = 0; i < lists.size(); i++) {
+ if (lists[i] && lists[i]->val < mini) {
+ index = i;
+ mini = lists[i]->val;
+ }
+ }
+ if (index == -1) break;
+ ListNode *t = lists[index];
+ lists[index] = lists[index]->next;
+ tmp = tmp->next = t;
+ }
+ return dummy->next;
+ }
+};
diff --git a/Problems/0025.cpp b/Problems/0025.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+ ListNode *reverseKGroup(ListNode *head, int k) {
+ stack<ListNode *> st;
+ ListNode *tmp, *dummy, *next;
+
+ tmp = dummy = new ListNode(-1, nullptr);
+ for (ListNode *p = head; p; p = next) {
+ next = p->next;
+ st.push(p);
+ if (st.size() == k) {
+ while (!st.empty()) {
+ tmp = tmp->next = st.top();
+ st.pop();
+ }
+ tmp->next = next;
+ }
+ }
+ return dummy->next;
+ }
+};
diff --git a/Problems/0049.cpp b/Problems/0049.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ vector<vector<string>> groupAnagrams(vector<string> &strs) {
+ vector<vector<string>> res;
+ unordered_map<unsigned long long, int> um;
+ for (int i = 0; i < strs.size(); i++) {
+ unsigned long long hash = 0;
+ vector<int> m(26, 0);
+
+ for (char c : strs[i]) m[c - 'a']++;
+ for (int i = 0; i < 26; i++) hash = hash * 100 + m[i];
+ if (um.find(hash) == um.end()) {
+ um[hash] = res.size();
+ res.push_back({strs[i]});
+ } else
+ res[um[hash]].push_back(strs[i]);
+ }
+ return res;
+ }
+};
diff --git a/Problems/0055.cpp b/Problems/0055.cpp
@@ -0,0 +1,8 @@
+class Solution {
+public:
+ bool canJump(vector<int> &nums) {
+ int n = nums.size(), limit = 0;
+ for (int i = 0; i <= limit && i < n; i++) limit = max(limit, i + nums[i]);
+ return limit >= n - 1;
+ }
+};
diff --git a/Problems/0122.cpp b/Problems/0122.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+ int maxProfit(vector<int> &prices) {
+ int profit = 0;
+ prices.push_back(INT_MIN);
+ for (int i = 0, j = 0; i < prices.size() - 1; i++) {
+ while (prices[j] < prices[j + 1]) j++;
+ profit += prices[j] - prices[i];
+ i = j++;
+ }
+ return profit;
+ }
+};
diff --git a/Problems/0125.cpp b/Problems/0125.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ bool isPalindrome(string s) {
+ int i = 0, j = s.size() - 1;
+ while (i < j) {
+ if (!isalnum(s[j]))
+ j--;
+ else if (!isalnum(s[i]))
+ i++;
+ else if (tolower(s[i]) != tolower(s[j]))
+ return false;
+ else
+ i++, j--;
+ }
+ return true;
+ }
+};
diff --git a/Problems/0155.cpp b/Problems/0155.cpp
@@ -0,0 +1,12 @@
+class MinStack {
+ stack<pair<int, int>> st;
+
+public:
+ MinStack() {}
+ void push(int val) {
+ st.push({val, !st.size() ? val : min(val, st.top().second)});
+ }
+ void pop() { st.pop(); }
+ int top() { return st.top().first; }
+ int getMin() { return st.top().second; }
+};
diff --git a/Problems/0217.cpp b/Problems/0217.cpp
@@ -0,0 +1,12 @@
+class Solution {
+public:
+ bool containsDuplicate(vector<int> &nums) {
+ unordered_set<int> us;
+ for (int n : nums)
+ if (us.count(n))
+ return true;
+ else
+ us.insert(n);
+ return false;
+ }
+};
diff --git a/Problems/0238.cpp b/Problems/0238.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ vector<int> productExceptSelf(vector<int> &nums) {
+ int n = nums.size();
+ vector<int> answer(n, 1);
+
+ int acc1 = 1, acc2 = 1;
+ for (int i = 0, j = n - 1; i < n; i++, j--) {
+ answer[i] *= acc1;
+ answer[j] *= acc2;
+ acc1 *= nums[i];
+ acc2 *= nums[j];
+ }
+
+ return answer;
+ }
+};
diff --git a/Problems/0242.cpp b/Problems/0242.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ bool isAnagram(string s, string t) {
+ if (s.size() != t.size()) return false;
+ vector<int> um(26, 0);
+ for (char c : s) um[c - 'a']++;
+ for (char c : t)
+ if (!um[c - 'a'])
+ return false;
+ else
+ um[c - 'a']--;
+ return true;
+ }
+};
diff --git a/Problems/0287.cpp b/Problems/0287.cpp
@@ -0,0 +1,18 @@
+class Solution {
+public:
+ int findDuplicate(vector<int> &nums) {
+ int slow = 0, fast = 0;
+ while (true) {
+ fast = nums[nums[fast]];
+ slow = nums[slow];
+ if (fast == slow) {
+ fast = 0;
+ while (fast != slow) {
+ fast = nums[fast];
+ slow = nums[slow];
+ }
+ return fast;
+ }
+ }
+ }
+};
diff --git a/Problems/0347.cpp b/Problems/0347.cpp
@@ -0,0 +1,29 @@
+struct elem {
+ static void reset() { id_cnt = 0; }
+ static int id_cnt;
+ int id = id_cnt++, count = 0;
+ void operator++(int) { count++; }
+ friend bool operator<(const elem &e1, const elem &e2) {
+ return e1.count > e2.count;
+ }
+ friend ostream &operator<<(ostream &os, const elem &e) {
+ return os << e.id << ": " << e.count;
+ }
+};
+int elem::id_cnt = 0;
+
+class Solution {
+ const int size = 20002;
+ const int mod = 10000;
+
+public:
+ vector<int> topKFrequent(vector<int> &nums, int k) {
+ elem::reset();
+ vector<elem> um(size);
+ for (int n : nums) um[n + mod]++;
+ sort(um.begin(), um.end());
+ vector<int> res;
+ for (int i = 0; i < k; i++) res.push_back(um[i].id - mod);
+ return res;
+ }
+};
diff --git a/Problems/0802.cpp b/Problems/0802.cpp
@@ -0,0 +1,39 @@
+class Solution {
+public:
+ vector<int> eventualSafeNodes(vector<vector<int>> &graph) {
+ int n = graph.size();
+ vector<int> res;
+ vector<bool> visited(n, false);
+ vector<bool> safe(n, false);
+ stack<int> st;
+ for (int i = 0; i < n; i++) {
+ if (visited[i]) continue;
+ st.push(i);
+ while (!st.empty()) {
+ int root = st.top();
+ st.pop();
+ if (root == -1) {
+ root = st.top();
+ st.pop();
+ bool s = true;
+ for (int c : graph[root])
+ if (!safe[c]) {
+ s = false;
+ break;
+ }
+ safe[root] = s;
+ continue;
+ }
+ if (visited[root]) continue;
+ visited[root] = true;
+ st.push(root);
+ st.push(-1);
+ for (int c : graph[root])
+ if (!visited[c]) st.push(c);
+ }
+ }
+ for (int i = 0; i < n; i++)
+ if (safe[i]) res.push_back(i);
+ return res;
+ }
+};
diff --git a/Problems/0886.cpp b/Problems/0886.cpp
@@ -0,0 +1,30 @@
+class Solution {
+public:
+ bool possibleBipartition(int n, vector<vector<int>> &dislikes) {
+ vector<vector<int>> adj(n + 1, vector<int>());
+ for (auto &p : dislikes) {
+ adj[p[0]].push_back(p[1]);
+ adj[p[1]].push_back(p[0]);
+ }
+
+ stack<int> st;
+ vector<int> color(n + 1, -1);
+ for (int i = 1; i <= n; i++) {
+ if (color[i] != -1) continue;
+ color[i] = 0;
+ st.push(i);
+ while (!st.empty()) {
+ int root = st.top();
+ st.pop();
+ for (int child : adj[root]) {
+ if (color[child] == color[root]) return false;
+ if (color[child] == -1) {
+ color[child] = !color[root];
+ st.push(child);
+ }
+ }
+ }
+ }
+ return true;
+ }
+};
diff --git a/Problems/1319.cpp b/Problems/1319.cpp
@@ -13,8 +13,6 @@ public:
}
void join(int x, int y) {
- x = find(x), y = find(y);
-
if (x != y) {
if (rank[x] > rank[y]) swap(x, y);
@@ -36,10 +34,11 @@ public:
int count = 0;
UnionFind uf(n);
for (auto &edge : connections) {
- if (uf.find(edge[0]) == uf.find(edge[1]))
+ int x = uf.find(edge[0]), y = uf.find(edge[1]);
+ if (x == y)
count++;
else
- uf.join(edge[0], edge[1]);
+ uf.join(x, y);
}
return count < uf.count() - 1 ? -1 : uf.count() - 1;
}
diff --git a/Problems/1615.cpp b/Problems/1615.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ int maximalNetworkRank(int n, vector<vector<int>> &roads) {
+ vector<unordered_set<int>> adj(n, unordered_set<int>());
+ for (auto &p : roads) {
+ adj[p[0]].insert(p[1]);
+ adj[p[1]].insert(p[0]);
+ }
+
+ int res = 0;
+ for (int i = 0; i < n; i++)
+ for (int j = i + 1; j < n; j++)
+ res = max(res, (int)(adj[i].size() + adj[j].size() - adj[i].count(j)));
+
+ return res;
+ }
+};
diff --git a/Problems/2368.cpp b/Problems/2368.cpp
@@ -0,0 +1,31 @@
+class Solution {
+public:
+ int reachableNodes(int n, vector<vector<int>> &edges,
+ vector<int> &restricted) {
+ unordered_set<int> rest(restricted.begin(), restricted.end());
+ vector<vector<int>> adj(n, vector<int>());
+
+ for (auto &p : edges) {
+ if (rest.count(p[0]) || rest.count(p[1])) continue;
+ adj[p[0]].push_back(p[1]);
+ adj[p[1]].push_back(p[0]);
+ }
+
+ int res = 0;
+ stack<int> st;
+ vector<bool> visited(n, false);
+ st.push(0);
+ visited[0] = true;
+ while (!st.empty()) {
+ int root = st.top();
+ st.pop();
+ res++;
+ for (int c : adj[root])
+ if (!visited[c]) {
+ st.push(c);
+ visited[c] = true;
+ }
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -19,13 +19,17 @@ if you have any questions.
| 0019 | Medium | [Remove Nth Node From the End of List](Problems/0019.cpp) |
| 0020 | Easy | [Valid Parentheses](Problems/0020.cpp) |
| 0021 | Easy | [Merge Two Sorted Lists](Problems/0021.cpp) |
+| 0023 | Hard | [Merge k Sorted Lists](Problems/0023.cpp) |
| 0024 | Medium | [Swap Nodes in Pairs](Problems/0024.cpp) |
+| 0025 | Hard | [Reverse Nodes in k-Group](Problems/0025.cpp) |
| 0026 | Easy | [Remove Duplicates from Sorted Array](Problems/0026.cpp) |
| 0027 | Easy | [Remove Element](Problems/0027.cpp) |
| 0028 | Medium | [Find the Index of the First Occurrence in a String](Problems/0028.cpp) |
| 0036 | Medium | [Valid Sudoku](Problems/0036.cpp) |
| 0043 | Medium | [Multiply Strings](Problems/0043.cpp) |
+| 0049 | Medium | [Group Anagrams](Problems/0049.cpp) |
| 0054 | Medium | [Spiral Matrix](Problems/0054.cpp) |
+| 0055 | Medium | [Jump Game](Problems/0055.cpp) |
| 0059 | Medium | [Spiral Matrix II](Problems/0059.cpp) |
| 0061 | Medium | [Rotate List](Problems/0061.cpp) |
| 0066 | Easy | [Plus One](Problems/0066.cpp) |
@@ -48,7 +52,9 @@ if you have any questions.
| 0118 | Easy | [Pascal's Triangle](Problems/0118.cpp) |
| 0119 | Easy | [Pascal's Triangle II](Problems/0119.cpp) |
| 0121 | Easy | [Best Time to Buy and Sell Stock](Problems/0121.cpp) |
+| 0122 | Medium | [Best Time to Buy and Sell Stock II](Problems/0122.cpp) |
| 0124 | Hard | [Binary Tree Maximum Path Sum](Problems/0124.cpp) |
+| 0125 | Easy | [Valid Palindrome](Problems/0125.cpp) |
| 0133 | Medium | [Clone Graph](Problems/0133.cpp) |
| 0138 | Medium | [Copy List with Random Pointer](Problems/0138.cpp) |
| 0141 | Easy | [Linked List Cycle](Problems/0141.cpp) |
@@ -57,6 +63,7 @@ if you have any questions.
| 0145 | Easy | [Binary Tree Postorder Traversal](Problems/0145.cpp) |
| 0150 | Medium | [Evaluate Reverse Polish Notation](Problems/0150.cpp) |
| 0151 | Medium | [Reverse Words in a String](Problems/0151.cpp) |
+| 0155 | Medium | [Min Stack](Problems/0155.cpp) |
| 0160 | Easy | [Intersection of Two Linked Lists](Problems/0160.cpp) |
| 0167 | Medium | [Two Sum II - Input Array Is Sorted](Problems/0167.cpp) |
| 0189 | Medium | [Rotate Array](Problems/0189.cpp) |
@@ -66,20 +73,25 @@ if you have any questions.
| 0203 | Easy | [Remove Linked List Elements](Problems/0203.cpp) |
| 0206 | Easy | [Reverse Linked List](Problems/0206.cpp) |
| 0209 | Medium | [Minimum Size Subarray Sum](Problems/0209.cpp) |
+| 0217 | Easy | [Contains Duplicate](Problems/0217.cpp) |
| 0222 | Medium | [Count Complete Tree Nodes](Problems/0222.cpp) |
| 0223 | Medium | [Rectangle Area](Problems/0223.cpp) |
| 0226 | Easy | [Invert Binary Tree](Problems/0226.cpp) |
| 0234 | Easy | [Palindrome Linked List](Problems/0234.cpp) |
| 0236 | Medium | [Lowest Common Ancestor of a Binary Tree](Problems/0236.cpp) |
| 0237 | Medium | [Delete Node in a Linked List](Problems/0237.cpp) |
+| 0238 | Medium | [Product of Array Except Self](Problems/0238.cpp) |
+| 0242 | Easy | [Valid Anagram](Problems/0242.cpp) |
| 0257 | Easy | [Binary Tree Paths](Problems/0257.cpp) |
| 0263 | Easy | [Ugly Number](Problems/0263.cpp) |
| 0279 | Medium | [Perfect Squares](Problems/0279.cpp) |
| 0283 | Easy | [Move Zeroes](Problems/0283.cpp) |
+| 0287 | Medium | [Find the Duplicate Number](Problems/0287.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
| 0338 | Easy | [Counting Bits](Problems/0338.cpp) |
| 0344 | Easy | [Reverse String](Problems/0344.cpp) |
| 0345 | Easy | [Reverse Vowels of a String](Problems/0345.cpp) |
+| 0347 | Medium | [Top K Frequent Elements](Problems/0347.cpp) |
| 0374 | Easy | [Guess Number Higher or Lower](Problems/0374.cpp) |
| 0383 | Easy | [Ransom Note](Problems/0383.cpp) |
| 0387 | Easy | [First Unique Character in a String](Problems/0387.cpp) |
@@ -121,10 +133,12 @@ if you have any questions.
| 0747 | Easy | [Largest Number At Least Twice of Others](Problems/0747.cpp) |
| 0752 | Medium | [Open the Lock](Problems/0752.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
+| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
| 0876 | Easy | [Middle of the Linked List](Problems/0876.cpp) |
+| 0886 | Medium | [Possible Bipartition](Problems/0886.cpp) |
| 0901 | Medium | [Online Stock Span](Problems/0901.cpp) |
| 0905 | Easy | [Sort Array By Parity](Problems/0905.cpp) |
| 0931 | Medium | [Minimum Falling Path Sum](Problems/0931.cpp) |
@@ -165,6 +179,7 @@ if you have any questions.
| 1557 | Medium | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp) |
| 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |
| 1609 | Medium | [Even Odd Tree](Problems/1609.cpp) |
+| 1615 | Medium | [Maximal Network Rank](Problems/1615.cpp) |
| 1646 | Easy | [Get Maximum in Generated Array](Problems/1646.cpp) |
| 1669 | Medium | [Merge In Between Linked Lists](Problems/1669.cpp) |
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
@@ -186,6 +201,7 @@ if you have any questions.
| 2285 | Medium | [Maximum Total Importance of Roads](Problems/2285.cpp) |
| 2326 | Medium | [Spiral Matrix IV](Problems/2326.cpp) |
| 2331 | Easy | [Evaluate Boolean Binary Tree](Problems/2331.cpp) |
+| 2368 | Medium | [Reachable Nodes With Restrictions](Problems/2368.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
| 2465 | Easy | [Number of Distinct Averages](Problems/2465.cpp) |
| 2466 | Medium | [Count Ways To Build Good Strings](Problems/2466.cpp) |
