Posts tagged as “hard”

花花酱 LeetCode 1377. Frog Position After T Seconds

By zxi on March 8, 2020

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [from_i, to_i] means that exists an edge connecting directly the vertices from_i and to_i.

Return the probability that after t seconds the frog is on the vertex target.

Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666 
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.

Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.

Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666

Constraints:

1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t <= 50
1 <= target <= n
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: BFS

key: if a node has children, the fog jumps to to children so the probability at current node will become 0.

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

C++

// Author: Huahua

class Solution {

public:

double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {

vector<double> p(n + 1);

p[1] = 1.0;

vector<vector<int>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n + 1);

seen[1] = 1;

queue<int> q{{1}};

while (t--) {

int size = q.size();

while (size--) {

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

int children = 0;

for (int nxt : g[cur])

if (!seen[nxt]) ++children;

for (int nxt : g[cur])

if (!seen[nxt]++) {

q.push(nxt);

p[nxt] += p[cur] / children;

}

// key: fog jumps this node has children

if (children > 0) p[cur] = 0.0;

}

return p[target];

}

};

python3

class Solution:

def frogPosition(self, n: int, edges: List[List[int]],

t: int, target: int) -> float:

p = [0] + [1] + [0] * (n - 1)

seen = [False] + [True] + [False] * (n - 1)

q = [1]

g = [[] for _ in range(n + 1)]

for i, j in edges:

g[i].append(j)

g[j].append(i)

for _ in range(t):

q2 = []

for cur in q:

children = sum([not seen[nxt] for nxt in g[cur]])

for nxt in g[cur]:

if seen[nxt]: continue

seen[nxt] = True

q2.append(nxt)

p[nxt] = p[cur] / children

if children > 0: p[cur] = 0

q = q2

return p[target]

花花酱 LeetCode 1373. Maximum Sum BST in Binary Tree

By zxi on March 8, 2020

Given a binary tree root, the task is to return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2:

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

Example 4:

Input: root = [2,1,3]
Output: 6

Example 5:

Input: root = [5,4,8,3,null,6,3]
Output: 7

Constraints:

Each tree has at most 40000 nodes..
Each node’s value is between [-4 * 10^4 , 4 * 10^4].

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int maxSumBST(TreeNode* root) {

int ans = 0;

dfs(root, &ans);

return ans;

}

private:

// returns {lo, hi, sum, valid_bst}

tuple<int, int, int, bool> dfs(TreeNode* root, int* ans) {

if (!root) return {INT_MAX, INT_MIN, 0, true};

auto [ll, lh, ls, lv] = dfs(root->left, ans);

auto [rl, rh, rs, rv] = dfs(root->right, ans);

bool valid = lv && rv && root->val > lh && root->val < rl;

int sum = valid ? ls + rs + root->val : -1;

*ans = max(*ans, sum);

return {min(ll, root->val), max(rh, root->val), sum, valid};

}

};

Python3

# Author: Huahua

class Solution:

def maxSumBST(self, root: TreeNode) -> int:

# returns {lo, hi, sum, valid}

def dfs(node):

if not node: return (1e9, -1e9, 0, True)

ll, lh, ls, lv = dfs(node.left)

rl, rh, rs, rv = dfs(node.right)

v = lv and rv and node.val > lh and node.val < rl

s = ls + rs + node.val if v else -1

self.ans = max(self.ans, s)

return (min(ll, node.val), max(rh, node.val), s, v)

self.ans = 0

dfs(root)

return self.ans

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

By zxi on February 29, 2020

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

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

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

Input: grid = [[4]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100

Solution 1: Lazy BFS (fake DP)

dp[i][j] := min steps to reach (i, j)

Time complexity: O((m+n)*m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

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

int m = grid.size();

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

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

auto solve = [&](int x, int y) {

int& v = dp[y][x];

if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1));

if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3));

if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2));

if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4));

};

// At most m + n steps to propagate the results to (m - 1, n -1).

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

