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

李恒道

2024/4/5日注册账号
https://leetcode.cn/u/lihengdao/

李恒道

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;
};

李恒道

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;
};

李恒道

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;
};

今天收工

李恒道

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)
};

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

王一之

nb！这么强么gg

李恒道

王一之 发表于 2024-4-5 15:31
nb！这么强么gg

我也不知道为啥

最近突然对lc感兴趣了

然后发现题其实一点都不难....

王一之

李恒道 发表于 2024-4-5 15:54
我也不知道为啥

最近突然对lc感兴趣了

哥哥都还是简单题。。。。

别自信得太早

steven026

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

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

热榜第一题两数 ...

在哥哥基础上优化了一下，竟然和哥哥性能一样？算法好难哦😒

李恒道

王一之 发表于 2024-4-5 15:59
哥哥都还是简单题。。。。

别自信得太早

题虽然是简单题，但是打法不是简单题打法的

两数相加证明了区间范围单调性才写的收缩
跳楼梯从DP转斐波那契开方算法转斐波那契矩阵算法
完美数那个也是特性秒的

没一个走的纯暴力

也是挑战一下，看看能不能打到lc前一万名