Posts tagged as “hard”

花花酱 LeetCode 546. Remove Boxes

By zxi on August 2, 2018

Problem

Given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points.
Find the maximum points you can get.

Example 1:
Input:

1	[1, 3, 2, 2, 2, 3, 4, 3, 1]

Output:

Explanation:

[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

Note: The number of boxes n would not exceed 100.

Solution: Recursion + Memorization

Use dp[l][r][k] to denote the max score of subarray box[l] ~ box[r] with k boxes after box[r] that have the same color as box[r]

box[l], box[l+1], …, box[r], box[r+1], …, box[r+k]

e.g. “CDABACAAAAA”

dp[2][6][4] is the max score of [ABACA] followed by [AAAA]
dp[2][6][3] is the max score of [ABACA] followed by [AAA]

base case: l > r, empty array, return 0.

Transition:
dp[l][r][k] = max(dp[l][r-1][0] + (k + 1)*(k + 1),  # case 1
                  dp[l][i][k+1] + dp[i+1][r-1][0])  # case 2
# "ABACA|AAAA" 
# case 1: dp("ABAC") + score("AAAAA") drop j and the tail.
# case 2: box[i] == box[r], l <= i < r, try all break points
# max({dp("A|AAAAA") + dp("BAC")}, {dp("ABA|AAAAA") + dp("C")})

Time complexity: O(n^4)

Space complexity: O(n^3)

C++

// Author: Huahua

// Running time: 196 ms

class Solution {

public:

int removeBoxes(vector<int>& boxes) {

const int n = boxes.size();

m_ = vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n)));

return dfs(boxes, 0, n - 1, 0);

}

private:

vector<vector<vector<int>>> m_;

int dfs(const vector<int>& boxes, int l, int r, int k) {

if (l > r) return 0;

if (m_[l][r][k] > 0) return m_[l][r][k];

m_[l][r][k] = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);

for (int i = l; i < r; ++i)

if (boxes[i] == boxes[r])

m_[l][r][k] = max(m_[l][r][k], dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));

return m_[l][r][k];

}

};

Optimized

// Author: Huahua

// Running time: 16 ms

int m[100][100][100];

class Solution {

public:

int removeBoxes(vector<int>& boxes) {

memset(m, 0, sizeof(m));

return dfs(boxes, 0, boxes.size() - 1, 0);

}

private:

int dfs(const vector<int>& boxes, int l, int r, int k) {

if (l > r) return 0;

if (m[l][r][k] > 0) return m[l][r][k];

int rr = r;

int kk = k;

while (l < r && boxes[r - 1] == boxes[r]) {--r; ++k;}

m[l][r][k] = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);

for (int i = l; i < r; ++i)

if (boxes[i] == boxes[r])

m[l][r][k] = max(m[l][r][k], dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));

for (int d = 1; d <= r - rr; ++d)

m[l][r + d][k - d] = m[l][r][k];

return m[l][r][k];

}

};

Use a HashTable to replace the 3D DP array since the DP array could be sparse when many consecutive boxes are the same color.

// Author: Huahua

// Running time: 8 ms (beats 100%)

class Solution {

public:

int removeBoxes(vector<int>& boxes) {

len_ = vector<int>(boxes.size());

for (int i = 1; i < boxes.size(); ++i)

if (boxes[i] == boxes[i - 1]) len_[i] = len_[i - 1] + 1;

return dfs(boxes, 0, boxes.size() - 1, 0);

}

private:

unordered_map<int, int> m_;

vector<int> len_;

int dfs(const vector<int>& boxes, int l, int r, int k) {

if (l > r) return 0;

k += len_[r];

r -= len_[r];

int key = (l * 100 + r) * 100 + k;

auto it = m_.find(key);

if (it != m_.end()) return it->second;

int& ans = m_[key];

ans = dfs(boxes, l, r - 1, 0) + (k + 1) * (k + 1);

for (int i = l; i < r; ++i)

if (boxes[i] == boxes[r])

ans = max(ans, dfs(boxes, l, i, k + 1) + dfs(boxes, i + 1, r - 1, 0));

return ans;

}

};

Problem

There are G people in a gang, and a list of various crimes they could commit.

The i-th crime generates a profit[i] and requires group[i] gang members to participate.

If a gang member participates in one crime, that member can’t participate in another crime.

Let’s call a profitable scheme any subset of these crimes that generates at least P profit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen? Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: 
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: 
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Note:

1 <= G <= 100
0 <= P <= 100
1 <= group[i] <= 100
0 <= profit[i] <= 100
1 <= group.length = profit.length <= 100

Solution: DP

Time complexity: O(KPG)

