花花酱 LeetCode 97. Interleaving String

By zxi on August 5, 2018

Problem

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Solution: DP

Subproblems : whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huhaua

// Running time: 0 ms

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) {

int l1 = s1.length();

int l2 = s2.length();

int l3 = s3.length();

if (l1 + l2 != l3) return false;

// dp[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

dp[0][0] = true;

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

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

if (i > 0) dp[i][j] |= dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];

if (j > 0) dp[i][j] |= dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];

}

return dp[l1][l2];

}

};

Recursion + Memorization

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) {

m_ = vector<vector<int>>(s1.length() + 1, vector<int>(s2.length() + 1, INT_MIN));

return dp(s1, s1.length(), s2, s2.length(), s3, s3.length());

}

private:

// m_[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]

vector<vector<int>> m_;

bool dp(const string& s1, int l1, const string& s2, int l2, const string& s3, int l3) {

if (l1 + l2 != l3) return false;

if (l1 == 0 && l2 == 0) return true;

if (m_[l1][l2] != INT_MIN) return m_[l1][l2];

if (l1 > 0 & s3[l3 - 1] == s1[l1 - 1] && dp(s1, l1 - 1, s2, l2, s3, l3 - 1)

||l2 > 0 & s3[l3 - 1] == s2[l2 - 1] && dp(s1, l1, s2, l2 - 1, s3, l3 - 1))

m_[l1][l2] = 1;

else

m_[l1][l2] = 0;

return m_[l1][l2];

}

};

花花酱 LeetCode 882. Reachable Nodes In Subdivided Graph

By zxi on August 4, 2018

Problem

Starting with an undirected graph (the “original graph”) with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, ..., x_n) are added to the original graph,

and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.

Example 1:

Input: edge = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3 
Output: 13 
Explanation:  The nodes that are reachable in the final graph after M = 6 moves are indicated below.

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4 
Output: 23

Note:

0 <= edges.length <= 10000
0 <= edges[i][0] < edges[i][1] < N
There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].
The original graph has no parallel edges.
0 <= edges[i][2] <= 10000
0 <= M <= 10^9
1 <= N <= 3000

Solution: Dijkstra Shortest Path

Compute the shortest from 0 to rest of the nodes. Use HP to mark the maximum moves left to reach each node.

HP[u] = a, HP[v] = b, new_nodes[u][v] = c

nodes covered between a<->b = min(c, a + b)

Time complexity: O(ElogE)

Space complexity: O(E)

C++

// Author: Huahua

// Running time: 88 ms

class Solution {

public:

int reachableNodes(vector<vector<int>>& edges, int M, int N) {

unordered_map<int, unordered_map<int, int>> g;

for (const auto& e : edges)

g[e[0]][e[1]] = g[e[1]][e[0]] = e[2];

priority_queue<pair<int, int>> q; // {hp, node}, sort by HP desc

unordered_map<int, int> HP; // node -> max HP left

q.push({M, 0});

while (!q.empty()) {

int hp = q.top().first;

int cur = q.top().second;

q.pop();

if (HP.count(cur)) continue;

HP[cur] = hp;

for (const auto& pair : g[cur]) {

int nxt = pair.first;

int nxt_hp = hp - pair.second - 1;

if (HP.count(nxt) || nxt_hp < 0) continue;

q.push({nxt_hp, nxt});

}

int ans = HP.size(); // Original nodes covered.

for (const auto& e : edges) {

int uv = HP.count(e[0]) ? HP[e[0]] : 0;

int vu = HP.count(e[1]) ? HP[e[1]] : 0;

ans += min(e[2], uv + vu);

}

return ans;

}

};

Optimized Dijkstra (replace hashmap with vector)

// Author: Huahua

// Running time: 56 ms (beats 88%)

class Solution {

public:

int reachableNodes(vector<vector<int>>& edges, int M, int N) {

vector<vector<pair<int, int>>> g(N);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

set<pair<int, int>> q; // {hp, node}, sort by HP asc

vector<int> HP(N, INT_MIN); // node -> HP left

q.insert({M, 0});

int ans = 0;

while (!q.empty()) {

auto last_it = prev(end(q));

int hp = last_it->first;

int cur = last_it->second;

q.erase(last_it);

if (HP[cur] != INT_MIN) continue;

HP[cur] = hp;

++ans;

for (const auto& pair : g[cur]) {

int nxt = pair.first;

int nxt_hp = hp - pair.second - 1;

if (nxt_hp < 0 || HP[nxt] != INT_MIN) continue;

q.insert({nxt_hp, nxt});

}

for (const auto& e : edges) {

const int uv = HP[e[0]] == INT_MIN ? 0 : HP[e[0]];

const int vu = HP[e[1]] == INT_MIN ? 0 : HP[e[1]];

ans += min(e[2], uv + vu);

}

return ans;

}

};

Using SPFA

// Author: Huahua

// Running time: 56 ms (beats 88%)

class Solution {

public:

int reachableNodes(vector<vector<int>>& edges, int M, int N) {

vector<vector<pair<int, int>>> g(N);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

queue<int> q;

vector<int> HP(N, INT_MIN);

vector<bool> in_q(N);

HP[0] = M;

q.push(0);

in_q[0] = true;

// SPFA (Shortest Path Faster Algorithm).

while (!q.empty()) {

int u = q.front(); q.pop();

in_q[u] = false;

for (const auto& pair : g[u]) {

int v = pair.first;

int new_hp = HP[u] - pair.second - 1;

if (new_hp < 0 || new_hp <= HP[v]) continue;

HP[v] = new_hp;

if (in_q[v]) continue;

q.push(v);

in_q[v] = true;

}

int ans = 0;

for (int i = 0; i < N; ++i) ans += HP[i] >= 0;

for (const auto& e : edges) {

const int uv = HP[e[0]] == INT_MIN ? 0 : HP[e[0]];

const int vu = HP[e[1]] == INT_MIN ? 0 : HP[e[1]];

ans += min(e[2], uv + vu);

}

return ans;

}

};

BFS

// Author: Huahua

// Running time: 108 ms

class Solution {

public:

int reachableNodes(vector<vector<int>>& edges, int M, int N) {

unordered_map<int, unordered_map<int, int>> g;

for (const auto& e : edges)

g[e[0]][e[1]] = g[e[1]][e[0]] = e[2];

queue<pair<int, int>> q; // {hp, node}

unordered_map<int, int> HP; // node -> max HP left

q.push({M, 0});

while (!q.empty()) {

int hp = q.front().first;

int cur = q.front().second;

q.pop();

if (HP.count(cur) && HP[cur] > hp) continue;

HP[cur] = hp;

for (const auto& pair : g[cur]) {

int nxt = pair.first;

int nxt_hp = hp - pair.second - 1;

if (nxt_hp < 0 || (HP.count(nxt) && HP[nxt] > nxt_hp)) continue;

q.push({nxt_hp, nxt});

}

int ans = HP.size(); // Original nodes covered.

for (const auto& e : edges) {

int uv = HP.count(e[0]) ? HP[e[0]] : 0;

int vu = HP.count(e[1]) ? HP[e[1]] : 0;

ans += min(e[2], uv + vu);

}

return ans;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 97. Interleaving String

Problem

Solution: DP

花花酱 LeetCode 882. Reachable Nodes In Subdivided Graph

Problem

Solution: Dijkstra Shortest Path

花花酱 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