手写算法: 可能的二分法

886. 可能的二分法

思路

• 理解题意：编号从 1 开始，分成两组，并且不喜欢的人不能在一组， dislikes = [ai, bi]，那么 ai 和 bi 可以看作是两个阵营的，用两个颜色来表示，就是非黑即白！水火不容

• 按照以上的说话，那么可以形成二分图（其实不太明白图的结构）

• 根据二维数组，先做出每个人对应不喜欢的人的图，根据生成的图，再去遍历每个节点

• 用 visited 记录走过的节点，不然会死循环

• 用 colored 记录染色，自己与不喜欢的人需要是不同颜色，如果颜色相同，则表示二分法不成立

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(n, dislikes) {
  // 默认它是一个二分法
  let isDichotomy = true;
  // 记录访问过的人
  let visited = new Array(n + 1).fill(false);
  // 染色，自己与不喜欢的人颜色相反
  let colored = new Array(n + 1).fill(false);

  // 生成图
  const buildGraph = (n, dislikes) => {
    // 创建一个二维码数组，以编号为下标，将不喜欢的人都归类
    let graph = new Array(n + 1).fill(0).map(() => []);
    for (const edge of dislikes) {
      const [self, other] = edge;
      graph[self].push(other);
      graph[other].push(self);
    }
    return graph;
  };

  // 遍历每个节点
  const traverse = (graph, self) => {
    if (!isDichotomy) return;
    // 标记访问过
    visited[self] = true;

    for (const other of graph[self]) {
      // 如果已经访问过，那么就要判断自己与不喜欢的人是否同一个颜色
      if (visited[other]) {
        // 是同一个颜色的话，那么就不是二分法
        if (colored[self] === colored[other]) {
          isDichotomy = false;
          // 不是二分法直接跳出循环
          break;
        }
        // 为了跑完所有节点
        continue;
      }

      // 没有访问过，那么就要进行染色操作; 自己与不喜欢的人要是不同阵营，即不同颜色
      colored[other] = !colored[self];
      // 顺着节点走，继续遍历
      traverse(graph, other);
    }
  };

  // 按编号生成对应不喜欢的人
  const graph = buildGraph(n, dislikes);

  // 逐个遍历，若是已访问过，直接跳过
  for (let i = 1; i <= n; i++) {
    if (!isDichotomy) return isDichotomy;
    // 如果没访问过，就去遍历节点
    if (!visited[i]) {
      traverse(graph, i);
    }
  }
  return isDichotomy;
};

手写题: 请使用你熟悉的语言或技术或框架实现一个 autocomplete 组件

附上项目的 git 地址 里面有 autocomplete 组件的代码，简略写了一下