commit b4e4ea8d0be765c17741baeb806ee34e5c179f03
parent 87740c85dacf580478a2d2d4f0b655cdd611a34f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 11 Dec 2022 16:49:56 +0100
Add some daily problems
Diffstat:
5 files changed, 138 insertions(+), 0 deletions(-)
diff --git a/Problems/0124.cpp b/Problems/0124.cpp
@@ -0,0 +1,41 @@
+class Solution {
+public:
+ int maxPathSum(TreeNode *root) {
+ if (!root) return 0;
+ int res = INT_MIN;
+
+ unordered_set<TreeNode *> us;
+ stack<TreeNode *> st;
+ while (root) {
+ st.push(root);
+ root = root->left;
+ }
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+
+ if (us.find(root) == us.end()) {
+ st.push(root);
+ us.insert(root);
+ root = root->right;
+ while (root) {
+ st.push(root);
+ root = root->left;
+ }
+ } else {
+ int opt = 0, sum = 0;
+ if (root->left) {
+ opt = max(opt, root->left->val), sum += root->left->val;
+ };
+ if (root->right) {
+ opt = max(opt, root->right->val), sum += root->right->val;
+ };
+ res = max(res, root->val + sum);
+ root->val = max(root->val, root->val + opt);
+ res = max(res, root->val);
+ continue;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0938.cpp b/Problems/0938.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+ Solution() {
+ ios_base::sync_with_stdio(false);
+ cin.tie(nullptr);
+ cout.tie(nullptr);
+ }
+ int rangeSumBST(TreeNode *root, int low, int high) {
+ int sum = 0;
+ stack<TreeNode *> st;
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+ if (root->val >= low && root->val <= high) sum += root->val;
+ if (root->left && root->val > low) st.push(root->left);
+ if (root->right && root->val < high) st.push(root->right);
+ }
+ return sum;
+ }
+};
diff --git a/Problems/1026.cpp b/Problems/1026.cpp
@@ -0,0 +1,30 @@
+class Solution {
+public:
+ int maxAncestorDiff(TreeNode *root) {
+ if (!root) return 0;
+ int res = 0;
+ stack<pair<TreeNode *, pair<int, int>>> st;
+ st.push({
+ root, {root->val, root->val}
+ });
+ while (!st.empty()) {
+ TreeNode *root = st.top().first;
+ int maxi = st.top().second.first;
+ int mini = st.top().second.second;
+ st.pop();
+ res = max(res, abs(maxi - root->val));
+ res = max(res, abs(mini - root->val));
+ if (root->left)
+ st.push({
+ root->left,
+ {max(maxi, root->left->val), min(mini, root->left->val)}
+ });
+ if (root->right)
+ st.push({
+ root->right,
+ {max(maxi, root->right->val), min(mini, root->right->val)}
+ });
+ }
+ return res;
+ }
+};
diff --git a/Problems/1339.cpp b/Problems/1339.cpp
@@ -0,0 +1,41 @@
+class Solution {
+public:
+ int maxProduct(TreeNode *root) {
+ if (!root) return 0;
+ const unsigned int M = 1000000007;
+ stack<TreeNode *> st;
+ st.push(root);
+ unordered_set<TreeNode *> visited;
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+ if (visited.find(root) != visited.end()) {
+ if (root->left) root->val += root->left->val;
+ if (root->right) root->val += root->right->val;
+ root->val %= M;
+ continue;
+ }
+ st.push(root);
+ visited.insert(root);
+ if (root->left) st.push(root->left);
+ if (root->right) st.push(root->right);
+ }
+
+ long long res = 0ll;
+ int total = root->val;
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+ if (root->left) {
+ res = max(res, 1ll * root->left->val * (total - root->left->val));
+ st.push(root->left);
+ }
+ if (root->right) {
+ res = max(res, 1ll * root->right->val * (total - root->right->val));
+ st.push(root->right);
+ }
+ }
+ return res % M;
+ }
+};
diff --git a/README.md b/README.md
@@ -48,6 +48,7 @@ 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) |
+| 0124 | Hard | [Binary Tree Maximum Path Sum](Problems/0124.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) |
@@ -126,6 +127,7 @@ if you have any questions.
| 0901 | Medium | [Online Stock Span](Problems/0901.cpp) |
| 0905 | Easy | [Sort Array By Parity](Problems/0905.cpp) |
| 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) |
| 0947 | Medium | [Most Stones Removed with Same Row or Column](Problems/0947.cpp) |
| 0950 | Medium | [Reveal Cards In Increasing Order](Problems/0950.cpp) |
@@ -137,6 +139,7 @@ if you have any questions.
| 0997 | Easy | [Find the Town Judge](Problems/0997.cpp) |
| 1019 | Medium | [Next Greater Node In Linked List](Problems/1019.cpp) |
| 1022 | Easy | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp) |
+| 1026 | Medium | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp) |
| 1047 | Easy | [Remove All Adjacent Duplicates In String](Problems/1047.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |
@@ -148,6 +151,7 @@ if you have any questions.
| 1319 | Medium | [Number of Operations to Make Network Connected](Problems/1319.cpp) |
| 1323 | Easy | [Maximum 69 Number](Problems/1323.cpp) |
| 1337 | Easy | [The K Weakest Rows in a Matrix](Problems/1337.cpp) |
+| 1339 | Medium | [Maximum Product of Splitted Binary Tree](Problems/1339.cpp) |
| 1342 | Easy | [Number of Steps to Reduce a Number to Zero](Problems/1342.cpp) |
| 1346 | Easy | [Check if N and Its Double Exist](Problems/1346.cpp) |
| 1367 | Medium | [Linked List in Binary Tree ](Problems/1367.cpp) |
@@ -185,6 +189,7 @@ if you have any questions.
| 2466 | Medium | [Count Ways To Build Good Strings](Problems/2466.cpp) |
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
| 2469 | Hard | [Find Median from Data Stream](Problems/0295.cpp) |
+
## DNF
