define

Parallel lookup Set is also called Disjoint Set, which is mainly used to solve the problem of grouping some elements. There are two main operations: “merge sets” and “find elements in sets”. And lookup sets are perfect for solving “join” related problems.

Core operations

Find: To find the collection in which the element is located (the collection here refers to a generalized collection of data)

Union: To combine the sets of two elements into a single set

Implementation approach

There are two main implementation ideas. In practice, Quick Union is recommended.

Quick Find

Time complexity of find: O(1) Time complexity of union: O(n)

Quick Union: O(logn) Quick Union: O(logn)

Code implementation

When initialized, each element belongs to a single element collection

Quick Find union(v1, v2): all elements of the set v1 refer to the root of v2

Quick Find implementation

class UnionFind { constructor(n) { this.parents = new Array(n); } init() { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; }} find(x) {return this.parents[v]; } // union(x, y) {let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; for (let i = 0; i < this.parents.length; i++) { if (this.parents[i] == p1) { this.parents[i] = p2; IsSame (x, y) {return this.find(x) === this.find(y)}}Copy the code

Quick Union Union (v1, v2): let the root of v1 point to the root of v2

The Quick Union implementation

class UnionFind { constructor() { this.parents = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; }} find(x) {while (x! = this.parents[x]) { x = this.parents[x]; } return x; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; this.parents[p1] = p2; } return this.find(x) === this.find(y)} return this.find(y) === this.find(y)}}Copy the code

The Quick Union optimization

In the process of union, unbalanced trees may appear, or even degenerate into linked lists, which need to be optimized.

There are two common optimization schemes:

  • Size-based optimization: grafting a tree with fewer elements onto a tree with more elements
  • Rank based optimization: Grafting a short tree onto a tall tree

Quick Union – Size based optimization

class UnionFind { constructor() { this.parents = new Array(n); this.sizes = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.sizes.length; i++) { this.sizes[i] = 1; }} find(x) {while (x! = this.parents[x]) { x = this.parents[x]; } return x; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.sizes[p1] < this.sizes[p2]) { this.parents[p1] = p2; this.sizes[p2] += this.sizes[p1]; } else { this.parents[p2] = p1; this.sizes[p1] += this.sizes[p2]; IsSame (x, y) {return this.find(x) === this.find(y)}}Copy the code

Quick Union – Rank based optimization

Optimization based on size also leads to tree imbalance, as shown in the figure below

Rank based optimization, as shown in the figure below

class UnionFind { constructor() { this.parents = new Array(n); this.ranks = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; }} find(x) {while (x! = this.parents[x]) { x = this.parents[x]; } return x; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; IsSame (x, y) {return this.find(x) === this.find(y)}}Copy the code

Path Compression

Based on rank optimization, the tree will be relatively balanced, but with the increase of Union times, the height of the tree will still be higher and higher, resulting in a slow find operation, especially for the bottom node (because find is constantly going up to find the root node). Therefore, it can be optimized based on path compression. Path compression means that all nodes on the path point to the root during find, thus reducing the height of the tree.

