Huahua’s Tech Road

花花酱 LeetCode 2236. Root Equals Sum of Children

By zxi on April 16, 2022

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6]
Output: true
Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.
10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1]
Output: false
Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.
5 is not equal to 3 + 1, so we return false.

Constraints:

The tree consists only of the root, its left child, and its right child.
-100 <= Node.val <= 100

Solution:

Just want to check whether you know binary tree or not.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkTree(TreeNode* root) {

return root->val == root->left->val + root->right->val;

}

};

花花酱 LeetCode 2235. Add Two Integers

By zxi on April 16, 2022

Given two integers num1 and num2, return the sum of the two integers.

Example 1:

Input: num1 = 12, num2 = 5
Output: 17
Explanation: num1 is 12, num2 is 5, and their sum is 12 + 5 = 17, so 17 is returned.

Example 2:

Input: num1 = -10, num2 = 4
Output: -6
Explanation: num1 + num2 = -6, so -6 is returned.

Constraints:

-100 <= num1, num2 <= 100

Solution: Just sum them up

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int sum(int num1, int num2) {

return num1 + num2;

}

};

花花酱 LeetCode 2233. Maximum Product After K Increments

By zxi on April 9, 2022

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

Solution: priority queue

Always increment the smallest number. Proof?

Time complexity: O(klogn + nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumProduct(vector<int>& nums, int k) {

constexpr int kMod = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums));

while (k--) {

const int n = q.top();

q.pop();

q.push(n + 1);

}

long long ans = 1;

while (!q.empty()) {

ans *= q.top(); q.pop();

ans %= kMod;

}

return ans;

}

};

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

By zxi on April 9, 2022

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Solution: Brute Force

Try all possible positions to add parentheses and evaluate the new expression.

Time complexity: O(n²)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string minimizeResult(string expression) {

const int n = expression.size();

auto p = expression.find('+');

int best = INT_MAX;

string ans;

for (int l = 0; l < p; ++l)

for (int r = p + 2; r < n + 1; ++r) {

const int m1 = l ? stoi(expression.substr(0, l)) : 1;

const int m2 = (r < n) ? stoi(expression.substr(r)) : 1;

const int n1 = stoi(expression.substr(l, p));

const int n2 = stoi(expression.substr(p + 1, r - p - 1));

const int cur = m1 * (n1 + n2) * m2;

if (cur < best) {

best = cur;

ans = expression;

ans.insert(l, "(");

ans.insert(r + 1, ")");

}

return ans;

}

};

花花酱 LeetCode 2231. Largest Number After Digit Swaps by Parity

By zxi on April 9, 2022

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

1 <= num <= 10⁹

Solution:

Put all even digits into one array, all odd digits into another one, all digits into the third. Sort two arrays, and generate a new number from sorted arrays.

Time complexity: O(logn*loglogn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int largestInteger(int num) {

vector<int> odd, even, org;

for (int cur = num; cur; cur /= 10) {

((cur & 1) ? odd : even).push_back(cur % 10);

org.push_back(cur % 10);

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

int ans = 0;

for (int i = 0; i < org.size(); ++i) {

if (i) ans *= 10;

auto& cur = (org[org.size() - i - 1] & 1) ? odd : even;

ans += cur.back();

cur.pop_back();

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2236. Root Equals Sum of Children

Solution:

C++

花花酱 LeetCode 2235. Add Two Integers

Solution: Just sum them up

C++

花花酱 LeetCode 2233. Maximum Product After K Increments

Solution: priority queue

C++

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

Solution: Brute Force

C++

花花酱 LeetCode 2231. Largest Number After Digit Swaps by Parity

C++