Huahua’s Tech Road

花花酱 LeetCode 1710. Maximum Units on a Truck

By zxi on January 2, 2021

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_iis the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints:

1 <= boxTypes.length <= 1000
1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

Solution: Greedy

Sort by unit in descending order.

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

C++

// Author: Huahua

class Solution {

public:

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {

sort(begin(boxTypes), end(boxTypes), [](const auto& a, const auto& b){

return a[1] > b[1]; // Sort by unit DESC

});

int ans = 0;

for (const auto& b : boxTypes) {

ans += b[1] * min(b[0], truckSize);

if ((truckSize -= b[0]) <= 0) break;

}

return ans;

}

};

Consistent Hashing

By zxi on December 30, 2020

花花酱 LeetCode 1707. Maximum XOR With an Element From Array

By zxi on December 27, 2020

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Solution: Trie on the fly

We can build the trie on the fly by sorting nums in ascending order and queries by its limit, insert nums into the trie up the limit.

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

C++

// Author: Huahua

class Trie {

public:

Trie(): children{nullptr, nullptr} {}

Trie* children[2];

};

class Solution {

public:

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {

const int n = nums.size();

sort(begin(nums), end(nums));

const int Q = queries.size();

for (int i = 0; i < Q; ++i)

queries[i].push_back(i);

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2) {

return q1[1] < q2[1];

});

Trie root;

auto insert = [&](int num) {

Trie* node = &root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = new Trie();

node = node->children[bit];

}

};

auto query = [&](int num) {

Trie* node = &root;

int sum = 0;

for (int i = 31; i >= 0; --i) {

if (!node) return -1;

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum |= (1 << i);

node = node->children[1 - bit];

} else {

node = node->children[bit];

}

return sum;

};

vector<int> ans(Q);

int i = 0;

for (const auto& q : queries) {

while (i < n && nums[i] <= q[1]) insert(nums[i++]);

ans[q[2]] = query(q[0]);

}

return ans;

}

};

花花酱 LeetCode 421. Maximum XOR of Two Numbers in an Array

By zxi on December 27, 2020

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

1 <= nums.length <= 2 * 10⁴
0 <= nums[i] <= 2³¹ - 1

Solution: Trie

Time complexity: O(31*2*n)
Space complexity: O(31*2*n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children(2) {}

vector<unique_ptr<Trie>> children;

};

class Solution {

public:

int findMaximumXOR(vector<int>& nums) {

Trie root;

// Insert a number into the trie.

auto insert = [&](Trie* node, int num) {

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = std::make_unique<Trie>();

node = node->children[bit].get();

}

};

// Find max xor sum of num and another element in the array.

auto query = [&](Trie* node, int num) {

int sum = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum += (1 << i);

node = node->children[1 - bit].get();

} else {

node = node->children[bit].get();

}

return sum;

};

// Insert all numbers.

for (int x : nums)

insert(&root, x);

int ans = 0;

// For each number find the maximum xor sum.

for (int x : nums)

ans = max(ans, query(&root, x));

return ans;

}

};

花花酱 LeetCode 1706. Where Will the Ball Fall

By zxi on December 27, 2020

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a “V” shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the i^th column at the top, or -1 if the ball gets stuck in the box.

Example 1:

Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
Explanation: This example is shown in the photo.
Ball b0 is dropped at column 0 and falls out of the box at column 1.
Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.
Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.

Example 2:

Input: grid = [[-1]]
Output: [-1]
Explanation: The ball gets stuck against the left wall.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] is 1 or -1.

Solution: Simulation

Figure out 4 conditions that the ball will get stuck.

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> findBall(vector<vector<int>>& G) {

const int m = G.size();

const int n = G[0].size();

auto fall = [&](int x) -> int {

for (int y = 0; y < m; ++y)

if ((G[y][x] == -1 && (x == 0 || G[y][x - 1] == 1)) ||

(G[y][x] == 1 && (x == n - 1 || G[y][x + 1] == -1)))

return -1;

else

x += G[y][x];

return x;

};

vector<int> ans(n);

for (int x = 0; x < n; ++x)

ans[x] = fall(x);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1710. Maximum Units on a Truck

Solution: Greedy

C++

Consistent Hashing

花花酱 LeetCode 1707. Maximum XOR With an Element From Array

Solution: Trie on the fly

C++

花花酱 LeetCode 421. Maximum XOR of Two Numbers in an Array

Solution: Trie

C++

花花酱 LeetCode 1706. Where Will the Ball Fall

Solution: Simulation

C++