Space complexity: O(KPG)

C++

// Author: Huahua

// Running time: 64 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

const int K = group.size();

// dp[k][i][j]:= # of schemes of making profit i with j people by commiting first k crimes.

vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(P + 1, vector<int>(G + 1, 0)));

dp[0][0][0] = 1;

for (int k = 1; k <= K; ++k) {

const int p = profit[k - 1];

const int g = group[k - 1];

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

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

dp[k][i][j] = (dp[k - 1][i][j] + (j < g ? 0 : dp[k - 1][max(0, i - p)][j - g])) % kMod;

}

return accumulate(begin(dp[K][P]), end(dp[K][P]), 0LL) % kMod;

}

};

Space complexity: O(PG)

v1: Dimension reduction by copying.

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

const int K = group.size();

// dp[i][j]:= # of schemes of making profit i with j people.

vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));

dp[0][0] = 1;

for (int k = 1; k <= K; ++k) {

auto tmp = dp;

const int p = profit[k - 1];

const int g = group[k - 1];

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

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

tmp[i][j] = (tmp[i][j] + (j < g ? 0 : dp[max(0, i - p)][j - g])) % kMod;

dp.swap(tmp);

}

return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;

}

};

v2: Dimension reduction by using rolling array.

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

// dp[i][j]:= # of schemes of making profit i with j people.

vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));

dp[0][0] = 1;

const int K = group.size();

for (int k = 0; k < K; ++k) {

const int p = profit[k];

const int g = group[k];

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

const int ip = min(P, i + p);

for (int j = G - g; j >= 0; --j)

dp[ip][j + g] = (dp[ip][j + g] + dp[i][j]) % kMod;

}

return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;

}

};

花花酱 LeetCode 878. Nth Magical Number

By zxi on July 28, 2018

Problem

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2

Example 2:

Input: N = 4, A = 2, B = 3
Output: 6

Example 3:

Input: N = 5, A = 2, B = 4
Output: 10

Example 4:

Input: N = 3, A = 6, B = 4
Output: 8

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Solution: Math + Binary Search

Let n denote the number of numbers <= X that are divisible by either A or B.

n = X / A + X / B – X / lcm(A, B) = X / A + X / B – X / (A * B / gcd(A, B))

Binary search for the smallest X such that n >= N

Time complexity: O(log(1e9*4e5)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int nthMagicalNumber(int N, int A, int B) {

const int kMod = 1000000007;

long l = 2;

long r = static_cast<long>(1e9 * 4e5);

int d = gcd(A, B);

while (l < r) {

long m = (r - l) / 2 + l;

if (m / A + m / B - m / (A * B / d) < N)

l = m + 1;

else

r = m;

}

return l % kMod;

}

private:

int gcd(int a, int b) {

if (a % b == 0) return b;

return gcd(b, a % b);

}

};

花花酱 LeetCode 135. Candy

By zxi on July 27, 2018

Problem

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Solution: Greedy

First pass: left to right, the right one will have one more candy than the left one if taller.

Second pass: right to left, the left one will be at least one more candy than the right one if taller.

Time Complexity: O(n)

Space Complexity: O(n)

C++

class Solution {

public:

int candy(vector<int>& ratings) {

const int n = ratings.size();

vector<int> ans(n, 1);

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

if (ratings[i] > ratings[i - 1]) ans[i] = ans[i - 1] + 1;

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

if (ratings[i] > ratings[i + 1]) ans[i] = max(ans[i], ans[i + 1] + 1);

return accumulate(begin(ans), end(ans), 0);

}

};

花花酱 LeetCode 115. Distinct Subsequences

By zxi on July 19, 2018

Problem

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:  As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters) 
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:  As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

Solution: DP

Time complexity: O(|s| * |t|)

Space complexity: O(|s| * |t|)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numDistinct(string s, string t) {

int ls = s.length();

int lt = t.length();

vector<vector<int>> dp(lt + 1, vector<int>(ls + 1));

fill(begin(dp[0]), end(dp[0]), 1);

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

for (int j = 1; j <= ls; ++j)

dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);

return dp[lt][ls];

}

};

Posts tagged as “hard”

花花酱 LeetCode 546. Remove Boxes

Problem

Solution: Recursion + Memorization

Related Problems

花花酱 LeetCode 879. Profitable Schemes

Problem

Solution: DP

花花酱 LeetCode 878. Nth Magical Number

Problem

Solution: Math + Binary Search

花花酱 LeetCode 135. Candy

Problem

Solution: Greedy

花花酱 LeetCode 115. Distinct Subsequences

Problem

Solution: DP

Related Problems: