Knowledge_Repository

主题

Teeker2026-04-06
1520
6.6m

前端机试：动态规划与贪心算法高频核心题整理 ​

你希望我把前端机试中动态规划（DP）和贪心算法的高频核心题目整理成“题目+核心思路+完整JS解答”的形式，方便你集中复习和直接练习，这也是考前冲刺最高效的方式。下面按题型分类整理，所有代码均可直接复制运行。

一、动态规划（DP）高频核心题（覆盖80%前端机试DP考点） ​

1. 爬楼梯（LeetCode 70） ​

题目：每次只能走1或2步，求到达第n阶楼梯的方法数。

核心思路：

  • 状态定义：dp[i] = 到达第i阶的方法数；

  • 转移方程：dp[i] = dp[i-1] + dp[i-2]（最后一步要么走1步，要么走2步）；

  • 初始条件：dp[1]=1，dp[2]=2。

JavaScript

// 空间优化版（机试优先写这个，更简洁）
function climbStairs(n) {
  // 边界处理：前端机试必做
  if (n <= 2) return n;
  let prev1 = 1; // 对应dp[i-2]
  let prev2 = 2; // 对应dp[i-1]
  for (let i = 3; i <= n; i++) {
    const temp = prev1 + prev2;
    prev1 = prev2;
    prev2 = temp;
  }
  return prev2;
}

// 测试
console.log(climbStairs(5)); // 8

2. 最大子数组和（LeetCode 53） ​

题目：给定整数数组，找一个连续子数组，使其和最大，返回该和。

核心思路：

  • 状态定义：dp[i] = 以第i个元素结尾的最大连续子数组和；

  • 转移方程：dp[i] = Math.max(nums[i], dp[i-1] + nums[i])（要么接上前一段，要么重新开始）；

  • 初始条件：dp[0] = nums[0]，同时维护全局最大值。

JavaScript

function maxSubArray(nums) {
  if (nums.length === 0) return 0;
  let dp = nums[0]; // 滚动变量，代替数组
  let maxSum = dp;
  
  for (let i = 1; i < nums.length; i++) {
    dp = Math.max(nums[i], dp + nums[i]);
    maxSum = Math.max(maxSum, dp);
  }
  return maxSum;
}

// 测试
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6

3. 打家劫舍（LeetCode 198） ​

题目：不能抢劫相邻房屋，求能抢劫的最大金额。

核心思路：

  • 状态定义：dp[i] = 前i间房屋能抢的最大金额；

  • 转移方程：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])（抢第i间则不能抢i-1，不抢则等于i-1的结果）；

  • 初始条件：dp[0]=nums[0]，dp[1]=Math.max(nums[0], nums[1])。

JavaScript

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  let prev1 = nums[0]; // dp[i-2]
  let prev2 = Math.max(nums[0], nums[1]); // dp[i-1]
  
  for (let i = 2; i < nums.length; i++) {
    const temp = Math.max(prev2, prev1 + nums[i]);
    prev1 = prev2;
    prev2 = temp;
  }
  return prev2;
}

// 测试
console.log(rob([1,2,3,1])); // 4
console.log(rob([2,7,9,3,1])); // 12

4. 最长递增子序列（LeetCode 300） ​

题目：找数组中最长的严格递增子序列的长度（子序列不要求连续）。

核心思路：

  • 状态定义：dp[i] = 以第i个元素结尾的最长递增子序列长度；

  • 转移方程：遍历j < i，若nums[i] > nums[j]，则dp[i] = Math.max(dp[i], dp[j]+1)；

  • 初始条件：dp[i] = 1（每个元素自身是长度为1的子序列）。

JavaScript

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  const dp = new Array(nums.length).fill(1);
  let maxLen = 1;
  
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  return maxLen;
}

// 测试
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4（[2,3,7,101]）

二、贪心算法高频核心题（机试贪心题90%和排序相关） ​

1. 买卖股票的最佳时机II（LeetCode 122） ​

题目：可以多次买卖股票（买入后必须卖出才能再买），求最大利润。

核心思路：贪心策略——只要后一天价格比前一天高，就赚差价（局部最优推全局最优）。

JavaScript

function maxProfit(prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    // 只赚正差价
    if (prices[i] > prices[i-1]) {
      profit += prices[i] - prices[i-1];
    }
  }
  return profit;
}

// 测试
console.log(maxProfit([7,1,5,3,6,4])); // 7（5-1 + 6-3）

2. 分发饼干（LeetCode 455） ​

题目：用饼干满足孩子胃口，每个孩子只能吃1块饼干，求最多满足多少孩子。

核心思路：贪心策略——先排序，用最小的能满足的饼干喂最小胃口的孩子（最大化满足数量）。

JavaScript

function findContentChildren(g, s) {
  // 先排序（核心步骤）
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  
  let child = 0; // 已满足的孩子数
  let cookie = 0; // 当前遍历的饼干
  
  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) {
      child++; // 满足一个孩子
    }
    cookie++; // 饼干无论是否用掉，都要换下一个
  }
  return child;
}

// 测试
console.log(findContentChildren([1,2,3], [1,1])); // 1
console.log(findContentChildren([1,2], [1,2,3])); // 2

3. 无重叠区间（LeetCode 435） ​

题目：移除最少的区间，使剩余区间互不重叠，求需要移除的区间数。

核心思路：贪心策略——按区间结束时间排序，优先选结束早的区间（最大化不重叠数量）。

JavaScript

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  
  // 按区间结束时间升序排序（核心贪心策略）
  intervals.sort((a, b) => a[1] - b[1]);
  
  let count = 1; // 不重叠的区间数（至少1个）
  let lastEnd = intervals[0][1];
  
  for (let i = 1; i < intervals.length; i++) {
    // 当前区间起始 >= 上一个区间结束，不重叠
    if (intervals[i][0] >= lastEnd) {
      count++;
      lastEnd = intervals[i][1];
    }
  }
  
  // 总区间数 - 不重叠数 = 需移除的数量
  return intervals.length - count;
}

// 测试
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1（移除[1,3]）

总结 ​

  1. DP核心：抓住「状态定义→转移方程→初始条件」三要素，优先用「滚动变量」优化空间（前端机试更青睐简洁代码）；

  2. 贪心核心：先确定排序类贪心策略（如“结束早优先”“最小满足优先”），验证无反例后直接编码；

  3. 刷题优先级：先吃透DP的前3题+贪心的前2题（覆盖基础考点），再练剩余题目（进阶考点），所有代码可直接用于机试。

这些题目是前端机试中DP/贪心的“保底题”，掌握后能应对80%以上的相关考点，建议你逐题手写一遍，重点记思路而非死记代码。

（注：文档部分内容可能由 AI 生成）

最近更新