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

李恒道

https://leetcode.cn/problems/4sum/submissions/589840312/
三数之和硬改过来的

var fourSum = function (nums, target) {
    nums = nums.sort((a, b) => a - b)
    const result = [];
    const cache = new Map()
    for (let top = 0; top < nums.length; top++) {
        const t = nums[top];
        for (let index = top + 1; index < nums.length; index++) {
            const a = nums[index];
            let indey = index + 1;
            let indez = nums.length - 1
            while (indey < nums.length && indez != index && indey < indez) {
                const b = nums[indey]
                const c = nums[indez]
                const num = a + b + c + t
                if (num === target) {
                    const tag = [t, a, b, c].join(' ')
                    if (cache.has(tag)) {
                        indey++;
                    } else {
                        result.push([t, a, b, c])
                        indey++;
                        indez--;
                        cache.set(tag, true);

                    }
                } else if (num - target < 0) {
                    indey++;
                } else {
                    indez--;
                }
            }
        }

    }

    return result

};

李恒道

https://leetcode.cn/problems/3sum-closest/submissions/589851344/
写错个0以为自己算法错了
扣了半个小时我日

var threeSumClosest = function (nums, target) {
    nums = nums.sort((a, b) => a - b)
    let sep = Number.MAX_SAFE_INTEGER;
    let ans = 0
    for (let index = 0; index < nums.length; index++) {
        const a = nums[index];
        let indey = index + 1;
        let indez = nums.length - 1
        while (indey < nums.length && indez != index && indey < indez) {
            const b = nums[indey]
            const c = nums[indez]
            const num = a + b + c
            if (num === target) {
                indey++;
            } else if (num < target) {
                indey++;
            } else {
                indez--;
            }
            if (Math.abs(target - num) < sep) {
                sep=Math.abs(target - num)
                ans = num
            }
        }
    }
    return ans
};

李恒道

https://leetcode.cn/problems/rank-teams-by-votes/
打卡题

var rankTeams = function (votes) {
  const rank = new Array(26).fill(0).map((val, index) => {
    return {
      char: index,
      arr: new Array(votes[0].length).fill(0),
    };
  });

  for (let index = 0; index < votes.length; index++) {
    for (let indey = 0; indey < votes[index].length; indey++) {
      const char = votes[index][indey];
      rank[char.charCodeAt() - 65].arr[indey]++;
    }
  }
  rank.sort((a, b) => {
    for (let index = 0; index < a.arr.length; index++) {
      const num1 = a.arr[index];
      const num2 = b.arr[index];
      if (num1 > num2) {
        return -1;
      }
      if (num1 < num2) {
        return 1;
      }
    }
    return a.char - b.char;
  });
  let ans = "";
  for (let index = 0; index < votes[0].length; index++) {
    ans+=String.fromCharCode(rank[index].char+65)
  }
  return ans

};

李恒道

https://leetcode.cn/problems/linked-list-in-binary-tree/
打卡题

var isSubPath = function (head, root) {
  const dfs = (root1, root2) => {
    if (root2 == null) {
      return true;
    }
    if (root1 == null) {
      return false;
    }
    let ans = false;
    if (root1.val == root2.val) {
      ans = dfs(root1.left, root2.next) || dfs(root1.right, root2.next);
    }
    ans = ans || (root2==head&&(dfs(root1.left, head) || dfs(root1.right, head)));

    return ans;
  };
  return dfs(root, head);
};

李恒道

https://leetcode.cn/problems/subtree-of-another-tree/submissions/590282320/
这题是简单？

var isSubtree = function (root, subRoot) {
  const dfs = (root1, root2) => {
    if (root2 == null&&root1 == null) {
      return true;
    }
    if (root1 == null) {
      return false;
    }
    if (root2 == null) {
      return false;
    }
    let ans = false;
    if (root1.val == root2.val) {
      ans = dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    }
    ans =
      ans ||
      (root2 == subRoot && (dfs(root1.left, subRoot)||dfs(root1.right, subRoot)));
    return ans;
  };
  return dfs(root,subRoot)
};

李恒道

https://leetcode.cn/problems/divide-two-integers/submissions/590288371/

二分法秒了

