Huahua’s Tech Road

花花酱 LeetCode 1686. Stone Game VI

By zxi on December 12, 2020

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player’s turn, they can remove a stone from the pile and receive points based on the stone’s value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the i^th stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally.

Determine the result of the game, and:

If Alice wins, return 1.
If Bob wins, return -1.
If the game results in a draw, return 0.

Example 1:

Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation:
If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.
Bob can only choose stone 0, and will only receive 2 points.
Alice wins.

Example 2:

Input: aliceValues = [1,2], bobValues = [3,1]
Output: 0
Explanation:
If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.
Draw.

Example 3:

Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1
Explanation:
Regardless of how Alice plays, Bob will be able to have more points than Alice.
For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.
Bob wins.

Constraints:

n == aliceValues.length == bobValues.length
1 <= n <= 10⁵
1 <= aliceValues[i], bobValues[i] <= 100

Solution: Greedy

Sort by the sum of stone values.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = A.size();

vector<pair<int, int>> s(n);

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

s.emplace_back(A[i] + B[i], i);

sort(rbegin(s), rend(s));

int ans = 0;

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

int idx = s[i].second;

ans += (i & 1 ? B[idx] : A[idx]) * (i & 1 ? -1 : 1);

}

return ans < 0 ? -1 : (ans > 0);

}

};

花花酱 LeetCode 1685. Sum of Absolute Differences in a Sorted Array

By zxi on December 12, 2020

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= nums[i + 1] <= 10⁴

Solution: Prefix Sum

Let s[i] denote sum(num[i] – num[j]) 0 <= j <= i
s[i] = s[i – 1] + (num[i] – num[i – 1]) * i
Let l[i] denote sum(nums[j] – nums[i]) i <= j < n
l[i] = l[i + 1] + (nums[i + 1] – num[i]) * (n – i – 1)
ans[i] = s[i] + l[i]

e.g. 1, 3, 7, 9
s[0] = 0
s[1] = 0 + (3 – 1) * 1 = 2
s[2] = 2 + (7 – 3) * 2 = 10
s[3] = 10 + (9 – 7) * 3 = 16
l[3] = 0
l[2] = 0 + (9 – 7) * 1 = 2
l[1] = 2 + (7 – 3) * 2 = 10
l[0] = 10 + (3 – 1) * 3 = 16

ans = [16, 12, 12, 16]

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> ans(n);

for (int i = 1, sum = 0; i < n; ++i)

ans[i] += (sum += (nums[i] - nums[i - 1]) * i);

for (int i = n - 2, sum = 0; i >= 0; --i)

ans[i] += (sum += (nums[i + 1] - nums[i]) * (n - i - 1));

return ans;

}

};

花花酱 LeetCode 1684. Count the Number of Consistent Strings

By zxi on December 12, 2020

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

1 <= words.length <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution: Hashtable

Time complexity: O(sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countConsistentStrings(string allowed, vector<string>& words) {

vector<int> m(26);

for (char c : allowed) m[c - 'a'] = 1;

int ans = 0;

for (const string& w : words)

ans += all_of(begin(w), end(w), [&m](char c) { return m[c - 'a']; });

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

return sum(all(c in allowed for c in w) for w in words)

花花酱 LeetCode 1681. Minimum Incompatibility

By zxi on December 6, 2020

You are given an integer array nums and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset’s incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.

Constraints:

1 <= k <= nums.length <= 16
nums.length is divisible by k
1 <= nums[i] <= nums.length

Solution: TSP

dp[s][i] := min cost to distribute a set of numbers represented as a binary mask s, the last number in the set is the i-th number.

Init:
1.dp[*][*] = inf
2. dp[1 <<i][i] = 0, cost of selecting a single number is zero.

Transition:
1. dp[s | (1 << j)][j] = dp[s][i] if s % (n / k) == 0, we start a new group, no extra cost.
2. dp[s | (1 << j)][j] = dp[s][i] + nums[j] – nums[i] if nums[j] > nums[i]. In the same group, we require the selected numbers are monotonically increasing. Each cost is nums[j] – nums[i].
e.g. 1, 3, 7, 20, cost is (3 – 1) + (7 – 3) + (20 – 7) = 20 – 1 = 19.

Ans: min(dp[(1 << n) – 1])

Time complexity: O(2^n * n^2)
Space complexity: O(2^n * n)

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

const int c = n / k;

int dp[1 << 16][16];

memset(dp, 0x7f, sizeof(dp));

for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;

for (int s = 0; s < 1 << n; ++s)

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

if ((s & (1 << i)) == 0) continue;

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

if ((s & (1 << j))) continue;

const int t = s | (1 << j);

if (__builtin_popcount(s) % c == 0) {

dp[t][j] = min(dp[t][j], dp[s][i]);

} else if (nums[j] > nums[i]) {

dp[t][j] = min(dp[t][j],

dp[s][i] + nums[j] - nums[i]);

}

int ans = *min_element(begin(dp[(1 << n) - 1]),

end(dp[(1 << n) - 1]));

return ans > 1e9 ? - 1 : ans;

}

};

花花酱 LeetCode 1680. Concatenation of Consecutive Binary Numbers

By zxi on December 6, 2020

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10⁹+ 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10⁹ + 7, the result is 505379714.

Constraints:

1 <= n <= 10⁵

Solution: Bit Operation

f(n) = (f(n – 1) << length(n)) | n

length(n) increase by 1 whenever n is power of 2.
n = 1, YES, len = 1
n = 2, YES, len = 2
n = 3, NO, len = 2
n = 4, YES, len = 3
n = 5, NO, len = 3
n = 6, NO, len = 3
n = 7, NO, len = 3
n = 8, YES, len = 4
…

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

C++

// Author: Huahua

class Solution {

public:

int concatenatedBinary(int n) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

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

if ((i & (i - 1)) == 0) ++len;

ans = ((ans << len) % kMod + i) % kMod;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1686. Stone Game VI

Solution: Greedy

C++

花花酱 LeetCode 1685. Sum of Absolute Differences in a Sorted Array

Solution: Prefix Sum

C++

花花酱 LeetCode 1684. Count the Number of Consistent Strings

Solution: Hashtable

C++

Python3

花花酱 LeetCode 1681. Minimum Incompatibility

Solution: TSP

C++

花花酱 LeetCode 1680. Concatenation of Consecutive Binary Numbers

Solution: Bit Operation

C++