Huahua’s Tech Road

花花酱 LeetCode 1829. Maximum XOR for Each Query

By zxi on April 17, 2021

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

nums.length == n
1 <= n <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.

Solution: Prefix XOR

Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first

to remove nums[i], we just need to do s ^= nums[i]

We can always maximize the xor of s and k to (2^maxbit – 1)
k = (2 ^ maxbit – 1) ^ s

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {

const int t = (1 << maximumBit) - 1;

const int n = nums.size();

vector<int> ans(n);

int s = 0;

for (int x : nums) s ^= x;

for (int i = n - 1; i >= 0; --i) {

ans[n - i - 1] = t ^ s;

s ^= nums[i];

}

return ans;

}

};

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

By zxi on April 17, 2021

You are given an array points where points[i] = [x_i, y_i] is the coordinates of the i^th point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array queries where queries[j] = [x_j, y_j, r_j] describes a circle centered at (x_j, y_j) with a radius of r_j.

For each query queries[j], compute the number of points inside the j^th circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the j^th query.

Example 1:

Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.

Example 2:

Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.

Constraints:

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= x_j, y_j <= 500
1 <= r_j <= 500
All coordinates are integers.

Solution: Brute Force

Time complexity: O(P * Q)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {

vector<int> ans;

ans.reserve(queries.size());

for (const auto& q : queries) {

const int rs = q[2] * q[2];

int cnt = 0;

for (const auto& p : points)

if ((q[0] - p[0]) * (q[0] - p[0]) +

(q[1] - p[1]) * (q[1] - p[1]) <= rs)

++cnt;

ans.push_back(cnt);

}

return ans;

}

};

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

By zxi on April 17, 2021

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1]
Output: 3
Explanation: You can do the following operations:
1) Increment nums[2], so nums becomes [1,1,2].
2) Increment nums[1], so nums becomes [1,2,2].
3) Increment nums[2], so nums becomes [1,2,3].

Example 2:

Input: nums = [1,5,2,4,1]
Output: 14

Example 3:

Input: nums = [8]
Output: 0

Constraints:

1 <= nums.length <= 5000
1 <= nums[i] <= 10⁴

Solution: Track Last

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

C++

class Solution {

public:

int minOperations(vector<int>& nums) {

int ans = 0, last = 0;

for (int x : nums)

if (x <= last)

ans += ++last - x;

else

last = x;

return ans;

}

};

花花酱 LeetCode 1825. Finding MK Average

By zxi on April 13, 2021

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
Remove the smallest k elements and the largest k elements from the container.
Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
void addElement(int num) Inserts a new element num into the stream.
int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]
Explanation MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // current elements are [3] obj.addElement(1); // current elements are [3,1] obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist. obj.addElement(10); // current elements are [3,1,10] obj.calculateMKAverage(); // The last 3 elements are [3,1,10]. // After removing smallest and largest 1 element the container will be [3]. // The average of [3] equals 3/1 = 3, return 3 obj.addElement(5); // current elements are [3,1,10,5] obj.addElement(5); // current elements are [3,1,10,5,5] obj.addElement(5); // current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); // The last 3 elements are [5,5,5]. // After removing smallest and largest 1 element the container will be [5]. // The average of [5] equals 5/1 = 5, return 5

Constraints:

3 <= m <= 10⁵
1 <= k*2 < m
1 <= num <= 10⁵
At most 10⁵ calls will be made to addElement and calculateMKAverage.

**Solution 1: Multiset * 3**

Use three multiset to track the left part (smallest k elements), right part (largest k elements) and mid (middle part of m – 2*k elements).

Time complexity: addElememt: O(logn), average: O(1)
Space complexity: O(n)

C++

class MKAverage {

public:

MKAverage(int m, int k):

sum(0), m(m), k(k), n(m - 2*k) {}

void addElement(int num) {

if (q.size() == m) {

remove(q.front());

q.pop();

}

q.push(num);

add(num);

}

int calculateMKAverage() {

return (q.size() < m) ? -1 : sum / n;

}

private:

void add(int x) {

left.insert(x);

if (left.size() > k) {

auto it = prev(end(left));

sum += *it;

mid.insert(*it);

left.erase(it);

}

if (mid.size() > n) {

auto it = prev(end(mid));

sum -= *it;

right.insert(*it);

mid.erase(it);

}

void remove(int x) {

if (x <= *rbegin(left)) {

left.erase(left.find(x));

} else if (x <= *rbegin(mid)) {

sum -= x;

mid.erase(mid.find(x));

} else {

right.erase(right.find(x));

}

if (left.size() < k) {

auto it = begin(mid);

sum -= *it;

left.insert(*it);

mid.erase(it);

}

if (mid.size() < n) {

auto it = begin(right);

sum += *it;

mid.insert(*it);

right.erase(it);

}

queue<int> q;

multiset<int> left, mid, right;

long sum;

const int m;

const int k;

const int n;

};

花花酱 LeetCode 1824. Minimum Sideway Jumps

By zxi on April 13, 2021

There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second laneand wants to jump to point n. However, there could be obstacles along the way.

You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point.

For example, if obstacles[2] == 1, then there is an obstacle on lane 1 at point 2.

The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.

For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.

Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.

Note: There will be no obstacles on points 0 and n.

Example 1:

Input: obstacles = [0,1,2,3,0]
Output: 2 
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).

Example 2:

Input: obstacles = [0,1,1,3,3,0]
Output: 0
Explanation: There are no obstacles on lane 2. No side jumps are required.

Example 3:

Input: obstacles = [0,2,1,0,3,0]
Output: 2
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.

Constraints:

obstacles.length == n + 1
1 <= n <= 5 * 10⁵
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

Solution: DP

Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)

C++

class Solution {

public:

int minSideJumps(vector<int>& obstacles) {

const int n = obstacles.size();

vector<vector<int>> dp(3, vector<int>(n, INT_MAX / 2));

dp[1][0] = 0;

dp[0][0] = dp[2][0] = 1;

for (int i = 1; i < n; ++i) {

for (int k = 0; k < 3; ++k)

if (obstacles[i] != k + 1)

dp[k][i] = dp[k][i - 1];

for (int k = 0; k < 3; ++k)

if (obstacles[i] != k + 1)

dp[k][i] = min({dp[k][i],

dp[(k + 1) % 3][i] + 1,

dp[(k + 2) % 3][i] + 1});

}

return min({dp[0].back(), dp[1].back(), dp[2].back()});

}

};

C++/O(1) Space

class Solution {

public:

int minSideJumps(vector<int>& obstacles) {

const int n = obstacles.size();

vector<int> dp{1, 0, 1};

for (int o : obstacles) {

if (o) dp[o - 1] = 1e9;

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

if (k == o - 1) continue;

dp[k] = min({dp[k],

dp[(k + 1) % 3] + 1,

dp[(k + 2) % 3] + 1});

}

return *min_element(begin(dp), end(dp));

}

};

Huahua's Tech Road

花花酱 LeetCode 1829. Maximum XOR for Each Query

Solution: Prefix XOR

C++

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

Solution: Brute Force

C++

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

Solution: Track Last

C++

花花酱 LeetCode 1825. Finding MK Average

Solution 1: Multiset * 3

C++

花花酱 LeetCode 1824. Minimum Sideway Jumps

Solution: DP

C++

C++/O(1) Space

**Solution 1: Multiset * 3**