# [LeetCode 990] 等式方程的可满足性——TypeScript并查集实现

总的来说,思路还是很清晰的。

一看到这个题就想到了图,==构成的是连通关系,只要有连通关系,就可以构造图来解决问题。而解决图的问题,比较常见的思路的就是BFS(或者DFS)和并查集,这个题感觉用BFS和BFS有点麻烦,那就用并查集了:

function equationsPossible(equations: string[]): boolean {
  const parent: number[] = [];
  for (let i = 0; i < 26; ++i) {
    parent.push(i);
  }

  function find(i: number) {
    while (i !== parent[i]) {
      i = parent[i];
    }
    return i;
  }

  function union(a: number, b: number) {
    parent[find(a)] = find(b);
  }

  for (const equation of equations) {
    if (equation[1] === "=") {
      let leftId = equation[0].charCodeAt(0) - 0x61,
        rightId = equation[3].charCodeAt(0) - 0x61;
      union(leftId, rightId);
    }
  }
  for (const equation of equations) {
    if (equation[1] === "!") {
      let leftId = equation[0].charCodeAt(0) - 0x61,
        rightId = equation[3].charCodeAt(0) - 0x61;
      if (find(leftId) === find(rightId)) {
        return false;
      }
    }
  }
  return true;
}

可能有几个地方需要注意:

  1. 相对来说,因为ts / js的语言特性,可以嵌套函数,所以在使用“全局变量”(比如这里的parent数组)的时候会比较优雅一点。但是因为这语言里没有字符类型,所以在处理这种涉及字符的问题就比较麻烦,需要去调用charCodeAt方法去获取对应的ASCII码值,然后再进行数值运算。

  2. 为什么用更安全的codePointAt方法,而是选择了不那么安全的charCodeAt?因为题目里说了是小写英文字母,不需要考虑超过\uFFFF的字符。

  3. 为什么不用字符串来做并查集,而是用数字?用字符串来做就得用Map(或者对象),因为需要维护一个字符串到字符串的映射关系。而且用Map或者对象之后还要考虑类型上可能的undefined(虽然实际上并不会发生),写起来有点麻烦。

    当然运行起来好像是字符串快一点(因为可以减少每次转换成数字的运算量),而且对调用者比较友好(如果是一个封装好的并查集)。在最后会放两个用字符串的实现,一个是Map,一个是对象。对象的实现是最优雅的,但性能最差。

    总的来说,就我这里的实际运行结果来看,Map > 数字 > 对象。

  4. 关于find的实现,事实上这么写也是可以的:

    function find(i: number) {
      while (i !== parent[i]) {
        i = parent[i];
      }
      return i;
    }
    

    但是现在的实现可以减少循环次数,一定程度上可以提高性能。关于减少循环次数可能能够提高性能,可以参考“达夫设备(Duff's device)”;当然这个与具体的运行环境有关。

  5. 减少==的使用可以避免可能的类型转换,提高性能。

# 附录

# Map实现

function equationsPossible(equations: string[]): boolean {
  const parent = new Map<string, string>();
  for (let i = 0; i < 26; ++i) {
    const s = String.fromCharCode(0x61 + i);
    parent.set(s, s);
  }

  function find(i: string) {
    while (i !== parent.get(i)) {
      parent.set(i, parent.get(parent.get(i)!)!);
      i = parent.get(i)!;
    }
    return i;
  }

  function union(a: string, b: string) {
    parent.set(find(a), find(b));
  }

  for (const equation of equations) {
    if (equation[1] === "=") {
      union(equation[0], equation[3]);
    }
  }
  for (const equation of equations) {
    if (equation[1] === "!") {
      if (find(equation[0]) === find(equation[3])) {
        return false;
      }
    }
  }
  return true;
}

# 对象实现

interface Parent {
  [key: string]: string;
}

function equationsPossible(equations: string[]): boolean {
  const parent: Parent = {};
  for (let i = 0; i < 26; ++i) {
    const s = String.fromCharCode(0x61 + i);
    parent[s] = s;
  }

  function find(i: string) {
    while (i !== parent[i]) {
      parent[i] = parent[parent[i]];
      i = parent[i];
    }
    return i;
  }

  function union(a: string, b: string) {
    parent[find(a)] = find(b);
  }

  for (const equation of equations) {
    if (equation[1] === "=") {
      union(equation[0], equation[3]);
    }
  }
  for (const equation of equations) {
    if (equation[1] === "!") {
      if (find(equation[0]) === find(equation[3])) {
        return false;
      }
    }
  }
  return true;
}
最后更新于: 6/25/2020, 2:10:06 PM