Posts published in August 2018

花花酱 LeetCode 189. Rotate Array

By zxi on August 6, 2018

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3 
Output: [5,6,7,1,2,3,4]
Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] 
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:[-1,-100,3,99] and k = 2 
Output: [3,99,-1,-100] 
Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution 1: Simulate rotation with three reverses.

If k >= n, rotating k times has the same effect as rotating k % n times.

[1,2,3,4,5,6,7], K = 3

[5,6,7,1,2,3,4]

We can simulate the rotation with three reverses.

reverse the whole array O(n) [7,6,5,4,3,2,1]
reverse the left part 0 ~ k – 1 O(k) [5,6,7,4,3,2,1]
reverse the right part k ~ n – 1 O(n-k) [5,6,7,1,2,3,4]

Time complexity: O(n)

Space complexity: O(1) in-place

C++

class Solution {

public:

void rotate(vector<int>& nums, int k) {

if (nums.empty()) return;

k %= nums.size();

if (k == 0) return;

reverse(begin(nums), end(nums));

reverse(begin(nums), begin(nums) + k);

reverse(begin(nums) + k, end(nums));

}

};

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

}

};