花花酱 LeetCode 885. Boats to Save People

By zxi on August 4, 2018

Problem

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Solution: Greedy + Two Pointers

Time complexity: O(nlogn)

Space complexity: O(1)

Put one heaviest guy and put the lightest guy if not full.

// Author: Huahua

// Running time: 80 ms

class Solution {

public:

int numRescueBoats(vector<int>& people, int limit) {

sort(people.rbegin(), people.rend());

int i = 0;

int j = people.size() - 1;

int ans = 0;

while (i <= j) {

++ans;

if (i == j) break;

if (people[i++] + people[j] <= limit) --j;

}

return ans;

}

};

花花酱 LeetCode 887. Projection Area of 3D Shapes

By zxi on August 4, 2018

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane.

Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: [[2]]
Output: 5

Example 2:

Input: [[1,2],[3,4]]
Output: 17
Explanation: 
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

Example 3:

Input: [[1,0],[0,2]]
Output: 8

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 14

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 21

Note:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50

Solution: Brute Force

Sum of max heights for each cols / rows + # of non-zero-height bars.

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time : 4 ms

class Solution {

public:

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

int n = grid.size();

int m = grid[0].size();

int ans = 0;

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

int h = 0;

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

h = max(h, grid[i][j]);

if (grid[i][j] != 0) ++ans;

}

ans += h;

}

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

int h = 0;

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

h = max(h, grid[i][j]);

ans += h;

}

return ans;

}

};

花花酱 LeetCode 502. IPO

By zxi on August 4, 2018

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit P_i and a minimum capital of C_i is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
             After finishing it you will obtain profit 1 and your capital becomes 1.
             With capital 1, you can either start the project indexed 1 or the project indexed 2.
             Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
             Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Note:

You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.

Solution: Greedy

For each round, find the most profitable job whose capital requirement <= W.

Finish that job and increase W.

Brute force (TLE)

Time complexity: O(kn)

Space complexity: O(1)

C++

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

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

int best_j = -1;

int best_profit = 0;

for (int j = 0; j < Profits.size(); ++j) {

if (Capital[j] <= W && Profits[j] > best_profit) {

best_j = j;

best_profit = Profits[j];

}

if (best_profit == 0) break;

W += Profits[best_j];

Profits[best_j] = INT_MIN; // Used.

}

return W;

}

};

Use priority queue and multiset to track doable and undoable projects at given W.

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 28 ms (beats 96.4%)

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

priority_queue<int> doable; // sorted by profit high to low.

multiset<pair<int, int>> undoable; // {capital, profit}

for (int i = 0; i < Profits.size(); ++i) {

if (Profits[i] <= 0) continue;

if (Capital[i] <= W)

doable.push(Profits[i]);

else

undoable.emplace(Capital[i], Profits[i]);

}

auto it = undoable.cbegin();

while (!doable.empty() && k--) {

W += doable.top(); doable.pop();

while (it != undoable.cend() && it->first <= W)

doable.push(it++->second);

}

return W;

}

};

Or use an array and sort by capital

// Author: Huahua

// Running time: 28 ms (beats 96.4%)

class Solution {

public:

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {

priority_queue<int> doable; // sorted by profit high to low.

vector<pair<int, int>> undoable; // {capital, profit}

for (int i = 0; i < Profits.size(); ++i) {

if (Profits[i] <= 0) continue;

if (Capital[i] <= W)

doable.push(Profits[i]);

else

undoable.emplace_back(Capital[i], Profits[i]);

}

sort(begin(undoable), end(undoable));

auto it = undoable.cbegin();

while (!doable.empty() && k--) {

W += doable.top(); doable.pop();

while (it != undoable.cend() && it->first <= W)

doable.push(it++->second);

}

return W;

}

};

花花酱 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 two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:
Input: N = 50
Output: 0.625
Explanation: 
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.

Solution 1: Recursion with Memorization

Time complexity: O(N^2) N ~ 5000 / 25 = 200

Space complexity: O(N^2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

double soupServings(int N) {

if (N >= 5000) return 1.0;

return prob(N, N);

}

private:

unordered_map<int, unordered_map<int, double>> m_;

double prob(int A, int B) {

static int ops[][2] = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};

if (A <= 0 && B <= 0) return 0.5;

if (A <= 0) return 1.0;

if (B <= 0) return 0.0;

if (m_.count(A) && m_[A].count(B)) return m_[A][B];

m_[A][B] = 0.0;

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

m_[A][B] += 0.25 * prob(A - ops[i][0], B - ops[i][1]);

return m_[A][B];

}

};

花花酱 LeetCode 885. Boats to Save People

Problem

Solution: Greedy + Two Pointers

花花酱 LeetCode 887. Projection Area of 3D Shapes

Problem

Solution: Brute Force

花花酱 LeetCode 502. IPO

Problem

Solution: Greedy

花花酱 LeetCode 546. Remove Boxes

Problem

Solution: Recursion + Memorization

Related Problems

花花酱 LeetCode 808. Soup Servings

Problem

Solution 1: Recursion with Memorization

Huahua's Tech Road

花花酱 LeetCode 885. Boats to Save People

Problem

Solution: Greedy + Two Pointers

花花酱 LeetCode 887. Projection Area of 3D Shapes

Problem

Solution: Brute Force

花花酱 LeetCode 502. IPO

Problem

Solution: Greedy

花花酱 LeetCode 546. Remove Boxes

Problem

Solution: Recursion + Memorization

Related Problems

花花酱 LeetCode 808. Soup Servings

Problem

Solution 1: Recursion with Memorization