Huahua’s Tech Road

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

By zxi on August 7, 2021

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Solution: DP / Permutation to combination

dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums1.size();

vector<int> dp(1 << n, INT_MAX);

dp[0] = 0;

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

int index = __builtin_popcount(s);

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

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

dp[s | (1 << i)] = min(dp[s | (1 << i)],

dp[s] + (nums1[index] ^ nums2[i]));

}

return dp.back();

}

};

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

By zxi on August 6, 2021

You are given an m x n integer matrix grid.

A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Example 1:

Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 20 + 3 + 200 + 5 = 228
- Red: 200 + 2 + 10 + 4 = 216
- Green: 5 + 200 + 4 + 2 = 211

Example 2:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 4 + 2 + 6 + 8 = 20
- Red: 9 (area 0 rhombus in the bottom right corner)
- Green: 8 (area 0 rhombus in the bottom middle)

Example 3:

Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁵

Solution: Brute Force

Just find all Rhombus…

Time complexity: O(mn*min(n,m)²)
Space complexity: O(mn*min(n,m)²)

C++

// Author: Huahua

class Solution {

public:

vector<int> getBiggestThree(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> ans;

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

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

ans.push_back(grid[i][j]);

for (int a = 2; a <= min(m, n); ++a)

for (int cy = a - 1; cy + a <= m; ++cy)

for (int cx = a - 1; cx + a <= n; ++cx) {

int s = grid[cy][cx - a + 1]

+ grid[cy][cx + a - 1]

+ grid[cy + a - 1][cx]

+ grid[cy - a + 1][cx];

for (int i = 1; i < a - 1; ++i)

s += grid[cy - i][cx - a + i + 1]

+ grid[cy - i][cx + a - i - 1]

+ grid[cy + i][cx - a + i + 1]

+ grid[cy + i][cx + a - i - 1];

ans.push_back(s);

}

sort(rbegin(ans), rend(ans));

vector<int> output;

for (int x : ans) {

if (output.empty() || output.back() != x)

output.push_back(x);

if (output.size() == 3) break;

}

return output;

}

};

花花酱 LeetCode 1877. Minimize Maximum Pair Sum in Array

By zxi on August 6, 2021

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

n == nums.length
2 <= n <= 10⁵
n is even.
1 <= nums[i] <= 10⁵

Solution: Greedy

Sort the elements, pair nums[i] with nums[n – i – 1] and find the max pair.

Time complexity: O(nlogn) -> O(n) counting sort.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minPairSum(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

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

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

ans = max(ans, nums[i] + nums[n - i - 1]);

return ans;

}

};

花花酱 LeetCode 1876. Substrings of Size Three with Distinct Characters

By zxi on August 6, 2021

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length three in s.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". 
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.

Solution: Brute Force w/ (Hash)Set

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

C++

class Solution {

public:

int countGoodSubstrings(string s) {

int ans = 0;

for (int i = 0; i + 2 < s.length(); ++i)

ans += set<char>(s.begin() + i, s.begin() + i + 3).size() == 3;

return ans;

}

};

Python3

class Solution:

def countGoodSubstrings(self, s: str) -> int:

return sum(len(set(s[i:i + 3])) == 3 for i in range(len(s) - 2))

花花酱 LeetCode 1872. Stone Game VIII

By zxi on August 5, 2021

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

There are n stones arranged in a row. On each player’s turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones’ values to the player’s score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice’s goal is to maximize the score difference, and Bob’s goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

Constraints:

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

Solution: Prefix Sum + DP

Note: Naive DP (min-max) takes O(n²) which leads to TLE. The key of this problem is that each player takes k stones, but put their sum back as a new stone, so you can assume all the original stones are still there, but opponent has to start from the k+1 th stone.

Let dp[i] denote the max score diff that current player can achieve by taking stones[0~i] (or equivalent)

dp[n-1] = sum(A[0~n-1]) // Alice takes all the stones.
dp[n-2] = sum(A[0~n-2]) – (A[n-1] + sum(A[0~n-2])) = sum(A[0~n-2]) – dp[n-1] // Alice takes n-1 stones, Bob take the last one (A[n-1]) + put-back-stone.
dp[n-3] = sum(A[0~n-3]) – max(dp[n-2], dp[n-1]) // Alice takes n-2 stones, Bob has two options (takes n-1 stones or takes n stones)
…
dp[0] = A[0] – max(dp[n-1], dp[n-1], …, dp[1]) // Alice takes the first stone, Bob has n-1 options.

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

C++

// Author: Huahua

class Solution {

public:

int stoneGameVIII(vector<int>& stones) {

const int n = stones.size();

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

stones[i] += stones[i - 1];

int ans = stones.back(); // take all the stones.

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

ans = max(ans, stones[i] - ans);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

Solution: DP / Permutation to combination

C++

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

Solution: Brute Force

C++

花花酱 LeetCode 1877. Minimize Maximum Pair Sum in Array

Solution: Greedy

C++

花花酱 LeetCode 1876. Substrings of Size Three with Distinct Characters

Solution: Brute Force w/ (Hash)Set

C++

Python3

花花酱 LeetCode 1872. Stone Game VIII

Solution: Prefix Sum + DP

C++