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

李恒道

https://leetcode.cn/problems/remove-invalid-parentheses/submissions/573085240/
dfs，这题没想出来

var removeInvalidParentheses = function (s) {
    let lNum = 0;
    let rNum = 0;
    let other = 0;
    for (let index = 0; index < s.length; index++) {
        if (s[index] == '(') {
            lNum++
        } else if (s[index] == ')') {
            rNum++
        } else {
            other++;
        }
    }
    let max = Math.min(lNum, rNum);
    let cache = new Set();
    let len = 0;
    const dfs = (index, str, score) => {
        if (score < 0) {
            return
        }
        if (index >= s.length) {
            if (score == 0 && str.length >= len) {
                if (str.length > len) {
                    cache = new Set();
                    len=str.length
                }
                cache.add(str)
            }
            //end
            return;
        }
        const char = s[index]
        if (char == "(") {
            dfs(index + 1, str + "(", score + 1)
            dfs(index + 1, str, score)
        } else if (char == ")") {
            dfs(index + 1, str + ")", score - 1)
            dfs(index + 1, str, score)
        } else {
            dfs(index + 1, str + char, score)
        }
    }
    dfs(0, "", 0)
    return[...cache]
};

李恒道

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/submissions/573093753/?envType=study-plan-v2&envId=top-interview-150
考察中序遍历

var getMinimumDifference = function (root) {
  let pre = undefined;
  let result = Number.MAX_SAFE_INTEGER;
  const dfs = (node) => {
    if (node == null) {
      return;
    }
    dfs(node.left);
    if (pre !== undefined) {
      result = Math.min(result, Math.abs(pre - node.val));
      pre = node.val;
    } else {
      pre = node.val;
    }
    dfs(node.right);
  };
  dfs(root);
  return result;
};

李恒道

https://leetcode.cn/problems/find-peak-element/submissions/573095972/?envType=study-plan-v2&envId=top-interview-150
二分法

var findPeakElement = function (nums) {
  const findMax = (l, r) => {
    if (l > r) {
      return -1;
    }
    const center =  Math.floor((l + r) / 2);
    if (nums[center] > (nums[center - 1]??Number.MIN_SAFE_INTEGER )&& nums[center] > (nums[center + 1]??Number.MIN_SAFE_INTEGER)) {
      return center;
    } else {
      //没找到
      const result1 = findMax(l, center - 1);
      if(result1!==-1){
        return result1
      }
      const result2 = findMax(center + 1, r);
      if(result2!==-1){
        return result2
      }
    }
    return -1
  };
  return  findMax(0, nums.length - 1);
};

李恒道

https://leetcode.cn/problems/minimum-average-of-smallest-and-largest-elements/submissions/573105227/
排序+双指针
简单题

var minimumAverage = function (nums) {
  nums.sort((a, b) => a - b);
  const base=Math.floor(nums.length/2)
  let result=Number.MAX_SAFE_INTEGER
  for (let index = 0; index < base; index++) {
    result=Math.min(result,(nums[index]+nums[nums.length-1-index])/2)
  }

  return result
};

李恒道

https://leetcode.cn/problems/number-of-1-bits/submissions/573109008/?envType=study-plan-v2&envId=top-interview-150
简单题，查1

var hammingWeight = function(n) {
  let times=0;
  for (let index = 0; index < 32; index++) {
    times+=(n>>index)&1

  }
  return times
};

李恒道

https://leetcode.cn/problems/k-inverse-pairs-array/submissions/573401817/

逆序对，mod卡我半天，优化卡我半天...

var kInversePairs = function (n, k) {
  const dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
  for (let index = 0; index < dp.length; index++) {
    dp[index][0] = 1;
  }
  const mod = 1000000007;
  for (let index = 2; index < dp.length; index++) {
    for (let indey = 1; indey < dp[0].length; indey++) {
      //5-3依赖于4-3 4-2 4-1 4-0
      //5-4依赖于4-4 4-3 4-2 4-1 4-0
      dp[index][indey] = (dp[index][indey - 1] + dp[index - 1][indey]) % mod;
      if (indey >= index) {
        // 5-6依赖于 4-6 4-5 4-4 4-3 4-2
        // 5-7依赖于 4-7 4-6 4-5 4-4 4-3\
        dp[index][indey] += mod;
        dp[index][indey] -= dp[index - 1][indey - index];
        dp[index][indey] = dp[index][indey] % mod;
      }
    }
  }
  return dp.pop().pop();
};

