Huahua's Tech Road

花花酱 LeetCode 1466. Reorder Routes to Make All Paths Lead to the City Zero

By zxi on May 31, 2020

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It’s guaranteed that each city can reach the city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i][0], connections[i][1] <= n-1
connections[i][0] != connections[i][1]

Solution: BFS

Augment the graph
g[u][v] = 1, g[v][u] = 0, u->v is an edge in the original graph.

BFS from 0, sum up all the edge costs to visit all the nodes.

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

C++

// Author: Huahua

class Solution {

public:

int minReorder(int n, vector<vector<int>>& connections) {

vector<vector<pair<int, int>>> g(n); // u -> {v, cost}

for (const auto& e : connections) {

g[e[0]].emplace_back(e[1], 1); // u -> v, needs flip

g[e[1]].emplace_back(e[0], 0); // v -> u, no cost

}

int ans = 0;

queue<int> q{{0}};

vector<int> seen(n);

while (!q.empty()) {

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

seen[cur] = 1;

for (const auto& [nxt, cost] : g[cur]) {

if (seen[nxt]) continue;

ans += cost;

q.push(nxt);

}

return ans;

}

};

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

By zxi on May 31, 2020

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Solution: Geometry

Find the max gap between vertical cuts mx and max gap between horizontal cuts my. ans = mx * my

Time complexity: O(nlogn)
Space complexity: O(1) if sort in place otherweise O(n)

C++

// Author: Huahua

class Solution {

public:

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {

constexpr int kMod = 1e9 + 7;

sort(begin(verticalCuts), end(verticalCuts));

sort(begin(horizontalCuts), end(horizontalCuts));

int mx = max(verticalCuts[0], w - verticalCuts.back());

int my = max(horizontalCuts[0], h - horizontalCuts.back());

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

mx = max(mx, verticalCuts[i] - verticalCuts[i - 1]);

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

my = max(my, horizontalCuts[i] - horizontalCuts[i - 1]);

return static_cast<long>(mx) * my % kMod;

}

};

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

By zxi on May 31, 2020

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution 1: Sort

We want to find the largest and second largest elements.

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

return (nums[0] - 1) * (nums[1] - 1);

}

};

Solution 2: Without sorting

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int m1 = 0;

int m2 = 0;

for (int n : nums) {

if (n > m1) {

m2 = m1;

m1 = n;

} else if (n > m2) {

m2 = n;

}

return (m1 - 1) * (m2 - 1);

}

};

花花酱 LeetCode 1463. Cherry Pickup II

By zxi on May 30, 2020

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Solution: DP

dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)
dp[y][x1][x2] = max(dp[y+1][x1 + dx1][x2 + dx2]) -1 <= dx1, dx2 <= 1

Time complexity: O(c^2*r)
Space complexity: O(c^2*r)

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1)));

function<int(int, int, int)> dp = [&](int y, int x1, int x2) {

if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0;

int& ans = cache[y][x1][x2];

if (ans != -1) return ans;

const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2));

return ans;

};

return dp(0, 0, c - 1);

}

};

Bottom-up

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> dp(r + 2,

vector<vector<int>>(c + 2, vector<int>(c + 2)));

for (int y = r; y >= 1; --y)

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

int& ans = dp[y][x1][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]);

}

return dp[1][1][c];

}

};

O(c^2) Space

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<int>> dp(c + 2, vector<int>(c + 2));

for (int y = r; y >= 1; --y) {

vector<vector<int>> tmp(c + 2, vector<int>(c + 2));

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]);

}

dp.swap(tmp);

}

return dp[1][c];

}

};

花花酱 LeetCode 1462. Course Schedule IV

By zxi on May 30, 2020

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.

Example 3:

Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

Constraints:

2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
The prerequisites graph has no cycles.
The prerequisites graph has no repeated edges.
1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

Solution: Floyd-Warshall Algorithm (All pairs shortest paths)

Time complexity: O(n^3 + q)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<bool> checkIfPrerequisite(int n,

vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {

vector<vector<int>> g(n, vector<int>(n));

for (const auto& p : prerequisites)

g[p[0]][p[1]] = 1;

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

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

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

g[i][j] |= g[i][k] & g[k][j];

vector<bool> ans;

for (const auto& q : queries)

ans.push_back(g[q[0]][q[1]]);

return ans;

}

};