Huahua’s Tech Road

花花酱 LeetCode 1722. Minimize Hamming Distance After Swap Operations

By zxi on January 10, 2021

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [a_i, b_i] indicates that you are allowed to swap the elements at index a_i and index b_i (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

Solution: Union Find

Think each pair as an edge in a graph. Since we can swap as many time as we want, which means we can arrange the elements whose indices are in a connected component (CC) in any order.

For each index i, we increase the counter of CC(i) for key source[i] and decrease the counter of the same CC for key target[i]. If two keys are the same (can from different indices), one from source and one from target, it will cancel out, no distance. Otherwise, the counter will be off by two. Finally we sum up the counter for all the keys and divide it by two to get the hamming distance.

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

C++

// Author: huahua

class Solution {

public:

int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {

const int n = source.size();

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return x == p[x] ? x : p[x] = find(p[x]);

};

for (const auto& s : allowedSwaps)

p[find(s[0])] = find(s[1]);

unordered_map<int, unordered_map<int, int>> m;

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

++m[find(i)][source[i]];

--m[find(i)][target[i]];

}

int ans = 0;

for (const auto& g : m)

for (const auto& kv : g.second)

ans += abs(kv.second);

return ans / 2;

}

};

花花酱 LeetCode 1720. Decode XORed Array

By zxi on January 10, 2021

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

Constraints:

2 <= n <= 10⁴
encoded.length == n - 1
0 <= encoded[i] <= 10⁵
0 <= first <= 10⁵

Solution: XOR

encoded[i] = arr[i] ^ arr[i + 1]
encoded[i] ^ arr[i] = arr[i] ^ arr[i] ^ arr[i + 1]
arr[i+1] = encoded[i]^arr[i]

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

C++

class Solution {

public:

vector<int> decode(vector<int>& encoded, int first) {

const int n = encoded.size() + 1;

vector<int> ans(n, first);

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

ans[i + 1] = ans[i] ^ encoded[i];

return ans;

}

};

花花酱 LeetCode 1719. Number Of Ways To Reconstruct A Tree

By zxi on January 9, 2021

You are given an array pairs, where pairs[i] = [x_i, y_i], and:

There are no duplicates.
x_i < y_i

Let ways be the number of rooted trees that satisfy the following conditions:

The tree consists of nodes whose values appeared in pairs.
A pair [x_i, y_i] exists in pairs if and only if x_i is an ancestor of y_i or y_i is an ancestor of x_i.
Note: the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

0 if ways == 0
1 if ways == 1
2 if ways > 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

Constraints:

1 <= pairs.length <= 10⁵
1 <= x_i< y_i <= 500
The elements in pairs are unique.

Solution: Bitset

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

C++

// Author: Huahua

class Solution {

public:

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

// Construct a map, key is the node, value is the accessible nodes.

unordered_map<int, bitset<501>> m;

for (auto& e : pairs)

m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1;

// The tree must have one+ node/root that has paths to all the nodes.

if (!any_of(begin(m), end(m), [&m](const auto& kv) {

return kv.second.count() == m.size();})) return 0;

int multiple = 0;

for (const auto& e : pairs) {

// For each pair, check whether one can be the parent of another

// that can conver all the children nodes.

const auto& all = m[e[0]] | m[e[1]];

const int r0 = m[e[0]] == all;

const int r1 = m[e[1]] == all;

if (r0 + r1 == 0) return 0;

// If both can be parents, there can be multiple trees.

multiple |= r0 * r1;

}

return 1 + multiple;

}

};

Python3

# Author: Huahua

class Solution:

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

m = defaultdict(set)

for u, v in pairs:

m[u] |= set((u, v))

m[v] |= set((u, v))

if not any(len(m[x]) == len(m) for x in m):

return 0

multiple = 0

for u, v in pairs:

union = m[u] | m[v]

ru, rv = int(m[u] == union), int(m[v] == union)

if not ru + rv: return 0

multiple |= ru * rv

return 1 + multiple

花花酱 LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

By zxi on January 9, 2021

Given an integer n, find a sequence that satisfies all of the following:

The integer 1 occurs once in the sequence.
Each integer between 2 and n occurs twice in the sequence.
For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

1 <= n <= 20

Solution: Search

Search from left to right, largest to smallest.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> constructDistancedSequence(int n) {

const int len = 2 * n - 1;

vector<int> ans(len);

function<bool(int, int)> dfs = [&](int i, int s) {

if (i == len) return true;

if (ans[i]) return dfs(i + 1, s);

for (int d = n; d > 0; --d) {

const int j = i + (d == 1 ? 0 : d);

if ((s & (1 << d)) || j >= len || ans[j]) continue;

ans[i] = ans[j] = d;

if (dfs(i + 1, s | (1 << d))) return true;

ans[i] = ans[j] = 0;

}

return false;

};

dfs(0, 0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private boolean dfs(int[] ans, int n, int i, int s) {

if (i == ans.length) return true;

if (ans[i] > 0) return dfs(ans, n, i + 1, s);

for (int d = n; d > 0; --d) {

int j = i + (d == 1 ? 0 : d);

if ((s & (1 << d)) > 0 || j >= ans.length || ans[j] > 0)

continue;

ans[i] = ans[j] = d;

if (dfs(ans, n, i + 1, s | (1 << d))) return true;

ans[i] = ans[j] = 0;

}

return false;

}

public int[] constructDistancedSequence(int n) {

int[] ans = new int[n * 2 - 1];

dfs(ans, n, 0, 0);

return ans;

}

Python3

# Author: Huahua

class Solution:

def constructDistancedSequence(self, n: int) -> List[int]:

l = n * 2 - 1

ans = [0] * l

def dfs(i, s):

if i == l: return True

if ans[i]: return dfs(i + 1, s)

for d in range(n, 0, -1):

j = i + (0 if d == 1 else d)

if s & (1 << d) or j >= l or ans[j]: continue

ans[i] = ans[j] = d

if dfs(i + 1, s | (1 << d)): return True

ans[i] = ans[j] = 0

return False

dfs(0, 0)

return ans

Huahua's Tech Road

花花酱 LeetCode 1722. Minimize Hamming Distance After Swap Operations

Solution: Union Find

C++

花花酱 LeetCode 1721. Swapping Nodes in a Linked List

Solution:

C++

花花酱 LeetCode 1720. Decode XORed Array

Solution: XOR

C++

花花酱 LeetCode 1719. Number Of Ways To Reconstruct A Tree

Solution: Bitset

C++

Python3

花花酱 LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Solution: Search

C++

Java

Python3