Huahua’s Tech Road

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

By zxi on July 25, 2020

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

Solution: Brute Force

Since n <= 1024, and distance <= 10, we can collect all leaf nodes and try all pairs.

Time complexity: O(|leaves|^2)
Space complexity: O(n)

C++

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

unordered_map<TreeNode*, TreeNode*> parents;

vector<TreeNode*> leaves;

function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) {

if (!c) return;

parents[c] = p;

dfs(c->left, c);

dfs(c->right, c);

if (!c->left && !c->right) leaves.push_back(c);

};

dfs(root, nullptr);

unordered_map<TreeNode*, int> a;

auto isGood = [&](TreeNode* n) -> int {

for (int i = 0; i < distance && n; ++i, n = parents[n])

if (a.count(n) && a[n] + i <= distance) return 1;

return 0;

};

int ans = 0;

for (int i = 0; i < leaves.size(); ++i) {

TreeNode* n1 = leaves[i];

a.clear();

for (int k = 0; k < distance && n1; ++k, n1 = parents[n1])

a[n1] = k;

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

ans += isGood(leaves[j]);

}

return ans;

}

};

Solution 2: Post order traversal

For each node, compute the # of good leaf pair under itself.
1. count the frequency of leaf node at distance 1, 2, …, d for both left and right child.
2. ans += l[i] * r[j] (i + j <= distance) cartesian product
3. increase the distance by 1 for each leaf node when pop
Time complexity: O(n*D^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

int ans = 0;

function<vector<int>(TreeNode*)> dfs

= [&](TreeNode* c) -> vector<int> {

// f[i] = number of leaves node at distance i.

vector<int> f(distance + 1);

if (!c) return f;

if (!c->left && !c->right) {

f[0] = 1; // a single leaf node

return f;

}

const vector<int>& l = dfs(c->left);

const vector<int>& r = dfs(c->right);

for (int i = 0; i + 1 <= distance; ++i)

for (int j = 0; i + j + 2 <= distance; ++j)

ans += l[i] * r[j];

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

f[i + 1] = l[i] + r[i];

return f;

};

dfs(root);

return ans;

}

};

Java

