CodeKata Bus Routes

10077 ワード
leetcode algorithm JavaScript codekata テキストリンク

質問リンク


Bus Routes - LeetCode

問題を解く


問題はバスですが、地下鉄で考えて解決しました.routesは2 D配列、1 Dインデックスは円弧、各配列の要素はドメインの名前です.mapにより、各局がどの弧に含まれているか、始局の弧をqに入れるとともに、各弧が何回乗り換えたかをチェックするdist度の初期値を入れる.
BFSはqから出る要素が弧なので、繰り返しゲートを通ってその弧の駅をずっと回り、target駅ならreturnです.そして各局を経て、その局がどの線に含まれているかを決定した後、distの値を比較することによって、その局が別の線に含まれているか否かを決定する.

マイコード

var numBusesToDestination = function (routes, source, target) {
  if (source === target) return 0;
  const map = new Map();
  const dist = new Map();
  const q = [];
  for (let i = 0; i < routes.length; ++i)
    for (let j = 0; j < routes[i].length; ++j) {
      const tmp = map.get(routes[i][j]) || [];
      tmp.push(i);
      map.set(routes[i][j], tmp);
      if (routes[i][j] === source) {
        dist.set(i, 1);
        q.push(i);
      }
    }
  while (q.length) {
    const lane = q.shift();
    const val = dist.get(lane);
    for (let i = 0; i < routes[lane].length; ++i) {
      if (routes[lane][i] === target) return val;
      const otherLanes = map.get(routes[lane][i]);
      for (let j = 0; j < otherLanes.length; ++j) {
        const nextDist = dist.get(otherLanes[j]);
        if (nextDist === undefined || nextDist > val + 1) {
          q.push(otherLanes[j]);
          dist.set(otherLanes[j], val + 1);
        }
      }
    }
  }
  return -1;
};
[プログラマー]私はレベル1のような数字が好きではありません.
矢印関数を怖がっている開発者のためのIntersection Observer