class UnionFind { constructor() { this.parents = new Array(n); this.ranks = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; Find (x) {if (this.parents[x]! = x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; IsSame (x, y) {return this.find(x) === this.find(y)}}Copy the code

Path compression makes all nodes on a path point to the root node, which has a slightly higher implementation cost (the above implementation adopts recursive implementation). There are two better implementations, which can not only reduce the height of the tree, but also lower implementation cost than path compression, path Spliting and path Halving.

Path Spliting

Path splitting occurs when each node points to its parent during find, as shown in the figure below.

The implementation process is based on rank optimization, the difference is the find implementation, the code is as follows:

find(v) { while (v ! = this.parents[v]) { let p = this.parents[v]; this.parents[v] = this.parents[this.parents[v]]; v = p; } return v; }Copy the code

Path Halving

Path halving means that every other node in the find process points to its parent node (parent’s parent), as shown in the figure below.

The implementation process is based on rank optimization, the difference is the find implementation, the code is as follows:

find(v) { while (v ! = this.parents[v]) { this.parents[v] = this.parents[this.parents[v]]; v = this.parents[v];; } return v; }Copy the code

The Union – Find application

990. Satisfiability of equality equations

Given an array of string equations representing relationships between variables, each equation [I] is of length 4 and takes one of two different forms: “A ==b” or” A! = b “. In this case, a and b are lowercase (not necessarily different) letters that represent single-letter variable names. Return true only if an integer can be assigned to a variable name so that all given equations are satisfied, false otherwise.

Example 1: Input: [" A ==b","b!=a"] Output: false Explanation: If we specify a= 1 and b = 1, then the first equation can be satisfied, but not the second equation. There's no way to assign variables that satisfy both of these equations. Example 2: Input: ["b==a","a==b"] Output: true Explanation: We can specify a= 1 and b= 1 to satisfy both equations.Copy the code

Source: leetcode-cn.com/problems/sa…

/** * @param {string[]} equations * @return {boolean} */ var equationsPossible = function(equations) { const uf = new For (const e of equations) {if(e[1] === '=') uf. Union (e.charcodeat (0) -97, For (const e of equations) {if(e[1] === '! ' && uf.find(e.charCodeAt(0) - 97) === uf.find(e.charCodeAt(3) - 97)) { return false; } } return true; }; class UnionFind { constructor(num) { this.parents = new Array(num); this.ranks = new Array(num); for (let i = 0; i < num; i++) { this.parents[i] = -1; this.ranks[i] = 0; } } find(x) { while(this.parents[x] ! == -1) { x = this.parents[x]; } return x; } union(x, y) { let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; }}}Copy the code

547. Number of provinces

There are n cities, some of which are connected to each other, some of which are not. If city A is directly connected to city B, and city B is directly connected to city C, then city A is indirectly connected to city C. A province is a group of directly or indirectly connected cities that do not contain other unconnected cities. IsConnected [I][j] = 1 indicates that the ith city and the j city are directly connected, and isConnected[I][j] = 0 indicates that the two are not directly connected. Returns the number of provinces in the matrix.

Source: leetcode-cn.com/problems/nu…

Code implementation: the path compression way to achieve

/** * @param {number[][]} isConnected * @return {number} */ var findCircleNum = function(isConnected) { const provines =  isConnected.length; const uf = new UnionFind(provines); uf.init(provines); for (let i = 0; i < provines; i++) { for (let j = i + 1; j < provines; j++) { if(isConnected[i][j] === 1) { uf.union(i, j) } } } let circles = 0; uf.parents.forEach((ele, index) => { if(ele === index) { circles++; }}); return circles; }; class UnionFind { constructor(n) { this.parents = new Array(n); this.ranks = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; Find (x) {if (this.parents[x]! = x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; }}}Copy the code

130. The surrounding area

Given a two-dimensional matrix consisting of ‘X’ and ‘O’ (the letter O). Find all the regions surrounded by ‘X’ and fill all the ‘O’ in these regions with ‘X’.

Example:

 X X X X

X O O X

X X O X

X O X X 

After running your function, the matrix becomes:

 X X X X

X X X X

X X X X

X O X X 

Source: leetcode-cn.com/problems/su…

/** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */ var solve = function (board) { class unionFind { constructor(n) { this.count = n; this.parents = new Array(n); for (let i = 0; i < n; i++) { this.parents[i] = i; } } find(p) { if (this.parents[p] ! = p) { this.parents[p] = this.find(this.parents[p]); } return this.parents[p]; } union(p, q) { let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return; this.parents[rootP] = rootQ; this.count--; } isConnected(p, q) { return this.find(p) === this.find(q) } } let row = board.length; if (row == 0) return; let col = board[0].length; let dummy = row * col; let uf = new unionFind(dummy); let arr = [[1, 0], [0, 1], [-1, 0], [0, -1]]; For (let I = 0; i < row; i++) { for (let j = 0; j < col; J++) {if (board [I] [j] = = 'O') {/ / four boundary all unicom if (I = = 0 | | j = = 0 | | I = = row - 1 | | j = = col - 1) {uf. The union (col + I * J, dummy)} else {for (let k = 0; k < 4; k++) { let x = i + arr[k][0]; let y = j + arr[k][1]; if (board[x][y] == 'O') uf.union(x * col + y, i * col + j); }}}}} // For (let I = 1; i < row - 1; i++) { for (let j = 1; j < col - 1; j++) { if (! uf.isConnected(i * col + j, dummy)) board[i][j] = 'X'; }}};Copy the code

200. Number of islands

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically. Furthermore, you can assume that all four sides of the grid are surrounded by water.

Example 1: input: grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 ", "0" and "0" and "0" and "0"]] output: 1 example 2: input: grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 ", "0" and "0", "1", "1"]] output: 3Copy the code

Source: leetcode-cn.com/problems/nu…

/** * @param {character[][]} grid * @return {number} */ var numIslands = function(grid) { const Y = grid.length; const X = grid[0].length; const uf = new UnionFind(); for (let i = 0; i < Y; i++) { for (let j = 0; j < X; j++) { if(grid[i][j] == 1) { uf.makeSet([i, j]) } } } for (let i = 0; i < Y; i++) { for (let j = 0; j < X; j++) { if(grid[i][j] == 1) { if((i + 1 < Y) && (grid[i + 1][j] == 1)) uf.union([i, j], [i + 1, j]); if((j + 1 < X) && (grid[i][j + 1] == 1)) uf.union([i, j], [i, j+ 1]); } } } return uf.getCount(); }; class UnionFind { constructor() { this.parents = {}; this.count = 0; } makeSet(x) { this.parents[x] = x + ''; this.count++; } // find(x) {while ((x + ")! = this.parents[x]) { x = this.parents[x]; } return x + ''; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; this.parents[p1] = p2; this.count--; } getCount(x, y) {return this.count; }}Copy the code

684. Redundant connections

In this problem, tree refers to an undirected graph that is connected and acyclic. Enter a graph consisting of a graph with N nodes (the node values do not repeat 1, 2… , N) tree and an additional edge. The two vertices of the appended edge are contained between 1 and N, and the appended edge does not belong to an existing edge in the tree. The resulting graph is a two-dimensional array of edges. The elements of each edge are a pair [u, v], such that u < v, representing the edges of the undirected graph connecting vertices U and v. Returns an edge that can be deleted, resulting in a tree with N nodes. If there are more than one answer, the last edge to appear in the two-dimensional array is returned. Answer edges [u, v] should satisfy the same format u < v.

Example 1: input: [[1, 2], [1, 3], [2, 3]] output: [2, 3] : given the undirected the graph is: 1 / \ 2-3 example 2: input: [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] output: [1, 4] explain: given the undirected the graph is: 5-1-2 | | 4 to 3Copy the code

Source: leetcode-cn.com/problems/re…

/** * @param {number[][]} edges * @return {number[]} */ var findRedundantConnection = function(edges) { const count = edges.length; const uf = new UnionFind(count + 1); uf.init(count + 1); for (let i = 0; i < count; i++) { const edge = edges[i]; const node1 = edge[0], node2 = edge[1]; if(uf.find(node1) ! == uf.find(node2)) { uf.union(node1, node2) } else { return edge; } } return [0] }; class UnionFind { constructor(n) { this.parents = new Array(n); this.ranks = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; Find (x) {if (this.parents[x]! = x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; }}}Copy the code

1319. Number of network access operations

Ethernet cables are used to connect n computers, numbered from 0 to N-1, into a network. Connections [I] = [a, B] Connects computers A and B. Any computer on the network can directly or indirectly access any other computer on the same network. To give you the initial wiring connections for this computer network, you can unplug any cable between two directly connected computers and use it to connect a pair of not directly connected computers. Please calculate and return the minimum number of operations required to get all computers connected. If that is not possible, -1 is returned.

Example 1: input: n = 4, connections = [[0,1],[0,2]] output: 1 description: unplug the cable between computers 1 and 2, and plug it into computers 1 and 3.Copy the code

Source: leetcode-cn.com/problems/nu…

You can use and look up the set to get the number of connected components in the graph. If it contains N nodes, then the number of connected components is n at the beginning, and the number of connected components will decrease by 1 for each successful merge operation.

var makeConnected = function(n, connections) { if(connections.length < n - 1) { return -1; } const uf = new UnionFind(n); uf.init(n); for (const conn of connections) { uf.union(conn[0], conn[1]) } return uf.count - 1; }; class UnionFind { constructor(n) { this.parents = new Array(n); this.ranks = new Array(n); this.count = n; } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; Find (x) {if (this.parents[x]! = x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; } this.count--; } return this.find(x) === this.find(y)} return this.find(y) === this.find(y)}}Copy the code

765. Lovers hold hands

N couples are sitting in 2N consecutive seats, trying to hold each other’s hands. Count the minimum number of times you can switch seats so that each couple can sit side by side. Choose any two people at a time and have them stand up and switch seats. People and seats are represented by integers from 0 to 2n-1, and couples are numbered in order, with the first pair (0, 1), the second pair (2, 3), and so on, and the last pair (2N-2, 2N-1). The couples’ initial seat row[I] is determined by the person who originally sat in the ith seat.

Example 1: Input: row = [0, 2, 1, 3] Output: 1 Explanation: We simply swap the positions of row[1] and row[2]. Example 2: Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples can already hold hands without switching seats.Copy the code

Source: leetcode-cn.com/problems/co…

Each connected component of the graph is obtained by using and searching the set. For each connected component, its magnitude minus 1 is the number of swaps required.

var minSwapsCouples = function(row) { let len = row.length; let N = len / 2; const uf = new UnionFind(N); for (let i = 0; i < len; i += 2) { uf.union(Math.floor(row[i] / 2), Math.floor(row[i + 1] / 2)) } return N - uf.getCount(); }; class UnionFind { constructor(n) { this.parents = new Array(n).fill(0).map((ele, index) => index); this.count = n; } find(v) { while (v ! = this.parents[v]) { this.parents[v] = this.parents[this.parents[v]]; v = this.parents[v];; } return v; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; this.parents[p1] = p2; this.count--; } getCount() {return this.count; }}Copy the code

839. Similar string group

Strings X and Y are said to be similar if they swap letters at two different positions in string X so that it is equal to string Y. If the two strings themselves are equal, they are also similar. For example, “tars” and “rats” are similar (swap 0s and 2s); “Rats” is also similar to “arts”, but “star” is not similar to “tars”, “rats”, or “arts”. In summary, they form two association groups through similarity: {“tars”, “rats”, “arts”} and {“star”}. Note that “tars” and “arts” are in the same group, even though they are not similar. Formally, for each group, all that is needed to identify a word as being in the group is for that word to be similar to at least one word in that group. I give you a list of strings, STRS. Each string in the list is an anagram of all the other strings in STRS. How many similar string groups are there in STRS?

Example 1: Input: STRS = ["tars"," RATS ","arts","star"] Example 2: Input: STRS = [" OMV "," oVM "] Output: 1Copy the code

Source: leetcode-cn.com/problems/si…

var numSimilarGroups = function(strs) { const n = strs.length; const m = strs[0].length; const uf = new UnionFind(n); for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if(check(strs[i], strs[j], m)) { uf.union(i, j) } } } return uf.count; }; function check(a, b, length) { let count = 0; for (let i = 0; i < length; i++) { if(a[i] ! == b[i]) { count++; if(count > 2) { return false; } } } return true; } class UnionFind { constructor(n) { this.parents = new Array(n).fill(0).map((element, index) => index); this.sizes = new Array(n).fill(1); this.count = n; } // find(x) {while (x! = this.parents[x]) { x = this.parents[x]; } return x; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.sizes[p1] < this.sizes[p2]) { this.parents[p1] = p2; this.sizes[p2] += this.sizes[p1]; } else { this.parents[p2] = p1; this.sizes[p1] += this.sizes[p2]; } this.count--; }}Copy the code

947. Removal of the largest number of stones in the same row or row

N stones are placed at integer coordinate points in a two-dimensional plane. There can be no more than one stone on each coordinate point. A stone can be removed if there are other stones in the same row or row as a stone. Stones [I] = [xi, yi]; stones[I] = [xi, yi];

Example 1: input: featuring = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2]] output: 5: a way to remove the five stone is as follows: 1. Remove stone [2,2] as it walks with stone [2,1]. 2. Remove rock [2,1] as it is in the same column as [0,1]. 3. Remove stone [1,2] as it walks with [1,0]. 4. Remove the stone [1,0] as it is in the same column as [0,0]. 5. Remove the rock [0,1] as it runs with [0,0]. The stone [0,0] cannot be removed because it is not in line/column with another stone.Copy the code

Source: leetcode-cn.com/problems/mo…

var removeStones = function(stones) {
    const unionFindSet = new UnionFind();
    for(let stone of stones) {
        unionFindSet.union(stone[0], stone[1] + 10000);
    }
    return stones.length - unionFindSet.getCount();
};

class UnionFind {
    constructor() {
        this.parents = [];
        this.count = 0;
        this.ranks = []
    }
    init(x) {
        if(this.parents[x] === undefined) {
            this.parents[x] = x;
            this.ranks[x] = 0;
            this.count++;
        }
    }
    getCount() {
        return this.count;
    }
    find(x) {
        if(this.parents[x] !== x) {
            this.parents[x] = this.find(this.parents[x]);
        }
        return this.parents[x]
    }
    union(x, y) {
        this.init(x);
        this.init(y);
        let rootX = this.find(x);
        let rootY = this.find(y);
        if(rootX === rootY) return;
        if(this.ranks[rootX] > this.ranks[rootY]) {
            this.parents[rootY] = rootX;
        } else if (this.ranks[rootX] < this.ranks[rootY]) {
            this.parents[rootX] = rootY;
        } else {
            this.parents[rootY] = rootX;
            this.ranks[rootX]++;
        }
        this.count--;
    }
}
Copy the code

Area delimited by a slash

In an N x N grid of 1 x 1 squares, each 1 x 1 square is composed of /, \, or Spaces. These characters divide the square into areas with common sides. (Note that the backslash character is escaped, so \ is represented by “\\”.) . The number of regions returned.

Example 1: Input: ["/ ", "/ "] Output: 2 Explanation: the 2x2 grid is as follows:Copy the code

Example 2: Input: [" /", ""] Output: 1 Explanation: the 2x2 grid is as follows:Copy the code

Example 3: input: [" \ \ / ", "/ \ \"] output: 4 explain: (recall that because \ characters are escaped, so \ \ \ "/" said /, whereas / \ "/ \ \".) The 2x2 grid is as follows:Copy the code

Example 4: input: [" / \ \ ", \ \ "/"] output: 5 explanation: (recall that because \ characters are escaped, so / \ "/ \ \", \ \ \ "/" said /.) The 2x2 grid is as follows:Copy the code

Example 5: Input: ["//", "/ "] Output: 3 Explanation: the 2x2 grid is as follows:Copy the code

Source: leetcode-cn.com/problems/re…

var regionsBySlashes = function(grid) { let N = grid.length; let size = 4 * N * N; const UF = new UnionFind(size); UF.init(size); let i, j, c, start; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { c = grid[i].charAt(j); start = (i * N + j) * 4; If (c === ") {UF. Union (start + 0, start + 1); UF.union(start + 1, start + 2); UF.union(start + 2, start + 3); } else if(c === '/') { UF.union(start + 0, start + 3); UF.union(start + 1, start + 2); } else { UF.union(start + 0, start + 1); UF.union(start + 2, start + 3); If (j + 1 < N) {UF. Union (start + 1, 4 * (I * N + j + 1) + 3); } if(i + 1 < N) { UF.union(start + 2, ((i + 1) * N + j) * 4); } } } return UF.getCount(); }; class UnionFind { constructor(n) { this.parents = new Array(n); this.ranks = new Array(n); let count; } init(n) { for (let i = 0; i < n; i++) { this.parents[i] = i; } for (let i = 0; i < n; i++) { this.ranks[i] = 1; } this.count = n; } find(v) { while (v ! = this.parents[v]) { this.parents[v] = this.parents[this.parents[v]]; v = this.parents[v];; } return v; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; } this.count--; } getCount() { return this.count; }}Copy the code

Minimum physical exertion path

You’re going on a hike. Rows x columns heights[row][col] specifies the height of a row. You start with the upper-left cell (0, 0) and you want to go to the lower-right cell (rows-1, soxes-1) (note that the subscripts start numbered at 0). You can go up, down, left or right at a time, and you want to find the path that takes the least effort. The energy cost of a path is determined by the maximum absolute value of the height difference between adjacent grids on the path. Return the minimum physical cost of walking from the top left corner to the bottom right corner.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5] output: 2 description: the absolute value difference of continuous grid of path [1,3,5,3,5] is at most 2. This path is better than path [1,2,2,2,5] because the other path has a maximum difference of 3.Copy the code

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3]] output: 1 description: the absolute value of the difference between adjacent cells of path [1,2,3,4,5] is greater than that of path [1,3,5,3,5].Copy the code

Example 3:

Input: heights = [,2,1,1,1 [1], [1,2,1,2,1],,2,1,2,1 [1],,2,1,2,1 [1], [1,1,1,2,1]] output: 0 explanation: the above path does not need any physical consumption.Copy the code

Source: leetcode-cn.com/problems/pa…

We put the MN nodes in and check the set to maintain their connectivity in real time. Since we need to find the shortest path from the top left corner to the bottom right corner, we can sort all the edges in the graph in order of weight from the smallest to the largest, add them in turn and look up the set. When we add an edge of weight x, if the top left and bottom right go from unconnected to connected, then x is the answer.

var minimumEffortPath = function(heights) { const m = heights.length; const n = heights[0].length; const edges = []; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const id = i * n + j; if(i > 0) { edges.push([id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])]); } if(j > 0) { edges.push([id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])]); } } } edges.sort((a, b) => a[2] - b[2]); const uf = new UnionFind(m * n); let ans = 0; for (const edge of edges) { const x = edge[0], y = edge[1], v = edge[2]; uf.union(x, y); if(uf.isSame(0, m * n - 1)) { ans = v; break; } } return ans; }; class UnionFind { constructor(n) { this.parents = new Array(n).fill(0).map((element, index) => index); this.sizes = new Array(n).fill(1); // The current number of connected components this.setcount = n; } find(x) { if (this.parents[x] ! = x) { this.parents[x] = this.find(this.parents[x]); } return this.parents[x]; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.sizes[p1] < this.sizes[p2]) { this.parents[p1] = p2; this.sizes[p2] += this.sizes[p1]; } else { this.parents[p2] = p1; this.sizes[p1] += this.sizes[p2]; } this.setCount -= 1; return true; } return this.find(x) === this.find(y)} return this.find(y) === this.find(y)}}Copy the code

Interview question 17.07. Baby’s name

Every year, the government publishes the 10,000 most common baby names and their frequency, which is the number of babies with the same name. Some names have multiple spellings, for example, John and Jon are essentially the same name, but are published as two names. Given two lists, one of names and their corresponding frequencies, and the other of essentially identical pairs of names. Design an algorithm to print out the actual frequency of each real name. Note that if John and Jon are the same, and Jon and Johnny are the same, then John and Johnny are the same, i.e., they have transitivity and symmetry. In the result list, select the name with the smallest lexicographic order as the real name.

Example: Input: names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], Synonyms = [(Jon, John) ", "(John and Johnny)", "(Chris, Kris)", "(Chris, Christopher)"] output: [" John (27) ", "Chris (36)"]Copy the code

Source: leetcode-cn.com/problems/ba…

var trulyMostPopular = function(names, synonyms) { const res = []; const hash = {}; const uf = new UnionFind(); for (let n of names) { let name = n.split('(')[0]; uf.makeSet(name); } // console.log(uf) for (let s of synonyms) { const first = s.split(',')[0].slice(1); const second = s.split(',')[1].slice(0, -1); uf.makeSet(first); uf.makeSet(second); } // console.log(uf) for (let s of synonyms) { const first = s.split(',')[0].slice(1); const second = s.split(',')[1].slice(0, -1); uf.union(first, second); } // console.log(uf) for (let n of names){ let name = n.split('(')[0]; let rootName = uf.findSet(name); let frequency = +(n.split('(')[1].slice(0, -1)); hash[rootName] = (hash[rootName] || 0) + Number(frequency); } for (let key in hash) { res.push(`${key}(${hash[key]})`); } return res; }; class UnionFind { constructor() { this.parents = {}; } makeSet(x) { this.parents[x] = x; } findSet(x) { while(this.parents[x] ! == x) { x = this.parents[x] } return x; } union(x, y) { this.link(this.findSet(x), this.findSet(y)); } link(x, y) { if(x === y) return; if(x > y) { this.parents[x] = y; } else { this.parents[y] = x; }}}Copy the code

1202. Exchange elements in a string

You are given a string s and an array of “index pairs” in that string, pairs[I] = [a, b] representing two indexes (numbered from 0) in the string. You can swap characters at any pair of indexes in pairs as many times as you want. Returns the smallest lexicographical string that s can become after a number of swaps.

Example 1: Input: s = "dCAB ", pairs = [[0,3],[1,2]] Output: "bacd" Explanation: Swap S [0] and S [3], s = "bcad" Swap S [1] and s[2], s = "bacd" Example 2: Input: S = "dcab", pairs = [[0, 3], [1, 2], [0, 2]] output: "abcd" explanation: Swap s[0] and S [3], s = "bcad" Swap S [0] and S [2], S = "ACbd" Swap S [1] and S [2], s = "abCD" Example 3: Input: S = "cba", pairs = [[0,1],[1,2]] Exchange s [0] and [1] s, s = "bca exchange" s [1] and [2] s, s = "bac" exchange s [0] and [1] s, s = "ABC"Copy the code

Source: leetcode-cn.com/problems/sm…

Group the strings to be sorted by searching the set and sort them within the group. Then fill back the result value according to the corresponding subscript

var smallestStringWithSwaps = function(s, pairs) { const uf = new UnionFind(s.length); uf.init(); for (const [a, b] of pairs) { uf.union(a, b) } const map = {}; for (let i = 0; i < uf.parents.length; i++) { const root = uf.find(i); map[root] ? map[root].push(i) : (map[root] = [i]) } const result = []; Object.values(map).forEach((value) => { const arr = []; let idx = 0; const tmp = value.map((v) => { arr.push(v) return s[v] }) tmp.sort((a, b) => a.charCodeAt() - b.charCodeAt()); tmp.forEach((c) => { const index = arr[idx++]; result[index] = c; }) }) return result.join('') }; class UnionFind { constructor(n) { this.parents = new Array(n); this.ranks = new Array(n); } init(x) { for (let i = 0; i < this.parents.length; i++) { this.parents[i] = i; } for (let i = 0; i < this.ranks.length; i++) { this.ranks[i] = 1; }} find(x) {while (x! = this.parents[x]) { x = this.parents[x]; } return x; } // union(x, y) {let p1 = this.find(x); let p1 = this.find(x); let p2 = this.find(y); if (p1 == p2) return; if (this.ranks[p1] < this.ranks[p2]) { this.parents[p1] = p2; } else if((this.ranks[p1] > this.ranks[p2])) { this.parents[p2] = p1; } else { this.parents[p1] = p2; this.ranks[p2] += 1; }}}Copy the code