Huahua’s Tech Road

花花酱 LeetCode 1694. Reformat Phone Number

By zxi on December 20, 2020

You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.

You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:

2 digits: A single block of length 2.
3 digits: A single block of length 3.
4 digits: Two blocks of length 2 each.

The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.

Return the phone number after formatting.

Example 1:

Input: number = "1-23-45 6"
Output: "123-456"
Explanation: The digits are "123456".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456".
Joining the blocks gives "123-456".

Example 2:

Input: number = "123 4-567"
Output: "123-45-67"
Explanation: The digits are "1234567".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45" and "67".
Joining the blocks gives "123-45-67".

Example 3:

Input: number = "123 4-5678"
Output: "123-456-78"
Explanation: The digits are "12345678".
Step 1: The 1st block is "123".
Step 2: The 2nd block is "456".
Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78".
Joining the blocks gives "123-456-78".

Example 4:

Input: number = "12"
Output: "12"

Example 5:

Input: number = "--17-5 229 35-39475 "
Output: "175-229-353-94-75"

Constraints:

2 <= number.length <= 100
number consists of digits and the characters '-' and ' '.
There are at least two digits in number.

Solution:

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

C++

// Author: Huahua

class Solution {

public:

string reformatNumber(string number) {

string ans;

const int total = count_if(begin(number), end(number),

[](char c) { return isdigit(c); });

int l = 0;

for (char c : number) {

if (!isdigit(c)) continue;

ans += c;

++l;

if ((l % 3 == 0 && total - l >= 4) ||

(total % 3 != 0 && total - l == 2)

|| (total % 3 == 0 && total - l == 3))

ans += "-";

}

return ans;

}

};

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

By zxi on December 13, 2020

Given n cuboids where the dimensions of the i^th cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

n == cuboids.length
1 <= n <= 100
1 <= width_i, length_i, height_i <= 100

Solution: Math/Greedy + DP

Direct DP is very hard, since there is no orders.

We have to find some way to sort the cuboids such that cuboid i can NOT stack on cuboid j if i > j. Then dp[i] = max(dp[j]) + height[i], 0 <= j < i, for each i, find the best base j and stack on top of it.
ans = max(dp)

We can sort the cuboids by their sorted dimensions, and cuboid i can stack stack onto cuboid j if and only if w[i] <= w[j] and l[i] <= l[j] and h[i] <= h[j].

First of all, we need to prove that all heights must come from the largest dimension of each cuboid.

1. If the top of the stack is A1*A2*A3, A3 < max(A1, A2), we can easily swap A3 with max(A1, A2), it’s still stackable but we get larger heights.
e.g. 3x5x4, base is 3×5, height is 4, we can rotate to get base of 3×4 with height of 5.

2. If a middle cuboid A of size A1*A2*A3, assuming A1 >= A2, A1 > A3, on top of A we have another cuboid B of size B1*B2*B3, B1 <= B2 <= B3.
We have A1 >= B1, A2 >= B2, A3 >= B3, by rotating A we have A3*A2*A1
A3 >= B3 >= B1, A2 >= B2, A1 > A3 >= B3, so B can be still on top of A, and we get larger height.

e.g. A: 3x5x4, B: 2x3x4
A -> 3x4x5, B is still stackable.

…

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

C++

// Author: Huahua

class Solution {

public:

int maxHeight(vector<vector<int>>& A) {

A.push_back({0, 0, 0});

const int n = A.size();

for (auto& box : A) sort(begin(box), end(box));

sort(begin(A), end(A));

vector<int> dp(n);

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

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

if (A[i][0] >= A[j][0] && A[i][1] >= A[j][1] && A[i][2] >= A[j][2])

dp[i] = max(dp[i], dp[j] + A[i][2]);

return *max_element(begin(dp), end(dp));

}

};

花花酱 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 1688. Count of Matches in Tournament

By zxi on December 13, 2020

You are given an integer n, the number of teams in a tournament that has strange rules:

If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.

Return the number of matches played in the tournament until a winner is decided.

Example 1:

Input: n = 7
Output: 6
Explanation: Details of the tournament: 
- 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 3 + 2 + 1 = 6.

Example 2:

Input: n = 14
Output: 13
Explanation: Details of the tournament:
- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 7 + 3 + 2 + 1 = 13.

Constraints:

1 <= n <= 200

Solution: Simulation / Recursion

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

C++

// Ver 1

class Solution {

public:

int numberOfMatches(int n) {

int ans = 0;

while (n > 1) {

ans += n / 2 + (n & 1);

n /= 2;

}

return ans;

}

};

// Ver 2

class Solution {

public:

int numberOfMatches(int n) {

return n > 1 ? n / 2 + (n & 1) + numberOfMatches(n / 2) : 0;

}

};

Huahua's Tech Road

花花酱 LeetCode 1694. Reformat Phone Number

Solution:

C++

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

Solution: Math/Greedy + DP

C++

花花酱 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 1688. Count of Matches in Tournament

Solution: Simulation / Recursion

C++