var divide = function (dividend, divisor) {
  const symbol =
    (divisor < 0 && dividend > 0) || (divisor > 0 && dividend < 0) ? -1 : 1;
  divisor = Math.abs(divisor) ;
  dividend = Math.abs(dividend) ;

  let l = 0;
  let r = dividend;
  let ans = 0;
  while (l <= r) {
    const center = l + Math.floor((r - l) / 2);
    if (center * divisor > dividend) {
      r = center - 1;
    } else {
      l = center + 1;
      ans = center;
    }
  }
  ans=ans * symbol
  if(ans> 2147483647){
    return 2147483647
  }
  if(ans< -2147483648){
    return  -2147483648
  }
  return ans ;
};

李恒道

https://leetcode.cn/problems/minimum-cost-for-cutting-cake-ii/submissions/590434597/
贪心法直接打过了

var minimumCost = function (m, n, horizontalCut, verticalCut) {
  horizontalCut.sort((a, b) => b - a);
  verticalCut.sort((a, b) => b - a);
  h = 0;
  v = 0;
  vBlock = 1;
  hBlock = 1;
  ans = 0
  while (h < horizontalCut.length && v < verticalCut.length) {
      if (horizontalCut[h] > verticalCut[v]) {
          hBlock++;
          ans += horizontalCut[h] * vBlock
          h++
      } else {
          vBlock++;
          ans += verticalCut[v] * hBlock
          v++
      }
  }
  while (h < horizontalCut.length) {
      hBlock++;
      ans += horizontalCut[h] * vBlock
      h++
  }
  while (v < verticalCut.length) {
      vBlock++;
      ans += verticalCut[v] * hBlock
      v++
  }
  return ans

};

李恒道

https://leetcode.cn/problems/combination-sum-ii/submissions/590446003/
dfs按数组跑下去被卡时间了
转换结构一下就过了

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/count-and-say/submissions/590452129/
递归问题，还挺简单的，写的也很爽，有思路，好题！

var countAndSay = function (n) {
  const dfs = (i) => {
    if (i == 1) {
      return "1";
    }
    const last = dfs(i - 1);
    let ans = "";
    for (let index = 0; index < last.length; index++) {
      const char = last[index];
      let end = index;
      while (last[end + 1] == char) {
        end++;
      }
      ans += `${end - index+1}${char}`;
      index = end;
    }
    return ans
  };
  return dfs(n)
};

李恒道

https://leetcode.cn/problems/sudoku-solver/submissions/590541196/
dfs炸了

var solveSudoku = function (board) {
  const next = (x, y) => {
    if (y >= board.length) {
      return [x + 1, 0];
    } else {
      return [x, y + 1];
    }
  };
  const line = new Array(9).fill(0).map(() => new Map());
  const row = new Array(9).fill(0).map(() => new Map());
  const block = new Array(9).fill(0).map(() => new Map());
  const setChar = (index, indey, char, status = true) => {
    line[index].set(char, status);
    row[indey].set(char, status);
    block[Math.floor(index / 3) * 3 + Math.floor(indey / 3)].set(char, status);
  };
  const getUseNumber = (x, y) => {
    const list = [];
    for (let index = 1; index <= 9; index++) {
      const num = index + "";
      if (line[x].get(num) == true) {
        continue;
      }
      if (row[y].get(num) == true) {
        continue;
      }
      if (block[Math.floor(x / 3) * 3 + Math.floor(y / 3)].get(num) == true) {
        continue;
      }
      list.push(num);
    }
    return list;
  };
  let ans = false;
  const dfs = (x, y) => {
    if (x == board.length) {
      ans = true;
      return;
    }
    const char = board[x][y];
    if (char == ".") {
      const list = getUseNumber(x, y);
      const [nextX, nextY] = next(x, y);
      for (let index = 0; index < list.length; index++) {
        const num = list[index];
        board[x][y] = num;
        setChar(x, y, num);
        dfs(nextX, nextY);
        if (ans == true) {
          break;
        }
        setChar(x, y, num, false);
        board[x][y] = ".";
      }
    } else {
      const [nextX, nextY] = next(x, y);
      dfs(nextX, nextY);
    }
  };

  for (let index = 0; index < board.length; index++) {
    for (let indey = 0; indey < board[0].length; indey++) {
      const char = board[index][indey];
      if (char == ".") {
        continue;
      }
      setChar(index, indey, char);
    }
  }
  dfs(0, 0);
};