990. 等式方程的可满足性

[crawler-django]

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

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

原题地址: https://leetcode-cn.com/problems/satisfiability-of-equality-equations/

问题:

1. 当时做这个题的时候, 有一个思路就是:

   把互相相等的都放同一个数组里, 比较就在数组查询有没有这两个值, 没有就属于!=, 有就属于=. 这样的思路思考下去感觉还挺清晰, 好像挺可靠的.

   但是在实现的过程中, 发现并不那么容易, 因为当(a == b, f == e, e == b)的时候, a,b 在同一个数组; f,e在同一个数组; 查询e, b然后合并数组. (如果数值更多, 且互相没有联系, 就能到达n个数组, 那么进行查询将是一个非常大的耗时).

   那么该怎么实现一下子就能知道它的所属集合的方法呢? 这时就有了一个思路, 像树那样的一个根节点, 根节点相同就意味着所属集合为同一个. 但这又涉及到两个树合并的问题, 像 (a == b, f == e, e == b)这样的, �就会涉及到"并查集".

   (并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题).

   诶? 好像有点复杂啊... 看题解那些并查集的写法 都不能满足我心中所愿, 原因是每次查询比较的时候, 都要递归找到那个根节点进行比较.

   这就像问一个公司的基层员工 公司ceo是谁, 他不知道, 只能问他的上司, 他的上司可能也不知道, 只能再问上司...(等等, 以此类推, 层数越高就越复杂了. 当然了, 有些算法可以对这些层级进行不断的优化.)

   但是我想一步到位, 什么意思呢? 就像在咱们中国, 刚出生就赋予了中国人的称号. 其他国家的人(甚至一个国家)想要变成中国的一员, 那么直接改头换面, 并入中国就是了. 以后那个国家的人也都是中国人了.. �

   嗯? 有人可能就会说: "emmmmmm, 你说的...., 你在说屁话?".

   当然了.. 现实是不可能的事. 但是, 在代码里, 一切由我们掌控. 我们可以就让它那么简单 ---> "浅拷贝".

   如(a == b, f == e , e == b), 用浅拷贝创建a, 把a的值赋予b, b一改则全改, 同理f和e也是一样. e当话事人, 不需直接并入b的集合里, 直接改头换面把它的值改为b的值就行了. 话事人都说话了, f这个附属在e后面的人还敢不听吗?

废话不多说了, 直接上代码吧.

---

**代码**:

var equationsPossible = function(equations) {

    let obj = {}

    for (let i = 0; i < equations.length; i += 1) {
        let equation = equations[i]

        let oneLetter = equation[0]
        let otherLetter = equation[3]

        // 精神分裂患者, 自己不承认自己. 直接false
        if (oneLetter === otherLetter) {
            if (equation[1] === '!') {
                return false
            }
        }

        if (equation[1] === '=') {

            if (!obj[oneLetter] && !obj[otherLetter]) {
                // 两个字母都没有记录时
                obj[oneLetter] = {
                    parent: oneLetter
                }
                obj[otherLetter] = obj[oneLetter]
            } else if (obj[oneLetter] && obj[otherLetter]) {
                // 两个字母都有被记录时
                obj[otherLetter].parent = obj[oneLetter].parent
            } else {
                // 只有其中一个字母
                if (obj[oneLetter]) {
                    // 第一个字母有记录
                    obj[otherLetter] = obj[oneLetter]
                } else {
                    // 第二个字母有记录
                    obj[oneLetter] = obj[otherLetter]
                }
            }
            
        }
    }

    // 进行判断
    for (let j = 0; j < equations.length; j += 1) {
        let notEquation = equations[j]

        let oneLetter = notEquation[0]
        let otherLetter = notEquation[3]

        if (notEquation[1] === '!') {
            if (obj[oneLetter] && obj[otherLetter]) {
                if (obj[oneLetter].parent === obj[otherLetter].parent) {
                    return false
                }
            }
            
        }
    }

    return true
};

运行结果: