Huahua’s Tech Road

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

}

};

花花酱 LeetCode 1611. Minimum One Bit Operations to Make Integers Zero

By zxi on October 4, 2020

Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0^th) bit in the binary representation of n.
Change the i^th bit in the binary representation of n if the (i-1)^th bit is set to 1 and the (i-2)^th through 0^th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 0
Output: 0

Example 2:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 3:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

Constraints:

0 <= n <= 10⁹

Solution 1: Graycode

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

Ans is the order of n in graycode.

C++

// Author: Huahua

class Solution {

public:

int minimumOneBitOperations(int n) {

int ans = 0;

while (n) {

ans ^= n;

n >>= 1;

}

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 1611. Minimum One Bit Operations to Make Integers Zero

Solution 1: Graycode

C++