Posts tagged as “medium”

花花酱 LeetCode 1690. Stone Game VII

By zxi on December 13, 2020

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, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the i^th stone from the left, return the difference in Alice and Bob’s score if they both play optimally.

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

Constraints:

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Solution: MinMax + DP

For a sub game of stones[l~r] game(l, r), we have two choices:
Remove the left one: sum(stones[l + 1 ~ r]) – game(l + 1, r)
Remove the right one: sum(stones[l ~ r – 1]) – game(l, r – 1)
And take the best choice.

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

C++/Top Down

// Author: Huahua

class Solution {

public:

int stoneGameVII(vector<int>& A) {

const int n = A.size();

vector<vector<int>> cache(n, vector<int>(n, INT_MAX));

function<int(int, int, int)> dp = [&](int l, int r, int s) {

if (l >= r) return 0;

if (cache[l][r] == INT_MAX)

cache[l][r] = max(s - A[r] - dp(l, r - 1, s - A[r]),

s - A[l] - dp(l + 1, r, s - A[l]));

return cache[l][r];

};

return dp(0, n - 1, accumulate(begin(A), end(A), 0));

}

};

C++/Bottom-Up

// Author: Huahua

class Solution {

public:

int stoneGameVII(vector<int>& A) {

const int n = A.size();

vector<int> s(n + 1);

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

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int c = 2; c <= n; ++c)

for (int l = 0, r = l + c - 1; r < n; ++l, ++r)

dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],

s[r] - s[l] - dp[l][r - 1]);

return dp[0][n - 1];

}

};

Python3

# Author: Huahua

class Solution:

def stoneGameVII(self, stones: List[int]) -> int:

n = len(stones)

s = [0] * (n + 1)

for i in range(n): s[i + 1] = s[i] + stones[i]

dp = [[0] * n for _ in range(n)]

for c in range(2, n + 1):

for l in range(0, n - c + 1):

r = l + c - 1

dp[l][r] = max(s[r + 1] - s[l + 1] - dp[l + 1][r],

s[r] - s[l] - dp[l][r - 1])

return dp[0][n - 1]

花花酱 LeetCode 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

By zxi on December 13, 2020

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Example 1:

Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32

Example 2:

Input: n = "82734"
Output: 8

Example 3:

Input: n = "27346209830709182346"
Output: 9

Constraints:

1 <= n.length <= 10⁵
n consists of only digits.
n does not contain any leading zeros and represents a positive integer.

Solution: Return the max digit

Proof: For a given string, we find the maximum number m, we create m binary strings.
for each one, check each digit, if it’s greater than 0, we mark 1 at that position and decrease the digit by 1.

e.g. 21534
max is 5, we need five binary strings.
1. 11111: 21534 -> 10423
2. 10111: 10423 -> 00312
3: 00111: 00312 -> 00201
4: 00101: 00201 -> 00100
5: 00100: 00100 -> 00000

We can ignore the leading zeros.

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

C++

// Author: Huahua

class Solution {

public:

int minPartitions(string n) {

return *max_element(begin(n), end(n)) - '0';

}

};

花花酱 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 1286. Iterator for Combination

By zxi on November 30, 2020

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It’s guaranteed that all calls of the function next are valid.

Solution: Bitmask

Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.

mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done

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

C++

class CombinationIterator {

public:

CombinationIterator(string characters, int combinationLength):

chars_(rbegin(characters), rend(characters)),

length_(combinationLength),

mask_((1 << characters.size()) - 1) {}

string next() {

hasNext();

string ans;

for (int i = chars_.size() - 1; i >= 0 ; --i)

if ((mask_ >> i) & 1)

ans.push_back(chars_[i]);

--mask_;

return ans;

}

bool hasNext() {

while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;

return mask_ > 0;

}

private:

int mask_ = 0;

const int length_;

const string chars_;

};

Posts tagged as “medium”

花花酱 LeetCode 1690. Stone Game VII

Solution: MinMax + DP

C++/Top Down

C++/Bottom-Up

Python3

Related Problems

花花酱 LeetCode 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Solution: Return the max digit

C++

花花酱 LeetCode 1686. Stone Game VI

Solution: Greedy

C++

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

Solution: Prefix Sum

C++

花花酱 LeetCode 1286. Iterator for Combination

Solution: Bitmask

C++