练习

推荐练习

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。

示例 1:

输入:["a==b","b!=a"]
输出:false
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2:

输出:[“b==a",”a!=b"]
输入:true
解释:我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

提示:

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '=',要么是 '!'
equations[i][2] 是 '='

方法

设计思路

我们可以将每一个变量看作图中的一个节点,把相等的关系 == 看作是连接两个节点的边,那么由于表示相等关系的等式方程具有传递性,即如果 a==b 和 b==c 成立,则 a==c 也成立。也就是说,所有相等的变量属于同一个连通分量。因此,我们可以使用并查集来维护这种连通分量的关系。

首先遍历所有的等式,构造并查集。同一个等式中的两个变量属于同一个连通分量,因此将两个变量进行合并。

然后遍历所有的不等式。同一个不等式中的两个变量不能属于同一个连通分量,因此对两个变量分别查找其所在的连通分量,如果两个变量在同一个连通分量中,则产生矛盾,返回 false。

如果遍历完所有的不等式没有发现矛盾,则返回 true。

具体实现方面,使用一个数组 parent 存储每个变量的连通分量信息,其中的每个元素表示当前变量所在的连通分量的父节点信息,如果父节点是自身,说明该变量为所在的连通分量的根节点。一开始所有变量的父节点都是它们自身。对于合并操作,我们将第一个变量的根节点的父节点指向第二个变量的根节点;对于查找操作,我们沿着当前变量的父节点一路向上查找,直到找到根节点。(路径压缩)

class UnionFind {
private:
    vector<int> parent;

public:
    UnionFind() {
        parent.resize(26);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int index) {
        if (index == parent[index]) {
            return index;
        }
        parent[index] = find(parent[index]);
        return parent[index];
    }

    void unite(int index1, int index2) {
        parent[find(index1)] = find(index2);
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf;
        for (const string& str: equations) {
            if (str[1] == '=') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                uf.unite(index1, index2);
            }
        }
        for (const string& str: equations) {
            if (str[1] == '!') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                if (uf.find(index1) == uf.find(index2)) {
                    return false;
                }
            }
        }
        return true;
    }
};

复杂度分析

C++提示:

C++中iota是用来批量递增赋值vector的元素

#include<iostream>
#include<numeric>       //iota头文件
using namespace std;
void func()
{
    vector<int> v(10);
    iota(v.begin(),v.end(),1);
    vector<int>::iterator it = v.begin();
    while(it != v.end())
    {
        cout<<*it++<<" ";
    }
}

结果:
1 2 3 4 5 6 7 8 9 10

最后修改:2020 年 07 月 13 日 07 : 28 PM
如果觉得我的文章对你有用,请随意赞赏