leetcode常规算法题复盘（第十五期）——除法求值&省份数量&由斜杠划分区域&连通网络的操作次数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode常规算法题复盘（第十五期）——除法求值&省份数量&由斜杠划分区域&连通网络的操作次数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含19944字，纯文字阅读大概需要29分钟。
内容图文
题目原文
399. 除法求值
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000] 解释： 条件：a / b = 2.0, b / c = 3.0 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] 输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] 输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Dj由小写英文字母与数字组成
547. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
提示：
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]为1或0isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
959. 由斜杠划分区域
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。
返回区域的数目。
示例 1：
输入： [ " /", "/ " ] 输出：2 解释：2x2 网格如下：
示例 2：
输入： [ " /", " " ] 输出：1 解释：2x2 网格如下：
示例 3：
输入： [ "\\/", "/\\" ] 输出：4 解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。） 2x2 网格如下：
示例 4：
输入： [ "/\\", "\\/" ] 输出：5 解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。） 2x2 网格如下：
示例 5：
输入： [ "//", "/ " ] 输出：3 解释：2x2 网格如下：
提示：
1 <= grid.length == grid[0].length <= 30grid[i][j]是'/'、'\'、或' '。
1319. 连通网络的操作次数
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
示例 1：
输入：n = 4, connections = [[0,1],[0,2],[1,2]] 输出：1 解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] 输出：2
示例 3：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] 输出：-1 解释：线缆数量不足。
示例 4：
输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]] 输出：0
提示：
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= connections[i][0], connections[i][1]?< nconnections[i][0] != connections[i][1]- 没有重复的连接。
- 两台计算机不会通过多条线缆连接。
尝试解答
由于对图跟并查集比较陌生，这几道题做的是相当费劲（菜是原罪）。
除法求值
1 class Solution {
2 public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
3 int m = queries.size();
4 double[] result = new double[m];
5 //找出结点数n
6 int n = equations.size();
7 UF UnionFind = new UF(n*2);
8 for(int i=0;i<equations.size();i++){
9 UnionFind.union((int)equations.get(i).get(1).charAt(0)-(int)'a',
10 (int)equations.get(i).get(0).charAt(0)-(int)'a',values[i]);
11 UnionFind.union((int)equations.get(i).get(0).charAt(0)-(int)'a',
12 (int)equations.get(i).get(1).charAt(0)-(int)'a',1/values[i]);
13 }
14 m=0;
15 for(List<String> A:queries){
16 char from = A.get(0).charAt(0);
17 char to = A.get(1).charAt(0);
18 double res;
19 if(UnionFind.find((int)from-(int)'a')!=UnionFind.find((int)to-(int)'a')){
20 res = -1.0;
21
22 }
23 else{
24 res = UnionFind.getWeight((int)from-(int)'a',1.0)/UnionFind.getWeight((int)to-(int)'a',1.0);
25 }
26 result[m] = res;
27 m++;
28 }
29 return result;
30 }
31 private class UF{
32 private int[] parent;
33 private double[] weight;
34 public UF(int n){//n为结点的数量
35 int[] parent = new int[n];
36 double[] weight = new double[n];
37 for(int i=0;i<n;i++){
38 parent[i] = i;
39 weight[i] = 1;
40 }
41 this.parent = parent;
42 this.weight = weight;
43 }
44 public void union(int i,int j,double weight){
45 int root_i = find(i);
46 int root_j = find(j);
47 if(root_i==root_j){
48 return;
49 }
50 else{
51 parent[root_i] = root_j;
52 this.weight[root_i] = weight;
53 }
54 }
55 public int find(int i){
56 if(i==parent[i]){
57 return i;
58 }
59 else{
60 i = parent[i];
61 return find(i);
62 }
63 }
64 //作用是返回从当前结点到根节点的权值之积
65 public double getWeight(int i,double weight){
66 if(i==parent[i]){
67 return weight;
68 }
69 else{
70 weight = this.weight[i]*weight;
71 i = parent[i];
72 return getWeight(i,weight);
73 }
74 }
75 }
76 }
代码关系式推导的不正确
省份数量
1 class Solution {
2 public boolean[] vias;
3 public int findCircleNum(int[][] isConnected) {
4 int count = 0;//表示分离的集合数量
5 vias = new boolean[isConnected.length];
6 for(int i=0;i<isConnected.length;i++){
7 if(!vias[i]){
8 count++;
9 dfs(i,isConnected);
10 }
11 }
12 return count;
13 }
14 public void dfs(int v,int[][] isConnected){
15 vias[v] = true;
16 for(int i=0;i<isConnected.length;i++){
17 if(isConnected[v][i]==1 && !vias[i]){
18 dfs(i,isConnected);
19 }
20 }
21 }
22 }
由斜杠划分区域
1 public class Solution {
2
3 public int regionsBySlashes(String[] grid) {
4 int N = grid.length;
5 UnionFind unionFind = new UnionFind(N*N*4);
6 for(int i=0;i<N;i++){
7 for(int j=0;j<N;j++){
8 if(grid[i].charAt(j)==' '){
9 unionFind.union(4*(i*N+j)+0, 4*(i*N+j)+1);
10 unionFind.union(4*(i*N+j)+2, 4*(i*N+j)+3);
11 unionFind.union(4*(i*N+j)+0, 4*(i*N+j)+3);
12 }
13 else if(grid[i].charAt(j)=='/'){
14 unionFind.union(4*(i*N+j)+0, 4*(i*N+j)+3);
15 unionFind.union(4*(i*N+j)+1, 4*(i*N+j)+2);
16 }
17 else{
18 unionFind.union(4*(i*N+j)+0, 4*(i*N+j)+1);
19 unionFind.union(4*(i*N+j)+2, 4*(i*N+j)+3);
20 }
21 if(j<N-1){
22 unionFind.union(4*(i*N+j)+1, 4*(i*N+j+1)+3);
23 }
24 if(i<N-1){
25 unionFind.union(4*(i*N+j)+2, 4*((i+1)*N+j)+0);
26 }
27 }
28 }
29 return unionFind.getCount();
30 }
31 private class UnionFind{
32 //包括的方法有：合并集合、寻找上位、返回最终集合数
33 private int[] parent;
34 private int count;
35 public UnionFind(int num){
36 int[] parent = new int[num];
37 for(int i=0;i<num;i++){
38 parent[i] = i;
39 }
40 this.parent = parent;
41 this.count = num;
42 }
43 public void union(int i,int j){
44 int root_i = find(i);
45 int root_j = find(j);
46 if(root_i==root_j){
47 return;
48 }
49 else{
50 parent[root_j] = root_i;
51 this.count--;
52 }
53 }
54 private int find(int i){
55 if(i==parent[i]){
56 return i;
57 }
58 else{
59 i=parent[i];
60 return find(i);
61 }
62 }
63 public int getCount(){
64 return this.count;
65 }
66 }
67 }
连通网络的操作次数
1 class Solution {
2 boolean[] vias;
3 List<Integer>[] edges;
4 public int makeConnected(int n, int[][] connections) {
5 if(connections.length<n-1){
6 return -1;
7 }
8 edges = new List[n];
9 for(int i=0;i<n;i++){
10 edges[i] = new ArrayList<Integer>();
11 }
12 for(int[] con:connections){
13 edges[con[0]].add(con[1]);
14 edges[con[1]].add(con[0]);
15 }
16 vias = new boolean[n];
17 int ans = 0;
18 for(int i=0;i<n;i++){
19 if(!vias[i]){
20 dfs(i);
21 ans++;
22 }
23 }
24 return ans-1;
25 }
26 public void dfs(int v){
27 vias[v] = true;
28 for(int i:edges[v]){
29 if(!vias[i]){
30 dfs(i);
31 }
32 }
33 }
34 }
标准题解
除法求值
作者：LeetCode
链接：https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码如下：
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int equationsSize = equations.size();
UnionFind unionFind = new UnionFind(2 * equationsSize);
// 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize);
int id = 0;
for (int i = 0; i < equationsSize; i++) {
List<String> equation = equations.get(i);
String var1 = equation.get(0);
String var2 = equation.get(1);
if (!hashMap.containsKey(var1)) {
hashMap.put(var1, id);
id++;
}
if (!hashMap.containsKey(var2)) {
hashMap.put(var2, id);
id++;
}
unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
}
// 第 2 步：做查询
int queriesSize = queries.size();
double[] res = new double[queriesSize];
for (int i = 0; i < queriesSize; i++) {
String var1 = queries.get(i).get(0);
String var2 = queries.get(i).get(1);
Integer id1 = hashMap.get(var1);
Integer id2 = hashMap.get(var2);
if (id1 == null || id2 == null) {
res[i] = -1.0d;
} else {
res[i] = unionFind.isConnected(id1, id2);
}
}
return res;
}
private class UnionFind {
private int[] parent;
/**
* 指向的父结点的权值
*/
private double[] weight;
public UnionFind(int n) {
this.parent = new int[n];
this.weight = new double[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
weight[i] = 1.0d;
}
}
public void union(int x, int y, double value) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
// 关系式的推导请见「参考代码」下方的示意图
weight[rootX] = weight[y] * value / weight[x];
}
/**
* 路径压缩
*
* @param x
* @return 根结点的 id
*/
public int find(int x) {
if (x != parent[x]) {
int origin = parent[x];
parent[x] = find(parent[x]);
weight[x] *= weight[origin];
}
return parent[x];
}
public double isConnected(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return weight[x] / weight[y];
} else {
return -1.0d;
}
}
}
}
//作者：LeetCode
//链接：https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
省份数量
计算连通分量数的另一个方法是使用并查集。初始时，每个城市都属于不同的连通分量。遍历矩阵 \textit{isConnected}isConnected，如果两个城市之间有相连关系，则它们属于同一个连通分量，对它们进行合并。
遍历矩阵isConnected 的全部元素之后，计算连通分量的总数，即为省份的总数。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码如下：
class Solution {
public int findCircleNum(int[][] isConnected) {
int provinces = isConnected.length;
int[] parent = new int[provinces];
for (int i = 0; i < provinces; i++) {
parent[i] = i;
}
for (int i = 0; i < provinces; i++) {
for (int j = i + 1; j < provinces; j++) {
if (isConnected[i][j] == 1) {
union(parent, i, j);
}
}
}
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (parent[i] == i) {
circles++;
}
}
return circles;
}
public void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2);
}
public int find(int[] parent, int index) {
if (parent[index] != index) {
parent[index] = find(parent, parent[index]);
}
return parent[index];
}
}
//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
由斜杠划分区域
这是一个关于连通性的问题，让我们求解连通分量的个数，解决这个问题没有特别的技巧，根据题意 画图分析、稍微细心一点就可以通过系统测评。
可以用深度优先遍历（Depth First Search）、广度优先遍历（Breadth First Search）和并查集（Disjoint Sets），由于只要求计算结果，不要求给出具体的连通信息，可以使用并查集。
方法：并查集
「斜杠」、「反斜杠」把单元格拆分成的 2 个三角形的形态，在做合并的时候需要分类讨论。根据「斜杠」、「反斜杠」分割的特点，我们把一个单元格分割成逻辑上的 4 个部分。如下图所示：
我们须要遍历一次输入的二维网格 grid，在 单元格内 和 单元格间 进行合并。
单元格内：
如果是空格：合并 0、1、2、3；
如果是斜杠：合并 0、3，合并 1、2；
如果是反斜杠：合并 0、1，合并 2、3。
单元格间：
把每一个单元格拆分成 4 个小三角形以后，相邻的单元格须要合并，无须分类讨论。我们选择在遍历 grid 的每一个单元格的时候，分别「向右、向下」尝试合并。
向右：合并 1 （当前单元格）和 3（当前单元格右边 1 列的单元格），上图中红色部分；
向下：合并 2 （当前单元格）和 0（当前单元格下边 1 列的单元格），上图中蓝色部分。
事实上，大家选择在遍历 grid 的每一个单元格的时候，分别「向左、向上」、「向左、向下」、「向右、向上」、「向右、向下」中的任何一种都可以。
合并完成以后，并查集里连通分量的个数就是题目要求的区域的个数。
参考代码：
1 public class Solution {
2
3 public int regionsBySlashes(String[] grid) {
4 int N = grid.length;
5 int size = 4 * N * N;
6
7 UnionFind unionFind = new UnionFind(size);
8 for (int i = 0; i < N; i++) {
9 char[] row = grid[i].toCharArray();
10 for (int j = 0; j < N; j++) {
11 // 二维网格转换为一维表格
12 int index = 4 * (i * N + j);
13 char c = row[j];
14 // 单元格内合并
15 if (c == '/') {
16 // 合并 0、3，合并 1、2
17 unionFind.union(index, index + 3);
18 unionFind.union(index + 1, index + 2);
19 } else if (c == '\\') {
20 // 合并 0、1，合并 2、3
21 unionFind.union(index, index + 1);
22 unionFind.union(index + 2, index + 3);
23 } else {
24 unionFind.union(index, index + 1);
25 unionFind.union(index + 1, index + 2);
26 unionFind.union(index + 2, index + 3);
27 }
28
29 // 单元格间合并
30 // 向右合并：1（当前）、3（右一列）
31 if (j + 1 < N) {
32 unionFind.union(index + 1, 4 * (i * N + j + 1) + 3);
33 }
34 // 向下合并：2（当前）、0（下一行）
35 if (i + 1 < N) {
36 unionFind.union(index + 2, 4 * ((i + 1) * N + j));
37 }
38 }
39 }
40 return unionFind.getCount();
41 }
42
43 private class UnionFind {
44
45 private int[] parent;
46
47 private int count;
48
49 public int getCount() {
50 return count;
51 }
52
53 public UnionFind(int n) {
54 this.count = n;
55 this.parent = new int[n];
56 for (int i = 0; i < n; i++) {
57 parent[i] = i;
58 }
59 }
60
61 public int find(int x) {
62 while (x != parent[x]) {
63 parent[x] = parent[parent[x]];
64 x = parent[x];
65 }
66 return x;
67 }
68
69 public void union(int x, int y) {
70 int rootX = find(x);
71 int rootY = find(y);
72 if (rootX == rootY) {
73 return;
74 }
75
76 parent[rootX] = rootY;
77 count--;
78 }
79 }
80 }
81
82 //作者：LeetCode
83 //链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/
84 //来源：力扣（LeetCode）
85 //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
作者：LeetCode
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
连通网络的操作次数
基本思路与前四道题相近，既可以使用dfs、bfs，也可以使用UnionFind，具体思路看代码就能懂。
代码如下：
class Solution {
private:
vector<vector<int>> edges;
vector<int> used;
public:
void dfs(int u) {
used[u] = true;
for (int v: edges[u]) {
if (!used[v]) {
dfs(v);
}
}
}
int makeConnected(int n, vector<vector<int>>& connections) {
if (connections.size() < n - 1) {
return -1;
}
edges.resize(n);
for (const auto& conn: connections) {
edges[conn[0]].push_back(conn[1]);
edges[conn[1]].push_back(conn[0]);
}
used.resize(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i);
++ans;
}
}
return ans - 1;
}
};
//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/solution/lian-tong-wang-luo-de-cao-zuo-ci-shu-by-leetcode-s/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路差距
思路差距就是图、查找方面的知识，需要多接触一些类似的题目，有关“集合”、“合并”等结点之间粗略包含关系的，往往可以使用并查集进行解答，对于并查集还可以进行“路径压缩”的优化；而对于需要更精细的结点间遍历的操作，就需要深度优先搜索和广度优先搜索，后续的博客会再更新一期关于最短单源路径、最小生成树、拓扑排序等内容的一期博客，请继续关注。
内容总结
以上是互联网集市为您收集整理的leetcode常规算法题复盘（第十五期）——除法求值&省份数量&由斜杠划分区域&连通网络的操作次数全部内容，希望文章能够帮你解决leetcode常规算法题复盘（第十五期）——除法求值&省份数量&由斜杠划分区域&连通网络的操作次数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。