commit 76e6c84f4d1f40b5982d9b626c1d592e735e49db
parent fc752a9fdb9fc285e98d4b11810af07996c6e0da
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 3 Jan 2023 21:15:15 +0100
Remove DNF section
- README.md
* I've finished all DNF problems
* Template section is now at the top
Diffstat:
9 files changed, 177 insertions(+), 113 deletions(-)
diff --git a/Problems/0129.cpp b/Problems/0129.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+ int sumNumbers(TreeNode *root) {
+ if (!root) return 0;
+
+ int sum = 0, res = 0;
+ stack<pair<TreeNode *, int>> st;
+ while (true) {
+ while (root) {
+ sum *= 10;
+ sum += root->val;
+ if (root->right)
+ st.push({root->right, sum});
+ else if (!root->left)
+ res += sum;
+ root = root->left;
+ }
+ if (st.empty()) break;
+ root = st.top().first;
+ sum = st.top().second;
+ st.pop();
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0143.cpp b/Problems/0143.cpp
@@ -0,0 +1,18 @@
+class Solution {
+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++;
+ }
+ }
+ return j - i;
+ }
+};
diff --git a/Problems/0239.cpp b/Problems/0239.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ vector<int> maxSlidingWindow(vector<int> &nums, int k) {
+ int n = nums.size();
+ vector<int> res;
+ deque<int> q;
+
+ res.reserve(n - k + 1);
+ for (int i = 0; i < n; i++) {
+ while (!q.empty() && q.front() < i - k + 1) q.pop_front();
+ while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
+ q.push_back(i);
+ if (i >= k - 1) res.push_back(nums[q.front()]);
+ }
+ return res;
+ }
+};
diff --git a/Problems/0402.cpp b/Problems/0402.cpp
@@ -1,26 +1,28 @@
class Solution {
-public:
- string removeKdigits(string num, int k) {
- stack<char> st;
- for (char c : num) {
- while (k && !st.empty() && c < st.top()) {
- k--;
- st.pop();
- }
- if (st.empty() && c == '0') continue;
- st.push(c);
- }
- string res = "";
+ class Solution {
+ public:
+ string removeKdigits(string num, int k) {
+ if (num.length() <= k) return "0";
+ if (k == 0) return num;
- while (!st.empty() && k--) st.pop();
+ string res = "";
+ stack<char> s;
- while (!st.empty()) {
- res = st.top() + res;
- st.pop();
- }
+ s.push(num[0]);
+ for (int i = 1; i < num.length(); ++i) {
+ while (k > 0 && !s.empty() && num[i] < s.top()) {
+ --k;
+ s.pop();
+ }
+ s.push(num[i]);
+ if (s.size() == 1 && num[i] == '0') s.pop();
+ }
+
+ while (k && !s.empty()) --k, s.pop();
- if (res == "") return "0";
+ while (!s.empty()) res.push_back(s.top()), s.pop();
- return res;
- }
-};
+ reverse(res.begin(), res.end());
+ return res.size() ? res : "0";
+ }
+ };
diff --git a/Problems/0542.cpp b/Problems/0542.cpp
@@ -1,52 +1,45 @@
class Solution {
- queue<pair<int, int>> q;
int m, n;
-
- typedef vector<vector<int>> vvi;
+ vector<pair<int, int>> offset = {
+ {-1, 0},
+ { 1, 0},
+ { 0, -1},
+ { 0, 1}
+ };
int valid(int sr, int sc) { return sr >= 0 && sr < m && sc >= 0 && sc < n; }
- void add(vvi &mat, int sr, int sc) {
- cout << sr << " " << sc << " valid is: " << valid(sr, sc) << endl;
- if (valid(sr, sc) && mat[sr][sc] != 0) q.push(make_pair(sr, sc));
- }
-
- void ff(vvi &mat, vvi &res, int sr, int sc) {
- q.push(make_pair(sr, sc));
- for (int lvl = 0; !q.empty(); lvl++) {
- for (int t = q.size(); t > 0; t--) {
- int sr = q.front().first;
- int sc = q.front().second;
- cout << "lvl" << lvl << ": " << sr << " " << sc << endl;
- q.pop();
-
- if (!res[sr][sc] || res[sr][sc] > lvl)
- res[sr][sc] = lvl;
- else
- continue;
-
- cout << "adding" << endl;
- add(mat, sr + 1, sc);
- add(mat, sr - 1, sc);
- add(mat, sr, sc + 1);
- add(mat, sr, sc - 1);
- }
- }
- cout << "end FF" << endl;
- }
-
public:
- vector<vector<int>> updateMatrix(vvi &mat) {
+ vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
m = mat.size();
n = mat[0].size();
- cout << m << " " << n << endl;
+ vector<vector<int>> res(m, vector<int>(n, INT_MAX));
+ queue<pair<int, int>> q;
- vvi res(m, vector<int>(n, 0));
+ for (int i = 0; i < m; i++) {
+ for (int j = 0; j < n; j++) {
+ if (mat[i][j] == 0) {
+ res[i][j] = 0;
+ q.push({i, j});
+ }
+ }
+ }
- for (int i = 0; i < m; i++)
- for (int j = 0; j < n; j++)
- if (mat[i][j] == 0) ff(mat, res, i, j);
+ while (!q.empty()) {
+ auto [sr, sc] = q.front();
+ q.pop();
+ for (auto &p : offset) {
+ int nsr = sr + p.first;
+ int nsc = sc + p.second;
+ if (valid(nsr, nsc)) {
+ if (res[nsr][nsc] > res[sr][sc] + 1) {
+ res[nsr][nsc] = res[sr][sc] + 1;
+ q.push({nsr, nsc});
+ }
+ }
+ }
+ }
return res;
}
diff --git a/Problems/0662.cpp b/Problems/0662.cpp
@@ -1,25 +1,25 @@
class Solution {
public:
int widthOfBinaryTree(TreeNode *root) {
- int maxi = 0;
- queue<TreeNode *> q;
- q.push(root);
- for (int lvl = 0; !q.empty(); lvl++) {
- int first = -1, last = -1;
- for (int t = q.size(); t > 0; t--) {
- TreeNode *root = q.front();
+ if (root == NULL) return 0;
+ queue<pair<TreeNode *, int>> q;
+
+ int res = 1;
+ q.push({root, 0});
+ while (!q.empty()) {
+ int start = q.front().second, end = q.back().second;
+
+ res = max(res, end - start + 1);
+ for (int k = q.size(); k > 0; k--) {
+ pair<TreeNode *, int> p = q.front();
q.pop();
- if (root) {
- if (first == -1) first = t;
- last = t;
- }
- if (!root) continue;
+ int idx = p.second - start;
- q.push(root->left);
- q.push(root->right);
+ if (p.first->left) q.push({p.first->left, 2ll * idx + 1});
+ if (p.first->right) q.push({p.first->right, 2ll * idx + 2});
}
- maxi = max(maxi, first - last);
}
- return maxi;
+
+ return res;
}
};
diff --git a/Problems/1425.cpp b/Problems/1425.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ int constrainedSubsetSum(vector<int> &nums, int k) {
+ deque<int> q;
+ int res = nums[0];
+ for (int i = 0; i < nums.size(); ++i) {
+ nums[i] += !q.empty() ? q.front() : 0;
+ res = max(res, nums[i]);
+ while (!q.empty() && nums[i] > q.back()) q.pop_back();
+ if (nums[i] > 0) q.push_back(nums[i]);
+ if (i >= k && !q.empty() && q.front() == nums[i - k]) q.pop_front();
+ }
+ return res;
+ }
+};
diff --git a/Problems/2461.cpp b/Problems/2461.cpp
@@ -1,26 +1,18 @@
class Solution {
public:
long long maximumSubarraySum(vector<int> &nums, int k) {
- long long maxi = LLONG_MIN;
- unordered_set<int> us;
- int i = 0;
- long long sum = 0ll;
- for (int j = 0; j <= size(nums);) {
- while (us.find(nums[j]) != us.end()) {
- sum -= nums[i];
- us.erase(nums[i++]);
- }
- if (j - i < k) {
- sum += nums[j];
- us.insert(nums[j++]);
- }
- if (j > size(nums)) break;
- if (j - i == k) {
- maxi = max(sum, maxi);
- sum -= nums[i];
- us.erase(nums[i++]);
- }
+ unordered_map<int, int> mp;
+ long maxi = 0, sum = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ sum += nums[i];
+ mp[nums[i]]++;
+
+ if (i < k - 1) continue;
+ if (mp.size() == k) maxi = max(maxi, sum);
+ int &tmp = nums[i - k + 1];
+ sum -= tmp;
+ if (--mp[tmp] == 0) mp.erase(tmp);
}
- return maxi == LLONG_MIN ? 0 : maxi;
+ return maxi;
}
};
diff --git a/README.md b/README.md
@@ -10,6 +10,15 @@ update this list periodically as I do more problems. I hope it will be helpful
to some of you if you get stuck on a specific problem. Feel free to contact me
if you have any questions.
+## Templates
+
+I have accumulated a list of most commonly used algorithms to serve as a base
+for solving problems.
+
+* [Union Find](Templates/Union_Find.cpp)
+* [MST from edge vector](Templates/MST_vector.cpp)
+* [MST from edge priority queue](Templates/MST_pq.cpp)
+
## Problems
| Number | Difficulty | Solution |
@@ -64,6 +73,7 @@ if you have any questions.
| 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) |
+| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.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) |
@@ -94,6 +104,7 @@ if you have any questions.
| 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) |
+| 0239 | Hard | [Sliding Window Maximum](Problems/0239.cpp) |
| 0242 | Easy | [Valid Anagram](Problems/0242.cpp) |
| 0257 | Easy | [Binary Tree Paths](Problems/0257.cpp) |
| 0263 | Easy | [Ugly Number](Problems/0263.cpp) |
@@ -113,6 +124,7 @@ if you have any questions.
| 0392 | Easy | [Is Subsequence](Problems/0392.cpp) |
| 0394 | Medium | [Decode String](Problems/0394.cpp) |
| 0399 | Medium | [Evaluate Division](Problems/0399.cpp) |
+| 0402 | Medium | [Remove K Digits](Problems/0402.cpp) |
| 0404 | Easy | [Sum of Left Leaves](Problems/0404.cpp) |
| 0412 | Easy | [Fizz Buzz](Problems/0412.cpp) |
| 0414 | Easy | [Third Maximum Number](Problems/0414.cpp) |
@@ -133,6 +145,7 @@ if you have any questions.
| 0520 | Easy | [Detect Capital](Problems/0520.cpp) |
| 0530 | Easy | [Minimum Absolute Difference in BST](Problems/0530.cpp) |
| 0538 | Medium | [Convert BST to Greater Tree](Problems/0538.cpp) |
+| 0542 | Medium | [01 Matrix](Problems/0542.cpp) |
| 0543 | Easy | [Diameter of Binary Tree](Problems/0543.cpp) |
| 0547 | Medium | [Number of Provinces](Problems/0547.cpp) |
| 0556 | Medium | [Next Greater Element III](Problems/0556.cpp) |
@@ -148,6 +161,7 @@ if you have any questions.
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
| 0653 | Easy | [Two Sum IV - Input is a BST](Problems/0653.cpp) |
| 0654 | Medium | [Maximum Binary Tree](Problems/0654.cpp) |
+| 0662 | Medium | [Maximum Width of Binary Tree](Problems/0662.cpp) |
| 0669 | Medium | [Trim a Binary Search Tree](Problems/0669.cpp) |
| 0671 | Easy | [Second Minimum Node In a Binary Tree](Problems/0671.cpp) |
| 0684 | Medium | [Redundant Connection](Problems/0684.cpp) |
@@ -178,6 +192,7 @@ if you have any questions.
| 0933 | Easy | [Number of Recent Calls](Problems/0933.cpp) |
| 0938 | Easy | [Range Sum of BST](Problems/0938.cpp) |
| 0941 | Easy | [Valid Mountain Array](Problems/0941.cpp) |
+| 0944 | Easy | [Delete Columns to Make Sorted](Problems/0944.cpp) |
| 0947 | Medium | [Most Stones Removed with Same Row or Column](Problems/0947.cpp) |
| 0950 | Medium | [Reveal Cards In Increasing Order](Problems/0950.cpp) |
| 0959 | Medium | [Regions Cut By Slashes](Problems/0959.cpp) |
@@ -218,9 +233,12 @@ if you have any questions.
| 1373 | Hard | [Maximum Sum BST in Binary Tree](Problems/1373.cpp) |
| 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) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
| 1472 | Medium | [Design Browser History ](Problems/1472.cpp) |
| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |
+| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |
| 1514 | Medium | [Path with Maximum Probability](Problems/1514.cpp) |
| 1544 | Easy | [Make The String Great](Problems/1544.cpp) |
| 1557 | Medium | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp) |
@@ -260,27 +278,10 @@ if you have any questions.
| 2368 | Medium | [Reachable Nodes With Restrictions](Problems/2368.cpp) |
| 2374 | Medium | [Node With Highest Edge Score](Problems/2374.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
+| 2461 | Medium | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp) |
| 2465 | Easy | [Number of Distinct Averages](Problems/2465.cpp) |
| 2466 | Medium | [Count Ways To Build Good Strings](Problems/2466.cpp) |
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
-| 0944 | Easy | [Delete Columns to Make Sorted](Problems/0944.cpp) |
-| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |
-
-## Templates
-
-* [Union Find](Templates/Union_Find.cpp)
-* [MST from edge vector](Templates/MST_vector.cpp)
-* [MST from edge priority queue](Templates/MST_pq.cpp)
-## DNF
-
-| Number | Difficulty | Solution |
-|:------:|:----------:|-------------------------------------------------------------------------------------------------|
-| 0402 | Medium | [Remove K Digits](Problems/0402.cpp) |
-| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.cpp) |
-| 0542 | Medium | [01 Matrix](Problems/0542.cpp) |
-| 0662 | Medium | [Maximum Width of Binary Tree](Problems/0662.cpp) |
-| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/0143.cpp) |
-| 2461 | Medium | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp) |
