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

李恒道

https://leetcode.cn/problems/maximum-sum-circular-subarray/submissions/595064777/?envType=study-plan-v2&envId=top-interview-150
没凹出来
第一个想出来的简直是天才
我满脑子模拟

var maxSubarraySumCircular = function (nums) {
  let pre = 0,
    maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(pre + x, x);
    maxAns = Math.max(maxAns, pre);
  });
  pre = 0;
  minAns = nums[0];
  let total = 0;
  nums.forEach((x) => {
    pre = Math.min(pre + x, x);
    minAns = Math.min(minAns, pre);
    total += x;
  });
  if (total == minAns) {
    return maxAns;
  }

  return Math.max(maxAns, total - minAns);
};

李恒道

https://leetcode.cn/problems/evaluate-division/submissions/595066170/?envType=study-plan-v2&envId=top-interview-150
复杂除法
这题真的思路很爽

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @Return {number[]}
 */
var calcEquation = function (equations, values, queries) {
  const map = new Map();
  for (let index = 0; index < equations.length; index++) {
    const [n1, n2] = equations[index];
    const value = values[index];
    if (!map.has(n1)) {
      map.set(n1, new Map());
    }
    if (!map.has(n2)) {
      map.set(n2, new Map());
    }
    const n1Map = map.get(n1);
    const n2Map = map.get(n2);
    n1Map.set(n2, value);
    n2Map.set(n1, 1 / value);
  }
  const dfs = (start, end, visit) => {
    const temp = map.get(start);
    if (temp == undefined) {
      return -1;
    }
    if (map.get(end) == undefined) {
      return -1;
    }
    if (start == end) {
      return 1;
    }
    visit.set(start,true)
    for (let data of temp) {
      if (visit.has(data[0])) {
        continue;
      }
      const value = data[1];
      const nextValue = dfs(data[0], end, visit);
      if (nextValue == -1) {
        continue;
      }
      return value * nextValue;
    }
    return -1;
  };
  let ans = [];
  for (const [query0, query1] of queries) {
    ans.push(dfs(query0, query1, new Map()));
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/redundant-connection/submissions/595237637/
并查集
秒了！

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, index) => index);
    this.rank = new Array(n).fill(1);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }

  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}

/**
 * @param {number[][]} edges
 * @Return {number[]}
 */
var findRedundantConnection = function (edges) {
  const union = new UnionFind(edges.length);
  for (let index = 0; index < edges.length; index++) {
    const edge = edges[index];
    if(union.isConnected(edge[0],edge[1])){
      //已经是一个了
      return edge
    }else{
      union.union(edge[0],edge[1])
    }
  }
  return -1
};

李恒道

https://leetcode.cn/problems/minimum-money-required-before-transactions/description/
这题不喜欢
贪心 贪不出来是真难受

var minimumMoney = function (transactions) {
  let totalLostt = 0,
    mx = 0;
  for (const transaction of transactions) {
    totalLostt += Math.max(transaction[0] - transaction[1], 0);
    mx = Math.max(mx, Math.min(transaction[0], transaction[1]));
  }
  return totalLostt + mx;
};

李恒道

https://leetcode.cn/problems/number-of-operations-to-make-network-connected/submissions/595242423/
爽了

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, index) => index);
    this.rank = new Array(n).fill(1);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }

  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}

/**
 * @param {number[][]} edges
 * @Return {number[]}
 */
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function (n, connections) {
  if (connections.length < n - 1) {
    return -1;
  }
  let ans = 0;
  let ok = 0;
  const union = new UnionFind(n);
  for (const connection of connections) {
    if (union.isConnected(connection[0], connection[1])) {
      ans++;
    } else {
      ok++;
      union.union(connection[0], connection[1]);
    }
  }
  return Math.min(ans, n - 1 - ok);
};

李恒道

https://leetcode.cn/problems/combination-sum-ii/description/?envType=daily-question&envId=2025-01-26
打卡题

var combinationSum2 = function (candidates, target) {
  const map = new Map();
  for (let index = 0; index < candidates.length; index++) {
    const candidate = candidates[index];
    map.set(candidate, (map.get(candidate) ?? 0) + 1);
  }
  candidates = [...map.keys()];
  candidates.sort((a, b) => a - b);
  const ans = [];
  const dfs = (pos, val, arr) => {
    if (val > target) {
      return;
    }
    if (val == target) {
      ans.push([...arr]);
      return;
    }
    if (pos >= candidates.length) {
      return;
    }

    dfs(pos + 1, val, arr);
    let maxCount = map.get(candidates[pos]);
    const newArr = [...arr];
    for (let index = 1; index <= maxCount; index++) {
      newArr.push(candidates[pos]);
      dfs(pos + 1, val + candidates[pos] * index, newArr);
    }
  };
  dfs(0, 0, []);
  return ans;
};

