Posts tagged as “medium”

花花酱 LeetCode 1781. Sum of Beauty of All Substrings

By zxi on March 6, 2021

The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.

For example, the beauty of "abaacc" is 3 - 1 = 2.

Given a string s, return the sum of beauty of all of its substrings.

Example 1:

Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.

Example 2:

Input: s = "aabcbaa"
Output: 17

Constraints:

1 <= s.length <=500
s consists of only lowercase English letters.

Solution: Treemap

Time complexity: O(n²log26)
Space complexity: O(26)

C++

// Author: Huahua

class Solution {

public:

int beautySum(string_view s) {

const int n = s.size();

int ans = 0;

vector<int> f(26);

map<int, int> m;

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

fill(begin(f), end(f), 0);

m.clear();

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

const int c = ++f[s[j] - 'a'];

++m[c];

if (c > 1) {

auto it = m.find(c - 1);

if (--it->second == 0)

m.erase(it);

}

ans += rbegin(m)->first - begin(m)->first;

}

return ans;

}

};

花花酱 LeetCode 1780. Check if Number is a Sum of Powers of Three

By zxi on March 6, 2021

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3^x.

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3¹ + 3²

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3⁰ + 3² + 3⁴

Example 3:

Input: n = 21
Output: false

Constraints:

1 <= n <= 10⁷

Solution: Greedy + Math

Find the largest 3^x that <= n, subtract that from n and repeat the process.
x should be monotonically decreasing, otherwise we have duplicate terms.
e.g. 12 = 3² + 3¹ true
e.g. 21 = 3² + 3²+ 3¹ false

Time complexity: O(logn?)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkPowersOfThree(int n) {

int last = INT_MAX;

while (n) {

int p = 0;

int cur = 1;

while (cur * 3 <= n) {

cur *= 3;

++p;

}

if (p == last) return false;

last = p;

n -= cur;

}

return true;

}

};

花花酱 LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations

By zxi on February 27, 2021

You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.

In one operation, you can change any integer’s value in any of the arrays to any value between 1 and 6, inclusive.

Return the minimum number of operations required to make the sum of values in nums1 equal to the sum of values in nums2. Return -1 if it is not possible to make the sum of the two arrays equal.

Example 1:

Input: nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2].
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2].
- Change nums1[2] to 2. nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2].

Example 2:

Input: nums1 = [1,1,1,1,1,1,1], nums2 = [6]
Output: -1
Explanation: There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.

Example 3:

Input: nums1 = [6,6], nums2 = [1]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1[0] to 2. nums1 = [2,6], nums2 = [1].
- Change nums1[1] to 2. nums1 = [2,2], nums2 = [1].
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [4].

Constraints:

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

Solution: Greedy

Assuming sum(nums1) < sum(nums2),
sort both arrays
* scan nums1 from left to right, we need to increase the value form the smallest one.
* scan nums2 from right to left, we need to decrease the value from the largest one.
Each time, select the one with the largest delta to change.

e.g. nums1[i] = 2, nums[j] = 4, delta1 = 6 – 2 = 4, delta2 = 4 – 1 = 3, Increase 2 to 6 instead of decreasing 4 to 1.

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums1, vector<int>& nums2) {

const int l1 = nums1.size();

const int l2 = nums2.size();

if (min(l1, l2) * 6 < max(l1, l2)) return -1;

int s1 = accumulate(begin(nums1), end(nums1), 0);

int s2 = accumulate(begin(nums2), end(nums2), 0);

if (s1 > s2) return minOperations(nums2, nums1);

sort(begin(nums1), end(nums1));

sort(begin(nums2), end(nums2));

int ans = 0;

int i = 0;

int j = l2 - 1;

while (s1 != s2) {

const int diff = s2 - s1;

if (j == l2 || (i != l1 && 6 - nums1[i] >= nums2[j] - 1)) {

const int x = min(6, nums1[i] + diff);

s1 += x - nums1[i++];

} else {

const int x = max(1, nums2[j] - diff);

s2 += x - nums2[j--];

}

++ans;

}

return ans;

}

};

花花酱 LeetCode 1774. Closest Dessert Cost

By zxi on February 27, 2021

You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:

