js手写题：第一章-阿里云开发者社区

js手写题：第一章

2023-12-12 22

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： js手写题：第一章

前言

hello world欢迎来到前端的新世界

😜当前文章系列专栏：前端面试

🐱‍👓博主在前端领域还有很多知识和技术需要掌握，正在不断努力填补技术短板。(如果出现错误，感谢大家指出)🌹

💖感谢大家支持！您的观看就是作者创作的动力

题目

用js实现一个整数数组nums，找到其中最长严格递增子序列的长度，子序列是由数组派生而来的序列，删除(或不删除)数组中的元素而不改变其余元素的顺利，例如[3,0,2,7]是数组的[0,3,1,6,2,2,7]

加分项 :把算法难度降到O(nlog(n))

代码

方法一，二分查找法

function lengthOfLIS(nums) {
  // 特殊情况处理
  if (nums.length === 0) {
    return 0;
  }
  // 创建一个数组，用于存储递增子序列的末尾数
  const tails = [nums[0]];
  // 遍历数组，更新这个数组中的最长递增子序列
  for (let i = 1; i < nums.length; i++) {
    // 如果当前数比递增子序列的末尾数大，则将当前数加入递增子序列末尾
    if (nums[i] > tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      // 如果当前数比递增子序列的末尾数小，则用二分查找找到第一个比它大的数，并替换它
      const left = 0, right = tails.length - 1;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (tails[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tails[left] = nums[i];
    }
  }
  // 最后，返回递增子序列的长度，即 tails 数组的长度
  return tails.length;
}

方法二，动态规划

function lengthOfLIS(nums) {
  const len = nums.length;
  if (len === 0) return 0;
  const dp = new Array(len);
  let res = 0;
  dp[0] = nums[0];
  for (let i = 1; i < len; i++) {
    if (nums[i] < dp[0]) {
      dp[0] = nums[i];  // 替换掉最小末尾值
    } else if (nums[i] > dp[res]) {
      dp[++res] = nums[i];  // 如果当前元素大于所有已有递增子序列的末尾值，则直接添加到末尾
    } else {
      // 使用二分查找找到 nums[i] 在 dp 数组中该插入的位置，并替换掉该位置的值
      let left = 0;
      let right = res;
      while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (dp[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      dp[left] = nums[i];
    }
  }
  return res + 1;
}