Posts tagged as “medium”

花花酱 1276. Number of Burgers with No Waste of Ingredients

By zxi on December 1, 2019

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

Jumbo Burger: 4 tomato slices and 1 cheese slice.
Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]

Example 5:

Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]

Constraints:

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

vector<int> numOfBurgers(int T, int C) {

// Jumbo = x, small = y

// 4x + 2y = T

// x + y = C

// x = (T - 2C) / 2

int x = T / 2 - C;

int y = C - x;

if (4 * x + 2 * y == T && x >= 0 && y >= 0) return {x, y};

return {};

}

};

花花酱 LeetCode 1273. Delete Tree Nodes

By zxi on November 30, 2019

A tree rooted at node 0 is given as follows:

The number of nodes is nodes;
The value of the i-th node is value[i];
The parent of the i-th node is parent[i].

Remove every subtree whose sum of values of nodes is zero.

After doing so, return the number of nodes remaining in the tree.

Example 1:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

Constraints:

1 <= nodes <= 10^4
-10^5 <= value[i] <= 10^5
parent.length == nodes
parent[0] == -1 which indicates that 0 is the root.

Solution: Inorder Traversal

For each node, return the sum of all its subtrees and number of nodes including itself after removal.

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

C++

// Author: Huahua

class Solution {

public:

int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {

vector<vector<int>> g(nodes);

for (int i = 1; i < nodes; ++i)

g[parent[i]].push_back(i);

// Returns <sum, nodes> of subtree n.

function<pair<int,int>(int)> traverse = [&](int n) {

int sum = value[n];

int count = 1;

for (int x : g[n]) {

auto [s, c] = traverse(x);

sum += s;

count += s ? c : 0;

}

return make_pair(sum, sum ? count : 0);

};

return traverse(0).second;

}

};

花花酱 LeetCode 1272. Remove Interval

By zxi on November 30, 2019

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:

1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Solution: Geometry

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& r) {

vector<vector<int>> ans;

for (const auto& i : intervals)

// Does not intersect

if (i[1] <= r[0] || i[0] >= r[1])

ans.push_back(i);

else {

// i starts first

if (i[0] < r[0])

ans.push_back({i[0], r[0]});

// i ends later

if (i[1] > r[1])

ans.push_back({r[1], i[1]});

}

return ans;

}

};

花花酱 LeetCode 1262. Greatest Sum Divisible by Three

By zxi on November 26, 2019

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

Solution: DP

dp[i] := max sum that has a remainder i when mod 3.

dp[(i + num) % 3] = max( dp[(i + num) % 3] , dp[i] + num)

ans: dp[0]

C++

// Author: Huahua

class Solution {

public:

int maxSumDivThree(vector<int>& nums) {

vector<int> dp(3);

for (int num : nums) {

vector<int> tmp(dp);

for (int s : tmp)

dp[(s + num) % 3] = max(dp[(s + num) % 3], s + num);

}

return dp[0];

}

};

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

By zxi on November 26, 2019

Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output

[null,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output

[null,true,true,false]

Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output

[null,true,false,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.find(5); // return True

Constraints:

TreeNode.val == -1
The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6

Solutoin 1: Recursion and HashSet

Time complexity: Recover O(n), find O(1)
Space complexity: O(n)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root) {

recover(root, 0);

}

bool find(int target) {

return s_.count(target);

}

private:

unordered_set<int> s_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

s_.insert(val);

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

Solution 2: Recursion and Binary format

The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1

e.g. target = 13, t = 13 + 1 = 14

t = 14, t % 1 = 0, t / 2 = 7, left

t = 7, t % 1 = 1, t / 2 = 3, right

t = 3, t % 1 = 1, t / 2 = 1, right

13 => right, right, left

Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root): root_(root) {

recover(root, 0);

}

bool find(int target) {

++target;

stack<bool> right;

while (target != 1) {

right.push(target & 1);

target >>= 1;

}

TreeNode* node = root_;

while (!right.empty() && node) {

node = right.top() ? node->right : node->left;

right.pop();

}

return node;

}

private:

TreeNode* root_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};