There must be exactly one ice cream base.
You can add one or more types of topping or have no toppings at all.
There are at most two of each type of topping.

You are given three inputs:

baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the i^th ice cream base flavor.
toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the i^th topping.
target, an integer representing your target price for dessert.

You want to make a dessert with a total cost as close to target as possible.

Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

Example 1:

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

Example 2:

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3:

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

Example 4:

Input: baseCosts = [10], toppingCosts = [1], target = 1
Output: 10
Explanation: Notice that you don't have to have any toppings, but you must have exactly one base.

Constraints:

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 10⁴
1 <= target <= 10⁴

Solution: DP / Knapsack

Pre-compute the costs of all possible combinations of toppings.

Time complexity: O(sum(toppings) * 2 * (m + n)) ~ O(10^6)
Space complexity: O(sum(toppings)) ~ O(10^5)

C++

// Author: Huahua

class Solution {

public:

int closestCost(vector<int>& bs, vector<int>& ts, int target) {

const int kMax = 2 * accumulate(begin(ts), end(ts), 0);

int min_diff = INT_MAX;

int ans = INT_MAX;

vector<int> dp(kMax + 1);

dp[0] = 1;

for (int t : ts) {

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

if (!dp[i]) continue;

if (i + t <= kMax) dp[i + t] = 1;

if (i + 2 * t <= kMax) dp[i + 2 * t] = 1;

}

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

if (!dp[i]) continue;

for (int b : bs) {

const int diff = abs(b + i - target);

if (diff < min_diff || diff == min_diff && b + i < ans) {

min_diff = diff;

ans = b + i;

}

return ans;

}

};

Solution 2: DFS

Combination

Time complexity: O(3^m * n)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int closestCost(vector<int>& bs, vector<int>& ts, int target) {

const int m = ts.size();

int min_diff = INT_MAX;

int ans = INT_MAX;

function<void(int, int)> dfs = [&](int s, int cur) {

if (s == m) {

for (int b : bs) {

const int total = b + cur;

const int diff = abs(total - target);

if (diff < min_diff

|| diff == min_diff && total < ans) {

min_diff = diff;

ans = total;

}

return;

}

for (int i = s; i < m; ++i) {

dfs(i + 1, cur);

dfs(i + 1, cur + ts[i]);

dfs(i + 1, cur + ts[i] * 2);

}

};

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1770. Maximum Score from Performing Multiplication Operations

By zxi on February 21, 2021

You are given two integer arrays nums and multipliersof size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (1-indexed), you will:

Choose one integer x from either the start or the end of the array nums.
Add multipliers[i] * x to your score.
Remove x from the array nums.

Return the maximum score after performing m operations.

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

Constraints:

n == nums.length
m == multipliers.length
1 <= m <= 10³
m <= n <= 10⁵
-1000 <= nums[i], multipliers[i] <= 1000

Solution: DP

dp(i, j) := max score we can get with nums[i~j] left.

k = n – (j – i + 1)
dp(i, j) = max(dp(i + 1, j) + nums[i] * multipliers[k], dp(i, j-1) + nums[j] * multipliers[k])

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

C++/Top-Down

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

vector<vector<int>> cache(m, vector<int>(m, INT_MIN));

function<int(int, int)> dp = [&](int i, int j) {

const int k = n - (j - i + 1);

if (k == m) return 0;

int& ans = cache[i][k];

if (ans != INT_MIN) return ans;

return ans = max(dp(i + 1, j) + nums[i] * multipliers[k],

dp(i, j - 1) + nums[j] * multipliers[k]);

};

return dp(0, n - 1);

}

};

C++/Bottom-UP

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

// dp[i][j] := max score of using first i elements and last j elements

vector<vector<int>> dp(m + 1, vector<int>(m + 1));

for (int k = 1; k <= m; ++k)

for (int i = 0, j = k - i; i <= k; ++i, --j)

dp[i][j] = max((i ? dp[i - 1][j] + nums[i - 1] * multipliers[k - 1] : INT_MIN),

(j ? dp[i][j - 1] + nums[n - j] * multipliers[k - 1] : INT_MIN));

int ans = INT_MIN;

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

ans = max(ans, dp[i][m - i]);

return ans;

}

};