Huahua's Tech Road

花花酱 LeetCode 3005. Count Elements With Maximum Frequency

By zxi on January 15, 2024

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Hashtable

Use a hashtable to store the frequency of each element, and compare it with a running maximum frequency. Reset answer if current frequency is greater than maximum frequency. Increment the answer if current frequency is equal to the maximum frequency.

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

C++

// Author: Huahua

class Solution {

public:

int maxFrequencyElements(vector<int>& nums) {

unordered_map<int, int> m;

int freq = 0;

int ans = 0;

for (int x : nums) {

if (++m[x] > freq)

freq = m[x], ans = 0;

if (m[x] == freq)

ans += m[x];

}

return ans;

}

};

花花酱 LeetCode 2976. Minimum Cost to Convert String I

By zxi on January 8, 2024

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.

Example 3:

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.

Constraints:

1 <= source.length == target.length <= 10⁵
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 10⁶
original[i] != changed[i]

Solution: All pairs shortest path

Compute the shortest path (min cost) for any given letter pairs.

Time complexity: O(26^3 + m + n)
Space complexity: O(26^2)

C++

class Solution {

public:

long long minimumCost(string s, string t, vector<char>& o, vector<char>& c, vector<int>& cost) {

const int n = c.size();

vector<vector<int>> d(26, vector<int>(26, 1e9));

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

d[i][i] = 0;

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

d[o[i] - 'a'][c[i] - 'a'] = min(d[o[i] - 'a'][c[i] - 'a'], cost[i]);

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

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

for (int j = 0; j < 26; ++j)

if (d[i][k] + d[k][j] < d[i][j])

d[i][j] = d[i][k] + d[k][j];

long ans = 0;

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

if (d[s[i] - 'a'][t[i] - 'a'] >= 1e9) return -1;

ans += d[s[i] - 'a'][t[i] - 'a'];

}

return ans;

}

};

花花酱 LeetCode 2974. Minimum Number Game

By zxi on January 8, 2024

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice and Bob will do one move. The rules of the game are as follows:

Every round, first Alice will remove the minimum element from nums, and then Bob does the same.
Now, first Bob will append the removed element in the array arr, and then Alice does the same.
The game continues until nums becomes empty.

Return the resulting array arr.

Example 1:

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

Example 2:

Input: nums = [2,5]
Output: [5,2]
Explanation: In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0

Solution: Sort and Swap

Sort the array first and then swap the adjacent elements.

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

C++

class Solution {

public:

vector<int> numberGame(vector<int>& nums) {

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

for (int i = 0; i < nums.size(); i += 2)

swap(nums[i], nums[i + 1]);

return nums;

}

};

花花酱 LeetCode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

By zxi on October 29, 2023

You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0‘s in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0's in the following way:
- Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
- Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Solution: A few cases

Calculate the sum of number of zeros of each array as (s1, z1), (s2, z2). There are a few cases:

z1 == z2 == 0, there is no way to change, just check s1 == s2.
z1 == 0, z1 != 0 or z2 == 0, z1 != 0. Need to at least increase the sum by number of zeros, check s1 + z1 <= s2 / s2 + z2 <= s1
z1 != 0, z2 != 0, the min sum is max(s1 + z1, s2 + z2)

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

C++

// Author: Huahua

class Solution {

public:

long long minSum(vector<int>& nums1, vector<int>& nums2) {

auto getSumAndZeros = [](const vector<int>& nums) {

long long sum = 0;

long long zeros = 0;

for (int x : nums) {

sum += x;

zeros += x == 0;

}

return pair{sum, zeros};

};

auto [s1, z1] = getSumAndZeros(nums1);

auto [s2, z2] = getSumAndZeros(nums2);

if (z1 == 0 && z2 == 0) {

return s1 == s2 ? s1 : -1;

} else if (z1 == 0) {

return s2 + z2 <= s1 ? s1 : -1;

} else if (z2 == 0) {

return s1 + z1 <= s2 ? s2 : -1;

} else {

return max(s1 + z1, s2 + z2);

}

return -1;

}

};

花花酱 LeetCode 2917. Find the K-or of an Array

By zxi on October 29, 2023

You are given a 0-indexed integer array nums, and an integer k.

The K-or of nums is a non-negative integer that satisfies the following:

The i^th bit is set in the K-or if and only if there are at least k elements of nums in which bit i is set.

Return the K-or of nums.

Note that a bit i is set in x if (2ⁱ AND x) == 2ⁱ, where AND is the bitwise AND operator.

Example 1:

Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation: Bit 0 is set at nums[0], nums[2], nums[4], and nums[5].
Bit 1 is set at nums[0], and nums[5].
Bit 2 is set at nums[0], nums[1], and nums[5].
Bit 3 is set at nums[1], nums[2], nums[3], nums[4], and nums[5].
Only bits 0 and 3 are set in at least k elements of the array, and bits i >= 4 are not set in any of the array's elements. Hence, the answer is 2^0 + 2^3 = 9.

Example 2:

Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: Since k == 6 == nums.length, the 6-or of the array is equal to the bitwise AND of all its elements. Hence, the answer is 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0.

Example 3:

Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.

Constraints:

1 <= nums.length <= 50
0 <= nums[i] < 2³¹
1 <= k <= nums.length

Solution: Bit Operation

Enumerate every bit and enumerate every number.

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

C++

// Author: Huahua

class Solution {

public:

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

int ans = 0;

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

int count = 0;

for (int x : nums)

if (x >> i & 1) ++count;

if (count >= k) ans |= 1 << i;

}

return ans;

}

};