李恒道

https://leetcode.cn/problems/snakes-and-ladders/submissions/595568804/?envType=study-plan-v2&envId=top-interview-150
这题边界真是给我干蒙了

var snakesAndLadders = function (board) {
  const n = board.length;
  const stack = [1];
  const getPos = (index) => {
    const x = n - 1 - Math.floor((index - 1) / n);
    let isReverse = x % 2 == 0 ? true : false;
    if (n % 2 != 0) {
      isReverse = !isReverse;
    }
    const originY = (index - 1) % n;
    const y = isReverse ? n - 1 - originY : originY;
    return [x, y];
  };
  const cache = new Map();
  cache.set(1, 0);
  while (stack.length !== 0) {
    const index = stack.shift();
    for (let next = index + 1; next <= Math.min(index + 6, n * n); next++) {
      const [x, y] = getPos(next);
      let nextIndex = next;
      if (board[x][y] !== -1) {
        nextIndex = board[x][y];
      }
      if (cache.has(nextIndex)) {
        continue;
      }
      cache.set(nextIndex, cache.get(index) + 1);
      stack.push(nextIndex);
    }
  }
  const min = cache.get(n * n);
  return min == undefined ? -1 : min;
};

李恒道

https://leetcode.cn/problems/jump-game-ii/
这两天都是这种题

var jump = function (nums) {
    if(nums.length==1){
        return 0
    }
  let right = nums[0];
  let pos = 0;
  let times = 1;
  let nextRight = nums[0];
  while (pos <= right && right < nums.length - 1) {
    for (let index = pos; index < right; index++) {
      const num = nums[index];
      nextRight = Math.max(nextRight, index + num);
    }
    if (pos == right) {
      if (right == nextRight) {
        return -1;
      }
      right = nextRight;
      times++;
    }
    pos++;
  }
  return  times;
};

李恒道

https://leetcode.cn/problems/minimum-genetic-mutation/submissions/595576532/?envType=study-plan-v2&envId=top-interview-150
bfs过了

const charList = "ACGT".split("");
var minMutation = function (startGene, endGene, bank) {
  const cache = new Set();
  for (const str of bank) {
    cache.add(str);
  }
  const visit = new Set();
  const steps = new Map();
  const stack = [startGene];
  steps.set(startGene, 0);
  while (stack.length !== 0 && !steps.has(endGene)) {
    let ostr = stack.shift();
    if (visit.has(ostr)) {
      continue;
    }
    let str = ostr.split("");
    let step = steps.get(ostr);
    for (let index = 0; index < str.length; index++) {
      const originChar = str[index];
      if(index==4){
        debugger
    }
      for (let pos = 0; pos < charList.length; pos++) {
        const char = charList[pos];
        if (char == originChar) {
          continue;
        }
        str[index] = char;
        const generateStr = str.join("");
        if(cache.has(generateStr)){
            debugger
        }
        if (cache.has(generateStr) && !visit.has(generateStr)) {
          stack.push(generateStr);
          steps.set(generateStr, step + 1);
        }
        str[index] = originChar;
      }
    }
    visit.add(ostr);
  }
  return steps.has(endGene) ? steps.get(endGene) : -1;
};

李恒道

https://leetcode.cn/problems/minimum-genetic-mutation/submissions/595578637/?envType=study-plan-v2&envId=top-interview-150
优化了一下
暴打100%

const charList = "ACGT".split("");
var minMutation = function (startGene, endGene, bank) {
  const cache = new Set();
  for (const str of bank) {
    cache.add(str);
  }
  const steps = new Map();
  const stack = [startGene];
  steps.set(startGene, 0);
  while (stack.length !== 0 && !steps.has(endGene)) {
    let ostr = stack.shift();
    let str = ostr.split("");
    let step = steps.get(ostr);
    for (let index = 0; index < str.length; index++) {
      const originChar = str[index];
      for (let pos = 0; pos < charList.length; pos++) {
        const char = charList[pos];
        if (char == originChar) {
          continue;
        }
        str[index] = char;
        const generateStr = str.join("");
        if (cache.has(generateStr) && !steps.has(generateStr)) {
          stack.push(generateStr);
          steps.set(generateStr, step + 1);
        }
        str[index] = originChar;
      }
    }
  }
  return steps.has(endGene) ? steps.get(endGene) : -1;
};