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

李恒道 · 发表于 2024-4-5 12:16:35

账号
https://leetcode.cn/u/lihengdao/
2024年5月4日注册
2024年12月31日94688名 336题
2025年1月4日80696名
2025年1月5日77299名
2025年1月6日75700名 375题
2025年1月7日73814名 380题
2025年1月10日72410名 384题
2025年1月13日70306名 390题
2025年1月14日68618名 395题
2025年1月16日67359名 399题
2025年1月23日64868名 407题
2025年1月28日59118名 426题
2025年1月30日55195名 440题
2025年2月1日51466名 455题
2025年2月2日48762名 467题
2025年2月3日46547名 479题
2025年2月6日42710名 497题

李恒道 · 发表于 2024-4-5 12:36:37

https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-100-liked

热榜第一题两数相加
常规利用两层for或哈希表
这里我利用了排序数组的单调性
排序数组是Nlog，两次for循环N复杂度
总体复杂度Nlog
代码

var twoSum = function (oldNums, target) {
  nums = oldNums.toSorted((a, b) => a - b);
  let L = 0;
  let R = nums.length - 1;
  while (L < R) {
    const num1 = nums[L];
    const num2 = nums[R];
    const reuslt = num1 + num2;
    if (reuslt > target) {
      R--;
    } else if (reuslt == target) {
      break;
    } else {
      L++;
    }
  }
  const arr = [];
  for (let index = 0; index < oldNums.length; index++) {
    if (oldNums[index] === nums[L]&&arr[0]===undefined) {
      arr[0] = index;
    }else if (oldNums[index] === nums[R]&&arr[1]===undefined) {
      arr[1] = index;
    }
  }
  return arr;
};

图片.png

李恒道 · 发表于 2024-4-5 12:39:55

https://leetcode.cn/problems/perfect-number/submissions/520264242/
完美数
利用之前的特性解改改秒的

/**
 * @param {number} num
 * @Return {boolean}
 */
var checkPerfectNumber = function(num) {
  const baseBinary = num - (num & (num - 1)) - 1;
  if (num & (baseBinary - 1 !== 0)) {
    return false;
  }
  const moveNum = Math.log2(baseBinary + 1);
  if ((baseBinary << (moveNum + 1)) + (baseBinary + 1) === num) {
    let resultList = {1:true};
    let result = Math.ceil(num / 2);
    let charArray = num.toString().split("");
    while (charArray.length !== 1) {
      charArray = charArray
        .reduce((accumulator, currentValue) => {
          return accumulator + parseInt(currentValue);
        }, 0)
        .toString()
        .split("");
    }
    while (result !== 1) {
      resultList[result] = true;
      result = Math.ceil(result / 2);
    }
    if (num === 6 || charArray[0] === "1") {
      for (let i = 1; i < num; i++) {
        if (num % i == 0) {
          if (resultList[i] !== true) {
            return false;
          }
        }
      }
      return true;
    }
  }
  return false;
};

图片.png

李恒道 · 发表于 2024-4-5 13:02:55

https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked

var groupAnagrams = function (strs) {
  const obj = strs.reduce((obj, value) => {
    const name = value.split("").sort().join("");
    (obj[name] = obj[name] ?? []), obj[name].push(value);
    return obj;
  }, {});
  const arr = [];
  for (const key in obj) {
    arr.push(obj[key]);
  }
  return arr;
};

图片.png

今天收工

李恒道 · 发表于 2024-4-5 13:21:51

https://leetcode.cn/problems/climbing-stairs/?envType=study-plan-v2&envId=dynamic-programming

爬楼梯，标准DP

先出基础状态转移

/**
 * @param {number} n
 * @Return {number}
 */
var climbStairs = function (num) {
  const arr = new Array(num + 1).fill(0);
  arr[0] = arr[1] = 1;
  for (let index = 2; index < arr.length; index++) {
    arr[index] = arr[index - 1] + arr[index - 2];
  }
  return arr[num];
};

可以看出每次只依赖上次
打印数组发现是 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
斐波那契数列

可以直接用通项公式秒

const fibs = n =>
  Math.round(
    (Math.sqrt(5) / 5) *
      (Math.pow((1 + Math.sqrt(5)) / 2, n) -
        Math.pow((1 - Math.sqrt(5)) / 2, n)),
  );
var climbStairs = function (num) {
  return fibs(num+1)
};

矩阵法不知道为什么性能不好，就没用了
图片.png