for (int y = 0; y < m; ++y)

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

solve(x, y);

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

solve(x, y);

}

return dp[m - 1][n - 1];

}

};

C++

// Author: Huahua, 88 ms / 22.9 MB

class Solution {

public:

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

const int m = grid.size();

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

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

while (true) {

auto prev(dp);

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

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

if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3));

if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1));

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4));

if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2));

}

if (prev == dp) break; // optimal solution obtained.

}

return dp[m - 1][n - 1];

}

};

Solution 2: 0-1 BFS

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

C++

// Author: Huahua

class Solution {

public:

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

const int m = grid.size();

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

deque<pair<int, int>> q{{0, 0}};

vector<char> seen(m * n);

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

while (!q.empty()) {

auto [p, cost] = q.front(); q.pop_front();

int x = p % n, y = p / n;

if (x == n - 1 && y == m - 1) return cost;

if (seen[p]++) continue;

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

int tx = x + dirs[i][0], ty = y + dirs[i][1];

int tp = ty * n + tx;

if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue;

if (grid[y][x] == i + 1)

q.emplace_front(tp, cost);

else

q.emplace_back(tp, cost + 1);

}

return -1;

}

};

花花酱 LeetCode 1363. Largest Multiple of Three

By zxi on February 23, 2020

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Solution: Greedy + Math + Counting sort

Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0

Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output

C++

// Author: Huahua

class Solution {

public:

string largestMultipleOfThree(vector<int>& digits) {

vector<int> c(10);

for (int d : digits) ++c[d];

auto getNum = [&](const vector<int>& ds) {

for (int d : ds) --c[d];

string ans;

for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d);

ans.append(ans.empty() ? min(1, c[0]) : c[0], '0');

return ans;

};

const int r = accumulate(begin(digits), end(digits), 0) % 3;

vector<vector<int>> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}};

// Use all digitis.

if (r == 0) return getNum({});

// Remove one among {1, 4, 7}, {2, 5, 8}

for (int d : rs[r]) if (c[d]) return getNum({d});

// Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1)

for (int d1 : rs[3 - r])

for (int d2 : rs[3 - r])

if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2])

return getNum({d1, d2});

return "";

}

};

Python3

# Author: Huahua

class Solution:

def largestMultipleOfThree(self, digits: List[int]) -> str:

c = collections.Counter(digits)

def getNum(ds):

ans = []

for d in ds: c[d] -= 1

for d in range(9, 0, -1): ans += [d] * c[d]

ans += [0] * min(1 if not ans else c[0], c[0])

return ''.join(map(str, ans))

rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]

r = sum(digits) % 3

if r == 0: return getNum([])

for d in rs[r]:

if c[d] > 0: return getNum([d])

for d1, d2 in zip(rs[3 - r], rs[3 - r]):

if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]:

return getNum([d1, d2])

return ""

花花酱 LeetCode 1359. Count All Valid Pickup and Delivery Options

By zxi on February 23, 2020

Given n orders, each order consist in pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

Solution: Combination

Let dp[i] denote the number of valid sequence of i nodes.

For i-1 nodes, the sequence length is 2(i-1).
For the i-th nodes,
If we put Pi at index = 0, then we can put Di at 1, 2, …, 2i – 2 => 2i-1 options.
If we put Pi at index = 1, then we can put Di at 2,3,…, 2i – 2 => 2i – 2 options.
…
If we put Pi at index = 2i-1, then we can put Di at 2i – 1=> 1 option.
There are total (2i – 1 + 1) / 2 * (2i – 1) = i * (2*i – 1) options

dp[i] = dp[i – 1] * i * (2*i – 1)

dp[i] = 2n! / 2^n

C++

// Author: Huahua

class Solution {

public:

int countOrders(int n) {

constexpr int kMod = 1e9 + 7;

long ans = 1;

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

ans = ans * i * (2 * i - 1) % kMod;

return ans;

}

};