Huahua’s Tech Road

花花酱 LeetCode 1619. Mean of Array After Removing Some Elements

By zxi on October 17, 2020

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10^-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778

Example 4:

Input: arr = [9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
Output: 5.27778

Example 5:

Input: arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,7,2,10,7,7,8,2,0,1,1]
Output: 5.29167

Constraints:

20 <= arr.length <= 1000
arr.lengthis a multiple of 20.
0 <= arr[i] <= 10⁵

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

double trimMean(vector<int>& arr) {

sort(begin(arr), end(arr));

const int offset = arr.size() / 20;

const int sum = accumulate(begin(arr) + offset, end(arr) - offset, 0);

return static_cast<double>(sum) / (arr.size() - 2 * offset);

}

};

花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities

By zxi on October 11, 2020

There are n cities numbered from 1 to n. You are given an array edges of size n-1, where edges[i] = [u_i, v_i] represents a bidirectional edge between cities u_i and v_i. There exists a unique path between each pair of cities. In other words, the cities form a tree.

A subtree is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.

For each d from 1 to n-1, find the number of subtrees in which the maximum distance between any two cities in the subtree is equal to d.

Return an array of size n-1 where the d^thelement (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to d.

Notice that the distance between the two cities is the number of edges in the path between them.

Example 1:

Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.

Example 2:

Input: n = 2, edges = [[1,2]]
Output: [1]

Example 3:

Input: n = 3, edges = [[1,2],[2,3]]
Output: [2,1]

Constraints:

2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= u_i, v_i <= n
All pairs (u_i, v_i) are distinct.

Solution1: Brute Force + Diameter of tree

Try all subtrees and find the diameter of that subtree (longest distance between any node)

Time complexity: O(2^n * n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges, int last = -1) {

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

for (const auto& e : edges)

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

vector<int> seen(n, -1), seen2;

queue<int> q;

auto bfs = [&](int start, vector<int>& seen) -> pair<int, int> {

q.push(start);

seen[start] = 1;

int count = 0, dist = -1;

while (!q.empty()) {

int s = q.size();

while (s--) {

last = q.front(); q.pop();

++count;

for (int v : g[last])

if (seen[v] != -1 && !seen[v]++) q.push(v);

}

++dist;

}

return {dist, count};

};

vector<int> ans(n - 1);

for (int s = 0; s < 1 << n; ++s) {

if (__builtin_popcount(s) <= 1) continue;

fill(begin(seen), end(seen), -1);

for (int i = 0; i < n; ++i) if (s & (1 << i)) seen[i] = 0;

seen2 = seen;

const int start = 31 - __builtin_clz(s & (s - 1));

if (bfs(start, seen).second != __builtin_popcount(s)) continue;

++ans[bfs(last, seen2).first - 1];

}

return ans;

}

};

Solution 2: DP on Trees

dp[i][k][d] := # of subtrees rooted at i with tree diameter of d and the distance from i to the farthest node is k.

Time complexity: O(n^5)
Space complexity: O(n^3)

C++

// Author: Huahua, 4ms, 8.8MB

