Huahua's Tech Road

花花酱 LeetCode 3028. Ant on the Boundary

By zxi on February 5, 2024

An ant is on a boundary. It sometimes goes left and sometimes right.

You are given an array of non-zero integers nums. The ant starts reading nums from the first element of it to its end. At each step, it moves according to the value of the current element:

If nums[i] < 0, it moves left by -nums[i] units.
If nums[i] > 0, it moves right by nums[i] units.

Return the number of times the ant returns to the boundary.

Notes:

There is an infinite space on both sides of the boundary.
We check whether the ant is on the boundary only after it has moved |nums[i]| units. In other words, if the ant crosses the boundary during its movement, it does not count.

Example 1:

Input: nums = [2,3,-5]
Output: 1
Explanation: After the first step, the ant is 2 steps to the right of the boundary.
After the second step, the ant is 5 steps to the right of the boundary.
After the third step, the ant is on the boundary.
So the answer is 1.

Example 2:

Input: nums = [3,2,-3,-4]
Output: 0
Explanation: After the first step, the ant is 3 steps to the right of the boundary.
After the second step, the ant is 5 steps to the right of the boundary.
After the third step, the ant is 2 steps to the right of the boundary.
After the fourth step, the ant is 2 steps to the left of the boundary.
The ant never returned to the boundary, so the answer is 0.

Constraints:

1 <= nums.length <= 100
-10 <= nums[i] <= 10
nums[i] != 0

Solution: Simulation

Simulate the position of the ant by summing up the numbers. If the position is zero (at boundary), increase the answer by 1.

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

C++

class Solution {

public:

int returnToBoundaryCount(vector<int>& nums) {

int ans = 0;

int pos = 0;

for (int x : nums)

ans += !(pos += x);

return ans;

}

};

花花酱 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;

}

};