class Solution {

private int D;

private int ans;

public int countPairs(TreeNode root, int distance) {

this.D = distance;

this.ans = 0;

dfs(root);

return ans;

}

private int[] dfs(TreeNode root) {

int[] f = new int[D + 1];

if (root == null) return f;

if (root.left == null && root.right == null) {

f[0] = 1;

return f;

}

int[] fl = dfs(root.left);

int[] fr = dfs(root.right);

for (int i = 0; i + 1 <= D; ++i)

for (int j = 0; i + j + 2 <= D; ++j)

this.ans += fl[i] * fr[j];

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

f[i + 1] = fl[i] + fr[i];

return f;

}

Python3

# Author: Huahua

class Solution:

def countPairs(self, root: TreeNode, D: int) -> int:

def dfs(node):

f = [0] * (D + 1)

if not node: return f, 0

if not node.left and not node.right:

f[0] = 1

return f, 0

fl, pl = dfs(node.left)

fr, pr = dfs(node.right)

pairs = 0

for dl, cl in enumerate(fl):

for dr, cr in enumerate(fr):

if dl + dr + 2 <= D: pairs += cl * cr

for i in range(D):

f[i + 1] = fl[i] + fr[i]

return f, pl + pr + pairs

return dfs(root)[1]

花花酱 1528. Shuffle String

By zxi on July 25, 2020

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the i^th position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

s.length == indices.length == n
1 <= n <= 100
s contains only lower-case English letters.
0 <= indices[i] < n
All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string restoreString(string s, vector<int>& indices) {

string ans(s);

for (int i = 0; i < indices.size(); ++i)

ans[indices[i]] = s[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String restoreString(String s, int[] indices) {

char[] ans = new char[s.length()];

for (int i = 0; i < s.length(); ++i)

ans[indices[i]] = s.charAt(i);

return new String(ans);

}

Pyhton3

class Solution:

def restoreString(self, s: str, indices: List[int]) -> str:

ans = [None] * len(s)

for i, idx in enumerate(indices):

ans[idx] = s[i]

return ''.join(ans)

花花酱 LeetCode 1526. Minimum Number of Increments on Subarrays to Form a Target Array

By zxi on July 25, 2020

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:

Input: target = [1,1,1,1]
Output: 1

Constraints:

1 <= target.length <= 10^5
1 <= target[i] <= 10^5

Solution:

If arr[i] < arr[i – 1], if we can generate arr[i] then we can always generate arr[i] with no extra cost.
e.g. [3, 2, 1] 3 < 2 < 1, [0,0,0] => [1,1,1] => [2, 2, 1] => [3, 2, 1]

So we only need to handle the case of arr[i] > arr[i – 1], we can reuse the computation, with extra cost of arr[i] – arr[i-1].
e.g. [2, 5]: [0,0] => [1, 1] => [2, 2], it takes 2 steps to cover arr[0].
[2,2] => [2, 3] => [2, 4] => [2, 5], takes another 3 steps (arr[1] – arr[0] / 5 – 2) to cover arr[1].

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

C++

class Solution {

public:

int minNumberOperations(vector<int>& target) {

int ans = target[0];

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

ans += max(0, target[i] - target[i - 1]);

return ans;

}

};

花花酱 LeetCode 1525. Number of Good Ways to Split a String

By zxi on July 25, 2020

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

Constraints:

s contains only lowercase English letters.
1 <= s.length <= 10^5

Solution: Sliding Window

Count the frequency of each letter and count number of unique letters for the entire string as right part.
Iterate over the string, add current letter to the left part, and remove it from the right part.
We only
1. increase the number of unique letters when its frequency becomes to 1
2. decrease the number of unique letters when its frequency becomes to 0

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

C++

class Solution {

public:

int numSplits(string s) {

vector<int> r(26);

vector<int> l(26);

int cr = 0;

for (char c : s)

cr += (++r[c - 'a'] == 1);

int ans = 0;

int cl = 0;

for (char c : s) {

cl += (++l[c - 'a'] == 1);

cr -= (--r[c - 'a'] == 0);

ans += cl == cr;

}

return ans;

}

};

java

class Solution {

public int numSplits(String s) {

int[] l = new int[26];

int[] r = new int[26];

int ans = 0;

int cl = 0;

int cr = 0;

for (char c : s.toCharArray())

if (++r[c - 'a'] == 1) ++cr;

for (char c : s.toCharArray()) {

if (++l[c - 'a'] == 1) ++cl;

if (--r[c - 'a'] == 0) --cr;

if (cl == cr) ++ans;

}

return ans;

}

Python3

class Solution:

def numSplits(self, s: str) -> int:

s = [ord(c) - ord('a') for c in s]

l, r = [0] * 26, [0] * 26

cl, cr, ans = 0, 0, 0

for c in s:

r[c] += 1

if r[c] == 1: cr += 1

for c in s:

l[c] += 1

r[c] -= 1

if l[c] == 1: cl += 1

if r[c] == 0: cr -= 1

if cl == cr: ans += 1

return ans

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

By zxi on July 25, 2020

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

C++

class Solution {

public:

int numOfSubarrays(vector<int>& arr) {

const int n = arr.size();

constexpr int kMod = 1e9 + 7;

// dp[i][0] # of subarrays ends with a[i-1] have even sums.

// dp[i][1] # of subarrays ends with a[i-1] have odd sums.

vector<vector<int>> dp(n + 1, vector<int>(2));

long ans = 0;

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

if (arr[i - 1] & 1) {

dp[i][0] = dp[i - 1][1];

dp[i][1] = dp[i - 1][0] + 1;

} else {

dp[i][0] = dp[i - 1][0] + 1;

dp[i][1] = dp[i - 1][1];

}

ans += dp[i][1];

}

return ans % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int numOfSubarrays(int[] arr) {

long ans = 0, odd = 0, even = 0;

for (int x : arr) {

even += 1;

if (x % 2 == 1) {

long t = even; even = odd; odd = t;

}

ans += odd;

}

return (int)(ans % (int)(1e9 + 7));

}

Python3

# Author: Huahua

class Solution:

def numOfSubarrays(self, arr: List[int]) -> int:

ans, odd, even = 0, 0, 0

for x in arr:

if x & 1:

odd, even = even + 1, odd

else:

odd, even = odd, even + 1

ans += odd

return ans % int(1e9 + 7)

Huahua's Tech Road

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

Solution: Brute Force

C++

Solution 2: Post order traversal

C++

Java

Python3

花花酱 1528. Shuffle String

Solution: Simulation

C++

Java

Pyhton3

花花酱 LeetCode 1526. Minimum Number of Increments on Subarrays to Form a Target Array

Solution:

C++

花花酱 LeetCode 1525. Number of Good Ways to Split a String

Solution: Sliding Window

C++

java

Python3

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

Solution: DP

C++

Java

Python3