990.等式方程的可满足性

链接：990.等式方程的可满足性
难度：Medium
标签：并查集、图、数组、字符串
简介：给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或  "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回  true，否则返回 false。

题解 1 - typescript

• 编辑时间：2020-05-06
• 执行用时：120ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：相同的值用一个对象储存，不同的值用另一个对象去储存。

function equationsPossible(equations: string[]): boolean {
  const map = new Map<string, { eq: Set<string>; neq: Set<string> }>();
  for (const equation of new Set(equations)) {
    const c1 = equation[0];
    const c2 = equation[3];
    const isEqual = equation[1] === '=';
    if (c1 === c2) {
      if (!isEqual) return false;
      else continue;
    }
    const e1 = map.get(c1);
    const e2 = map.get(c2);
    if (e1 === undefined && e2 === undefined) {
      if (isEqual) {
        const obj = {
          eq: new Set<string>([c1, c2]),
          neq: new Set<string>(),
        };
        map.set(c1, obj);
        map.set(c2, obj);
      } else {
        map.set(c1, { eq: new Set<string>([c1]), neq: new Set<string>([c2]) });
        map.set(c2, { eq: new Set<string>([c2]), neq: new Set<string>([c1]) });
      }
    } else if (e1 !== undefined && e2 === undefined) {
      if (isEqual) {
        e1.eq.add(c2);
        map.set(c2, e1);
        for (let c of e1.neq) map.get(c)?.neq.add(c2);
      } else {
        e1.neq.add(c2);
        map.set(c2, {
          eq: new Set<string>([c2]),
          neq: new Set<string>([c1, ...e1.eq]),
        });
      }
    } else if (e1 === undefined && e2 !== undefined) {
      if (isEqual) {
        e2.eq.add(c1);
        map.set(c1, e2);
        for (let c of e2.neq) map.get(c)?.neq.add(c1);
      } else {
        e2.neq.add(c1);
        map.set(c1, {
          eq: new Set<string>([c1]),
          neq: new Set<string>([c2, ...e2.eq]),
        });
      }
    } else if (e1 !== undefined && e2 !== undefined) {
      if (isEqual) {
        if (e1.neq.has(c2)) return false;
        for (const c of e2.eq) {
          e1.eq.add(c);
          map.set(c, e1);
        }
        for (const c of e2.neq) e1.neq.add(c);
        for (const c of e1.neq) for (const eq of e1.eq) map.get(c)?.neq.add(eq);
      } else {
        if (e1.eq.has(c2)) return false;
        for (const c of e2.eq) e1.neq.add(c);
        for (const c of e1.eq) e2.neq.add(c);
      }
    }
  }
  return true;
}

题解 2 - typescript

• 编辑时间：2021-04-30
• 执行用时：108ms
• 内存消耗：41.8MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function equationsPossible(equations: string[]): boolean {
  equations.sort((a, b) => {
    if (a[1] === '=') return -1;
    return 1;
  });
  const uf = new UnionFind(26);
  const toNum = (char: string) => char.codePointAt(0)! - 'a'.codePointAt(0)!;
  for (const equation of equations) {
    const num1 = toNum(equation[0]);
    const num2 = toNum(equation[3]);
    const same = equation[1] === '=';
    if (same) uf.union(num1, num2);
    else if (uf.same(num1, num2)) return false;
  }
  return true;
}