Huahua’s Tech Road

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

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

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 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 2095. Delete the Middle Node of a Linked List

By zxi on December 4, 2021

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋^th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

The number of nodes in the list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Solution: Fast / Slow pointers

Use fast / slow pointers to find the previous node of the middle one, then skip the middle one.

prev.next = prev.next.next

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

C++

class Solution {

public:

ListNode* deleteMiddle(ListNode* head) {

ListNode dummy(0, head);

ListNode* prev = &dummy;

ListNode* fast = head;

// prev points to the previous node of the middle one.

while (fast && fast->next) {

prev = prev->next;

fast = fast->next->next;

}

prev->next = prev->next->next;

return dummy.next;

}

};

Huahua's Tech Road

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

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