leeguoo 的个人博客 leeguoo 的个人博客

If you stay positive, you have a shot at a silver lining.

目录
每日一题:等方程式的可满足性
/    

每日一题:等方程式的可满足性

990. 等式方程的可满足性

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

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

示例 1:

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

示例 2:

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

示例 3:

输入:["a==b","b==c","a==c"]
输出:true

示例 4:

输入:["a==b","b!=c","c==a"]
输出:false

示例 5:

输入:["c==c","b==d","x!=z"]
输出:true

提示:

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

首次尝试

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function(equations) {
    const equationList = [];
    const unEquationList = [];
    let result = true;
    equations.forEach(equation =>{
        const params1 = equation.split("=="), params2 = equation.split("!=");
        if(params1.length == 2 ){
            const param1 = params1[0], param2 = params1[1];
             equationList.push(new Set([param1,param2]));
        }else{
            unEquationList.push([params2[0],params2[1]]);
        }
    })
    if(equationList.length === 0)equationList.push(new Set())
    else{
        // 交集合并
        for(let i = 0; i < equationList.length - 1; i++){
            for(let j = i + 1; j < equationList.length; j++){
                let exist = false;
                equationList[i].forEach(v => {
                    if(equationList[j].has(v)){
                        exist = true;
                    }
                })
                if(exist){
                    equationList[i].forEach(v => {
                        equationList[j].add(v);
                    })
                    equationList[i] = new Set();
                }
            }
        }
    }
    equationList.forEach(eqSet => {
        unEquationList.forEach(unEqList => {
            if(eqSet.has(unEqList[0]) && eqSet.has(unEqList[1]))result = false;
            if(unEqList[0] === unEqList[1]) result = false;
        })
    })
    return result;
};

优化解法

// @TODO 两点半了 明日优化

标题:每日一题:等方程式的可满足性
作者:leeguooooo
地址:https://leeguoo.com/articles/2020/06/08/1591554307135.html