mask Archives - Huahua's Tech Road

花花酱 LeetCode 2657. Find the Prefix Common Array of Two Arrays

By zxi on April 30, 2023

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solution 1: Bitset

Use bitsets to store the numbers seen so far for each array, and use sA & sB to count the common elements.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

bitset<51> sA;

bitset<51> sB;

vector<int> ans;

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

sA.set(A[i]);

sB.set(B[i]);

ans.push_back((sA & sB).count());

}

return ans;

}

};

Solution 2: Counter

Use a counter to track the frequency of each element, when the counter[x] == 2, we found a pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {

vector<int> count(A.size() + 1);

vector<int> ans;

for (int i = 0, s = 0; i < A.size(); ++i) {

if (++count[A[i]] == 2) ++s;

if (++count[B[i]] == 2) ++s;

ans.push_back(s);

}

return ans;

}

};

花花酱 LeetCode 137. Single Number II

By zxi on November 27, 2021

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Solution: Bit by bit

Since every number appears three times, the i-th bit must be a factor of 3, if not, that bit belongs to the single number.

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

C++

// Author: Huahua

class Solution {

public:

int singleNumber(vector<int>& nums) {

int ans = 0;

for (int s = 0; s < 32; ++s) {

int mask = 1 << s;

int sum = 0;

for (int x : nums)

if (x & mask) ++sum;

if (sum % 3) ans |= mask;

}

return ans;

}

};

花花酱 LeetCode 1799. Maximize Score After N Operations

By zxi on March 20, 2021

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the i^th operation (1-indexed), you will:

Choose two elements, x and y.
Receive a score of i * gcd(x, y).
Remove x and y from nums.

Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

Example 1:

Input: nums = [1,2]
Output: 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1

Example 2:

Input: nums = [3,4,6,8]
Output: 11
Explanation: The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

Example 3:

Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

Constraints:

1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 10⁶

Solution: Mask DP

dp(mask, i) := max score of numbers (represented by a binary mask) at the i-th operations.
ans = dp(1, mask)
base case: dp = 0 if mask == 0
Transition: dp(mask, i) = max(dp(new_mask, i + 1) + i * gcd(nums[m], nums[n]))

Time complexity: O(n²*2²ⁿ)
Space complexity: O(2²ⁿ)

C++

// Author: Huahua, 184 ms, 8.3 MB

class Solution {

public:

int maxScore(vector<int>& nums) {

const int l = nums.size();

vector<int> cache(1 << l);

function<int(int)> dp = [&](int mask) {

if (mask == 0) return 0;

int& ans = cache[mask];

if (ans > 0) return ans;

const int k = (l - __builtin_popcount(mask)) / 2 + 1;

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

for (int j = i + 1; j < l; ++j)

if ((mask & (1 << i)) && (mask & (1 << j)))

ans = max(ans, k * gcd(nums[i], nums[j])

+ dp(mask ^ (1 << i) ^ (1 << j)));

return ans;

};

return dp((1 << l) - 1);

}

};

Bottom-Up

C++

// Author: Huahua, 156 ms, 8.3 MB

class Solution {

public:

int maxScore(vector<int>& nums) {

const int l = nums.size();

vector<int> dp(1 << l);

for (int mask = 0; mask < 1 << l; ++mask) {

int c = __builtin_popcount(mask);

if (c & 1) continue; // only do in pairs

int k = c / 2 + 1;

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

for (int j = i + 1; j < l; ++j)

if ((mask & (1 << i)) + (mask & (1 << j)) == 0) {

int new_mask = mask | (1 << i) | (1 << j);

dp[new_mask] = max(dp[new_mask],

k * gcd(nums[i], nums[j]) + dp[mask]);

}

return dp[(1 << l) - 1];

}

};

花花酱 LeetCode 477. Total Hamming Distance

By zxi on December 14, 2017

Problem:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just

showing the four bits relevant in this case). So the answer will be:

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目大意：给你一堆数，让你求所有数对的HammingDistance的总和。

Idea:

Brute force, compute HammingDistance for all pairs. O(n^2) TLE
Count how many ones on i-th bit, assuming k. Distance += k * (n – k). O(n)

Solution:

C++ / O(n)

// Author: Huahua

// Runtime: 59 ms

class Solution {

public:

int totalHammingDistance(vector<int>& nums) {

int ans = 0;

int mask = 1;

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

int count = 0;

for (const int num : nums)

if (num & mask) ++count;

ans += (nums.size() - count) * count;

mask <<= 1;

}

return ans;

}

};

Posts tagged as “mask”

花花酱 LeetCode 2657. Find the Prefix Common Array of Two Arrays

Solution 1: Bitset

C++

Solution 2: Counter

C++

花花酱 LeetCode 137. Single Number II

Solution: Bit by bit

C++

Related Problems

花花酱 LeetCode 1799. Maximize Score After N Operations

Solution: Mask DP

C++

C++

花花酱 LeetCode 477. Total Hamming Distance