米哈游3/19前端笔试

过了全部用例，是并查集。求第三道'mhy'字符串的解法。

class Uf {
  constructor(n) {
    this.pre = new Array(n).fill().map((val, key) => key);
  }
  find(x) {
    if (x != this.pre[x]) {
      return (this.pre[x] = this.find(this.pre[x]));
    }
    return this.pre[x];
  }
  union(x, y) {
    let [xroot, yroot] = [this.find(x), this.find(y)];
    if (xroot == yroot) return;
    this.pre[xroot] = yroot;
  }
}
function mysol(n, m, arr) {
  let uf1 = new Uf(n * m); //正常人视角
  let uf2 = new Uf(n * m); //色盲视角
  let color, curid, leftid, topid;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      color = arr[i][j];
      curid = i * m + j;
      //正常人视角
      if (i - 1 >= 0 && arr[i - 1][j] == color) {
        //上边的那一个
        topid = (i - 1) * m + j;
        uf1.union(curid, topid);
      }
      if (j - 1 >= 0 && arr[i][j - 1] == color) {
        //左边那一个
        leftid = i * m + j - 1;
        uf1.union(curid, leftid);
      }

      //色盲视角
      if (color == "G" || color == "B") {
        //蓝绿
        if (i - 1 >= 0 && (arr[i - 1][j] == "G" || arr[i - 1][j] == "B")) {
          //上边的那一个
          topid = (i - 1) * m + j;
          uf2.union(curid, topid);
        }
        if (j - 1 >= 0 && (arr[i][j - 1] == "G" || arr[i][j - 1] == "B")) {
          //左边那一个
          leftid = i * m + j - 1;
          uf2.union(curid, leftid);
        }
      } else {
        //红色
        if (i - 1 >= 0 && arr[i - 1][j] == color) {
          //上边的那一个
          topid = (i - 1) * m + j;
          uf2.union(curid, topid);
        }
        if (j - 1 >= 0 && arr[i][j - 1] == color) {
          //左边那一个
          leftid = i * m + j - 1;
          uf2.union(curid, leftid);
        }
      }
    }
  }
  let count1 = 0,
    count2 = 0;
  for (let id = 0; id < uf1.size.length; id++) {
    if (uf1.find(id) == id) {
      count1 += 1; 
    }
    if (uf2.find(id) == id) {
      count2 -= 1;
    }
  }
  return count1 + count2;
}
// mysol(2, 6, [
//   ["R", "R", "G", "G", "B", "B"],
//   ["R", "G", "B", "G", "R", "R"],
// ]);
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // Write your code here
  let line = await readline();
  let [n, m] = line.split(" ").map((val) => parseInt(val));
  let arr = [];
  for (var i = 0; i < n; i++) {
    lines = (await readline()).split("");
    arr.push(lines);
  }
  mysol(n, m, arr);
})();

第三道题过了40的解法

利用map计数，计算前后 m h y 的 净操作次数，比对三者净操作次数是否相同。

经大家提醒，这种解法缺少了对删除掉所有‘m' 'h' 'y'后的两字符串比较，所以没全过。

function mysol(n, arr) {
  let before = "",
    after = "";
  for (let i = 0; i < arr.length; i += 2) {
    before = arr[i];
    after = arr[i + 1];
    if (before.length == after.length && before != after) {
      console.log("No");
    } else if (before == after) {
      console.log("Yes");
    } else console.log(diff(before, after) ? "Yes" : "No");
  }
}
function diff(str1, str2) {
  let map = new Map();
  for (let c of str1) {
    map.set(c, (map.get(c) || 0) + 1);
  }
  for (let c of str2) {
    map.set(c, (map.get(c) || 0) - 1);
  }
  let [m, h, y] = [map.get("m") || 0, map.get("h") || 0, map.get("y") || 0];
  return m == h && h == y;
}
let n = 3,
  arr = ["mhbdy", "bd", "mhbdy", "mhmbhdyy", "mhy", "abc"];

mysol(n, arr);