李恒道

https://leetcode.cn/problems/boolean-evaluation-lcci/submissions/573403843/

dfs区间划分

var countEval = function (s, result) {
  const cache = new Map();
  const dfs = (l, r) => {
    const flag = `${l} ${r}`;
    if (cache.has(flag)) {
      return cache.get(flag);
    }
    if (l == r) {
      return {
        t: s[l] === "1" ? 1 : 0,
        f: s[l] === "0" ? 1 : 0,
      };
    }
    let t = 0;
    let f = 0;
    for (let index = l + 1; index < r; index += 2) {
      let info1 = dfs(l, index - 1);
      let info2 = dfs(index + 1, r);
      switch (s[index]) {
        case "&":
          t += info1.t * info2.t;
          f += info1.t * info2.f;
          f += info1.f * info2.t;
          f += info1.f * info2.f;
          break;
        case "|":
          t += info1.t * info2.t;
          t += info1.t * info2.f;
          t += info1.f * info2.t;
          f += info1.f * info2.f;
          break;
        case "^":
          f += info1.t * info2.t;
          t += info1.t * info2.f;
          t += info1.f * info2.t;
          f += info1.f * info2.f;
          break;
      }
    }
    cache.set(flag, {
      t,
      f,
    });
    return {
      t,
      f,
    };
  };
  let info = dfs(0, s.length - 1);
  return result == 1 ? info.t : info.f;
};

李恒道

https://leetcode.cn/problems/factorial-trailing-zeroes/submissions/573404825/?envType=study-plan-v2&envId=top-interview-150
找规律题

var trailingZeroes = function (n) {
  let fiveNum = 0;
  for (let index = 5; index <= n; index *= 5) {
    fiveNum += Math.floor(n / index);
  }
  return fiveNum;
};

李恒道

https://leetcode.cn/problems/valid-palindrome/submissions/573405820/?envType=study-plan-v2&envId=top-interview-150
gpt完全给ascii的知识污染了
我日

var isPalindrome = function (s) {
  let l = 0,
    r = s.length - 1;
  while (l < r) {
    let char1 = s[l].charCodeAt();
    let char2 = s[r].charCodeAt();
    if (char1 >= 65 && char1 <= 90) {
      //转小写
      char1 += 32;
    }
    if (char2 >= 65 && char2 <= 90) {
      //转小写
      char2 += 32;
    }
    if (!((char1 >= 97 && char1 <= 122) || (char1 >= 48 && char1 <= 57))) {
      l++;
      continue;
    }
    if (!((char2 >= 97 && char2 <= 122) || (char2 >= 48 && char2 <= 57))) {
      r--;
      continue;
    }
    if (char1 == char2) {
      l++;
      r--;
    } else {
      return false;
    }
  }
  return true;
};

李恒道

https://leetcode.cn/problems/palindrome-partitioning-ii/submissions/573717680/
双dp

var minCut = function (s) {
    const dp = new Array(s.length).fill(0).map(() => new Array(s.length).fill(0))
    for (let index = 0; index <= dp.length - 2; index++) {
        dp[index][index] = 1;
        dp[index][index + 1] = s[index] == s[index + 1] ? 2 : 0;
    }
    dp[s.length - 1][s.length - 1] = 1
    for (let index = dp.length - 3; index >= 0; index--) {
        for (let indey = index + 2; indey < dp[0].length; indey++) {
            dp[index][indey] = s[index] == s[indey] ? dp[index + 1][indey - 1] : 0;
        }
    }
    const sp = new Array(s.length + 1).fill(0)
    for (let pos = sp.length - 2; pos >= 0; pos--) {
        let result = Number.MAX_SAFE_INTEGER;
        for (let index = pos; index < s.length; index++) {
            if (dp[pos][index] !== 0) {
                result = Math.min(result, sp[index + 1])
            }
        }
        sp[pos]= result + 1
    }

    return sp[0] - 1
};