【当前排名42710】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/submissions/597896241/
秒了

const findMin = (arr, target) => {
  let left = 0,
    right = arr.length - 1;
  let ans = -1;
  while (left <= right) {
    const mid = Math.floor((right + left) / 2);
    const char = arr[mid];
    if (char < target) {
      left = mid + 1;
      ans = mid;
    } else {
      right = mid - 1;
    }
  }
  return ans;
};
const findMax = (arr, target) => {
  let left = 0,
    right = arr.length - 1;
  let ans = -1;
  while (left <= right) {
    const mid = Math.floor((right + left) / 2);
    const char = arr[mid];
    if (char <= target) {
      left = mid + 1;
    } else {
      right = mid - 1;
      ans = mid;
    }
  }
  return ans;
};
var findTheDistanceValue = function (arr1, arr2, d) {
  arr2=arr2.sort((a,b)=>a-b)
  let ans=0;
for (let index = 0; index < arr1.length; index++) {
  const num = arr1[index];
  const min = findMin(arr2, num);
  const max = findMax(arr2, num);
  const sep = Math.min(num - (arr2[min]??num-d-1), (arr2[max]??num+d+1) - num,Math.abs( (arr2[max-1]??num+d+1) - num));
  if(sep>d){
      ans++
  }
}
return ans
};

李恒道

https://leetcode.cn/problems/find-if-path-exists-in-graph/submissions/598303765/
过

var validPath = function (n, edges, source, destination) {
  const arr = new Array(n).fill(0).map(() => []);
  const visit = new Array(n).fill(false);
  for (const [a, b] of edges) {
    arr[a].push(b);
    arr[b].push(a);
  }
  const dfs = (pos) => {
    if(pos==destination){
        return true
    }
    if (visit[pos]) {
      return false;
    }
    visit[pos] = true;
    let ans = false;
    for (let index = 0; index < arr[pos].length && ans == false; index++) {
      const item = arr[pos][index];
      ans = dfs(item);
    }
    return ans;
  };
  const ans=dfs(source)
  return ans
};

李恒道

https://leetcode.cn/problems/all-paths-from-source-to-target/submissions/598307446/
过

var allPathsSourceTarget = function (graph) {

  const ans = [];
  const dfs = (pos, arr) => {
    arr.push(pos);
    if (pos == graph.length - 1) {
      ans.push([...arr]);
      arr.pop();
      return;
    }
    for (let index = 0; index < graph[pos].length ; index++) {
      const item = graph[pos][index];
      dfs(item,arr);
    }
    arr.pop();
    return;
  };
  dfs(0, []);
  return ans;
};

李恒道

https://leetcode.cn/problems/keys-and-rooms/submissions/598309416/
过`

var canVisitAllRooms = function (rooms) {
  const n = rooms.length;
  const visit = new Array(n).fill(false);
  let all=0;
  const dfs = (pos) => {
    if (visit[pos]) {
      return false;
    }
    visit[pos] = true;
    all++
    for (let index = 0; index < rooms[pos].length; index++) {
      const item = rooms[pos][index];
      dfs(item);
    }
  };
   dfs(0);
  return rooms.length==all;
};

李恒道

https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/submissions/598323095/
过了

var countPairs = function (n, edges) {
  const arr = new Array(n).fill(0).map(() => []);
  const visit = new Array(n).fill(false);
  for (const [a, b] of edges) {
    arr[a].push(b);
    arr[b].push(a);
  }
  const dfs = (pos, sum) => {
    if (visit[pos]) {
      return 0;
    }
    visit[pos] = true;
    sum = 1;
    for (let index = 0; index < arr[pos].length; index++) {
      const item = arr[pos][index];
      sum += dfs(item, sum);
    }
    return sum;
  };
  const list = [];
  let ret = 0;
  let sum = 0;
  for (let index = 0; index < n; index++) {
    const ans = dfs(index);
    if (ans !== 0) {
      list.push(ans);
      if (list.length != 1) {
        ret+=ans*sum
      }
      sum += ans;
    }
  }

  return ret
};

李恒道

https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/submissions/598406384/
打测例硬凹过去了

var minScore = function (n, roads) {
  n = n + 1;
  const arr = new Array(n).fill(0).map(() => []);
  for (const [a, b, c] of roads) {
    arr[a].push([b, c]);
    arr[b].push([a, c]);
  }
  const dfs = (pos, sum, visit) => {

    if (visit[pos] !== -1) {
      visit[pos] = Math.min(visit[pos], sum);
      return visit[pos];
    }
    let ans = sum;
    visit[pos]=sum
    for (let index = 0; index < arr[pos].length; index++) {
      const [target, value] = arr[pos][index];
      ans = Math.min(ans, dfs(target, Math.min(sum, value), visit));
    }
    visit[pos] = ans;
    return ans;
  };
  return dfs(1, Number.MAX_SAFE_INTEGER, new Array(n).fill(-1));
};