class Solution {

public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {

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

for (const auto& e : edges) {

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

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

}

vector<vector<vector<int>>> dp(n);

vector<int> sizes(n);

function<void(int, int)> dfs = [&](int u, int p) {

if (!dp[u].empty()) return;

dp[u] = vector<vector<int>>(n, vector<int>(n));

dp[u][0][0] = 1;

sizes[u] = 1;

for (int v : g[u]) {

if (v == p) continue;

dfs(v, u);

vector<vector<int>> dpu(dp[u]);

for (int d1 = 0; d1 < sizes[u]; ++d1)

for (int k1 = 0; k1 <= d1; ++k1) {

if (!dp[u][k1][d1]) continue;

for (int d2 = 0; d2 < sizes[v]; ++d2)

for (int k2 = 0; k2 <= d2; ++k2) {

const int d = max({d1, d2, k1 + k2 + 1});

const int k = max(k1, k2 + 1);

dpu[k][d] += dp[u][k1][d1] * dp[v][k2][d2];

}

swap(dpu, dp[u]);

sizes[u] += sizes[v];

}

};

vector<int> ans(n - 1);

dfs(0, -1);

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

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

for (int d = 1; d < n; ++d)

ans[d - 1] += dp[i][k][d];

return ans;

}

};

花花酱 LeetCode 1616. Split Two Strings to Make Palindrome

By zxi on October 10, 2020

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
Then, a_prefix + b_suffix = "" + "y" = "y", which is a palindrome.

Example 2:

Input: a = "abdef", b = "fecab"
Output: true

Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
Then, a_prefix + b_suffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

Input: a = "xbdef", b = "xecab"
Output: false

Constraints:

1 <= a.length, b.length <= 10⁵
a.length == b.length
a and b consist of lowercase English letters

Solution: Greedy

Try to match the prefix of A and suffix of B (or the other way) as much as possible and then check whether the remaining part is a palindrome or not.

e.g. A = “abcxyzzz”, B = “uuuvvcba”
A’s prefix abc matches B’s suffix cba
We just need to check whether “xy” or “vv” is palindrome or not.
The concatenated string “abc|vvcba” is a palindrome, left abc is from A and vvcba is from B.

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

C++

// Author: Huahua

class Solution {

public:

bool checkPalindromeFormation(string a, string b) {

auto isPalindrome = [](const string& s, int i, int j) {

while (i < j && s[i] == s[j]) ++i, --j;

return i >= j;

};

auto check = [&isPalindrome](const string& a, const string& b) {

int i = 0;

int j = a.length() - 1;

while (a[i] == b[j]) ++i, --j;

return isPalindrome(a, i, j) || isPalindrome(b, i, j);

};

return check(a, b) || check(b, a);

}

};

花花酱 LeetCode 1615. Maximal Network Rank

By zxi on October 10, 2020

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.

The network rankof two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= a_i, b_i <= n-1
a_i != b_i
Each pair of cities has at most one road connecting them.

Solution: Counting degrees and all pairs

Counting degrees for each node, if a and b are not connected, ans = degrees(a) + degrees(b), otherwise ans -= 1

Time complexity: O(E + V^2)
Space complexity: O(E)

C++

// Author: Huahua

class Solution {

public:

int maximalNetworkRank(int n, vector<vector<int>>& roads) {

vector<int> degrees(n);

unordered_set<int> connected;

for (const auto& road : roads) {

++degrees[road[0]];

++degrees[road[1]];

connected.insert((road[0] << 16) | road[1]);

connected.insert((road[1] << 16) | road[0]);

}

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

ans = max(ans, degrees[i] + degrees[j]

- (connected.count((i << 16) | j) ? 1 : 0));

return ans;

}

};

花花酱 LeetCode 1614. Maximum Nesting Depth of the Parentheses

By zxi on October 10, 2020

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string "", or a single character not equal to "(" or ")",
It can be written as AB (A concatenated with B), where A and B are VPS‘s, or
It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS‘s
depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS‘s (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS‘s.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3

Example 3:

Input: s = "1+(2*3)/(2-1)"
Output: 1

Example 4:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
It is guaranteed that parentheses expression s is a VPS.

Solution: Stack

We only need to deal with ‘(‘ and ‘)’

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

C++

// Author: Huahua

class Solution {

public:

int maxDepth(string s) {

int ans = 0;

int d = 0;

for (char c : s) {

if (c == '(') ans = max(ans, ++d);

else if (c == ')') --d;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1619. Mean of Array After Removing Some Elements

Solution: Sorting

C++

花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities

Solution1: Brute Force + Diameter of tree

C++

Solution 2: DP on Trees

C++

花花酱 LeetCode 1616. Split Two Strings to Make Palindrome

Solution: Greedy

C++

花花酱 LeetCode 1615. Maximal Network Rank

Solution: Counting degrees and all pairs

C++

花花酱 LeetCode 1614. Maximum Nesting Depth of the Parentheses

Solution: Stack

C++