等式方程的可满足性

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，990.Satisfiability of Equality Equations

先看题目描述

题目大意是给定一个由表示变量之间关系的字符串方程组成的数组，判断有没有办法分配变量使得同时满足这些方程

算法和思路

一开始想的是用字符数组存储相等的变量，例如输入 [“a==b”, “b==e”,”c==d”，”d==a”, “a!=c”] 时，预想的流程是先创立一个空的字符数组，然后把 a、b 添加到数组中，便得到一个 [a, b]，然后又有 b==e，则把 e 添加到 [a, b]中得到 [a, b, e]，又有 c==d 则则得到 [a, b, e] 和 [c, d]，又有 c==d 则将 [c, d] 连接到 [a, b, e] 后得到 [a, b, e, c, d]，再遍历 != 符号，发现 a、c 在同一数组中，则返回 false。预想的是这样一个流程，但在实际操作时发现极为麻烦，且无法控制创建数组的数量，这个实现的方法并不可行。之后去看题目标签，发现有个并查集，于是又去搜索并查集的相关算法，思路才真正形成，看的文章是这篇，一个非常实用而且精妙的算法-并查集（java语言实现）

基于这样的想法这道题使用了并查集

算法流程

  • 遍历所有 == 符号的字符串，将符号两边字母所属集合合并

  • 遍历所有 != 符号的字符串，若两边字母属于相同集合，则返回 false，若均属于不同集合，则返回 true

算法的实现关键点就在于如何将两个字母所属集合合并以及如何判断是否属于同一集合，这涉及到并查集的两个主要操作：合并与查找

我定义了一个长度为 26 的 s 数组，分别记录 26 个小写字母的上级，例如 s[0] 就表示字母 a 的上级，当 s[0] = 0 时，就表示字母 a 是这个集合的根节点，当 s[0] = 1 时，就表示字母 a 的上级是 b，还没开始遍历时所有字母的上级都是自身。

想要判断某个字母属于哪个集合，判断它的根节点即可，通过递归一层层的寻找该字母的上级直到 s[i] = i，则找到了其根节点，并将 i 返回，代码如下，为了节省查找根节点时间，每次调用查找操作都会对子节点调整，使其上级为根节点

1
2
3
4
5
6
public int find(int num) {
        if (s[num] == num) return num;
        else {
            return s[num] = find(s[num]);
        }
    }

要将两字母所属集合合并，使用合并操作即可，合并操作需先找出两个字母所属集合的根节点，然后使其中一个根节点的上级为另一个根节点即可，代码如下

1
2
3
public void union (int a, int b) {
        s[find(b)] = s[find(a)];
    }

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

class Solution {
    int[] s = new int[26];

    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < s.length; i++) s[i] = i;
        for (String equation: equations) {
            if (equation.charAt(1) == '=') {
                union(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
            }
        }
        for (String equation: equations) {
            if (equation.charAt(1) == '!') {
                if (find(equation.charAt(0) - 'a') == find(equation.charAt(3) - 'a')) return false;
            }
        }
        return true;
    }

    public int find(int num) {
        if (s[num] == num) return num;
        else {
            return s[num] = find(s[num]);
        }
    }

    public void union (int a, int b) {
        s[find(b)] = s[find(a)];
    }
}