Huahua’s Tech Road

花花酱 LeetCode 201. Bitwise AND of Numbers Range

By zxi on December 5, 2021

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2³¹ - 1

Solution: Bit operation

Bitwise AND all the numbers between left and right will clear out all the low bits. Basically this question is asking to find the common prefix of left and right in the binary format.

5 = 0b0101
7 = 0b0111
the common prefix is 0b0100 which is 4.

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

C++

// Author: Huahua

class Solution {

public:

int rangeBitwiseAnd(int left, int right) {

while (right > left)

right &= (right - 1); // clears the lowest set bit.

return right;

}

};

花花酱 LeetCode 2097. Valid Arrangement of Pairs

By zxi on December 5, 2021

You are given a 0-indexed 2D integer array pairs where pairs[i] = [start_i, end_i]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have end_i-1 == start_i.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 9 == 9 = start₁ 
end₁ = 4 == 4 = start₂
end₂ = 5 == 5 = start₃

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 3 == 3 = start₁
end₁ = 2 == 2 = start₂
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 2 == 2 = start₁
end₁ = 1 == 1 = start₂

Constraints:

1 <= pairs.length <= 10⁵
pairs[i].length == 2
0 <= start_i, end_i <= 10⁹
start_i != end_i
No two pairs are exactly the same.
There exists a valid arrangement of pairs.

Solution: Eulerian trail

The goal of the problem is to find a Eulerian trail in the graph.

If there is a vertex whose out degree – in degree == 1 which means it’s the starting vertex. Otherwise wise, the graph must have a Eulerian circuit thus we can start from any vertex.

We can use Hierholzer’s algorithm to find it.

Time complexity: O(|V| + |E|)
Space complexity: O(|V| + |E|)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {

unordered_map<int, queue<int>> g;

unordered_map<int, int> degree; // out - in

for (const auto& p : pairs) {

g[p[0]].push(p[1]);

++degree[p[0]];

--degree[p[1]];

}

int s = pairs[0][0];

for (const auto& [u, d] : degree)

if (d == 1) s = u;

vector<vector<int>> ans;

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

while (!g[u].empty()) {

int v = g[u].front(); g[u].pop();

dfs(v);

ans.push_back({u, v});

}

};

dfs(s);

return {rbegin(ans), rend(ans)};

}

};

Python3

# Author: Huahua

class Solution:

def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:

g = defaultdict(list)

d = defaultdict(int)

for u, v in pairs:

g[u].append(v)

d[u] += 1

d[v] -= 1

s = pairs[0][0]

for u in d:

if d[u] == 1: s = u

ans = []

def dfs(u: int) -> None:

while g[u]:

v = g[u].pop()

dfs(v)

ans.append([u, v])

dfs(s)

return ans[::-1]

花花酱 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

By zxi on December 5, 2021

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= n
All the values in the tree are unique.
1 <= startValue, destValue <= n
startValue != destValue

Solution: Lowest common ancestor

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node.
The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.
e.g.
root to start “LLRLR”
root to dest “LLLR”
common prefix is “LL”, after removing, it becomes:
LCA to start “RLR”
LCA to dest “LR”
Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

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

C++

// Author: Huahua

class Solution {

public:

string getDirections(TreeNode* root, int startValue, int destValue) {

string startPath;

string destPath;

buildPath(root, startValue, startPath);

buildPath(root, destValue, destPath);

// Remove common suffix (shared path from root to LCA)

while (!startPath.empty() && !destPath.empty()

&& startPath.back() == destPath.back()) {

startPath.pop_back();

destPath.pop_back();

}

reverse(begin(destPath), end(destPath));

return string(startPath.size(), 'U') + destPath;

}

private:

bool buildPath(TreeNode* root, int t, string& path) {

if (!root) return false;

if (root->val == t) return true;

if (buildPath(root->left, t, path)) {

path.push_back('L');

return true;

} else if (buildPath(root->right, t, path)) {

path.push_back('R');

return true;

}

return false;

}

};

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

By zxi on December 4, 2021

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 
All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: 
The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: 
No even integers can be formed using the given digits.

Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation: 
The only valid integer that can be formed with three digits and no leading zeros is 200.

Example 5:

Input: digits = [0,0,0]
Output: []
Explanation: 
All the integers that can be formed have leading zeros. Thus, there are no valid integers.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Solution: Enumerate all three digits even numbers

Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.

Time complexity: O(1000*lg(1000))
Space complexity: O(10)

C++

// Author: Huahua

class Solution {

public:

vector<int> findEvenNumbers(vector<int>& digits) {

vector<int> counts(10);

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

vector<int> ans;

for (int x = 100; x < 1000; x += 2) {

bool valid = true;

vector<int> c(10);

for (int t = x; t > 0; t /= 10)

valid &= (++c[t % 10] <= counts[t % 10]);

if (valid) ans.push_back(x);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 201. Bitwise AND of Numbers Range

Solution: Bit operation

C++

花花酱 LeetCode 2097. Valid Arrangement of Pairs

Solution: Eulerian trail

C++

Python3

花花酱 LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another

Solution: Lowest common ancestor

C++

花花酱 LeetCode 2095. Delete the Middle Node of a Linked List

Solution: Fast / Slow pointers

C++

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

Solution: Enumerate all three digits even numbers

C++