leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

commit	93c4fbb9b604739d4084d9d7d6587946515abaf0
parent	9eb5c5a876e83fa6ddda352dd4a9f06a947ba20b
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Thu, 11 Jan 2024 19:55:05 +0000

Improved Daily Problem and 1 Random Problem

Diffstat:

A	Problems/0667.cpp	\|	+++++++++++++
M	Problems/1026.cpp	\|	+++++++----------
M	README.md	\|	+

3 files changed, 21 insertions(+), 10 deletions(-)

diff --git a/Problems/0667.cpp b/Problems/0667.cpp

@@ -0,0 +1,13 @@

class Solution {

public:

vector<int> constructArray(int n, int k) const {

vector<int> res(n);

int idx = 0;

for (int i = 1; i < n - k; i++)

res[idx++] = i;

for (int i = 0; i <= k; i++) {

res[idx++] = i % 2 ? n - i / 2 : n - k + i / 2;

}

return res;

}

};

diff --git a/Problems/1026.cpp b/Problems/1026.cpp

@@ -3,18 +3,15 @@ class Solution {

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}});

stack<tuple<TreeNode *, 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;

auto [root, maxi, mini] = st.top();

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)}});

res = max({res, abs(maxi - root->val), abs(mini - root->val)});

maxi = max(maxi, root->val), mini = min(mini, root->val);

if (root->left) st.push({root->left, maxi, mini});

if (root->right) st.push({root->right, maxi, mini});

}

return res;

}

diff --git a/README.md b/README.md

@@ -414,6 +414,7 @@ for solving problems.

| 0661 | Easy | [Image Smoother](Problems/0661.cpp) |

| 0662 | Medium | [Maximum Width of Binary Tree](Problems/0662.cpp) |

| 0664 | Hard | [Strange Printer](Problems/0664.cpp) |

| 0667 | Medium | [Beautiful Arrangement II](Problems/0667.cpp) |

| 0669 | Medium | [Trim a Binary Search Tree](Problems/0669.cpp) |

| 0671 | Easy | [Second Minimum Node In a Binary Tree](Problems/0671.cpp) |

| 0673 | Medium | [Number of Longest Increasing Subsequence](Problems/0673.cpp) |