🎯 前端算法面试题精选
🌟 字符串处理
1. 最长回文子串
题目描述 📝 给定一个字符串 s，找到 s 中最长的回文子串。
基础解法 - 中心扩展法
javascript
function longestPalindrome(s) {
if (s.length < 2) return s;
let start = 0, maxLength = 1;
// 从中心向两边扩展检查回文
function expandAroundCenter(left, right) {
// 当左右指针在有效范围内且字符相等时继续扩展
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
// 返回当前回文串的长度
return right - left - 1;
}
for (let i = 0; i < s.length; i++) {
// 考虑奇数长度的回文串，以当前字符为中心
const len1 = expandAroundCenter(i, i);
// 考虑偶数长度的回文串，以当前字符和下一个字符之间为中心
const len2 = expandAroundCenter(i, i + 1);
const len = Math.max(len1, len2);
// 更新最长回文串的信息
if (len > maxLength) {
maxLength = len;
// 计算回文串的起始位置
start = i - Math.floor((len - 1) / 2);
}
}
return s.substring(start, start + maxLength);
}思路详解 💡
中心扩展法的核心思想：
- 遍历每个可能的中心点
- 对于每个中心点，分别考虑奇数长度和偶数长度的情况
- 从中心向两边扩展，直到不满足回文条件
- 记录最长的回文子串
关键优化点：
- 使用两个指针（left和right）向两边扩展，避免重复计算
- 通过数学公式计算回文串的起始位置，避免额外存储
- 提前处理长度小于2的特殊情况
进阶解法 - 动态规划
javascript
function longestPalindrome(s) {
const n = s.length;
const dp = Array.from(new Array(n), () => new Array(n).fill(false));
let start = 0, maxLength = 1;
// 所有单个字符都是回文
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// 检查长度大于1的子串
for (let len = 2; len <= n; len++) {
for (let i = 0; i < n - len + 1; i++) {
const j = i + len - 1;
if (len === 2) {
dp[i][j] = s[i] === s[j];
} else {
dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1];
}
if (dp[i][j] && len > maxLength) {
start = i;
maxLength = len;
}
}
}
return s.substring(start, start + maxLength);
}思路解析 💡
中心扩展法：
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 优点：实现简单，空间效率高
动态规划法：
- 时间复杂度：O(n²)
- 空间复杂度：O(n²)
- 优点：可以保存中间结果，适合处理大规模数据
2. 字符串的全排列
题目描述 📝 输入一个字符串，打印出该字符串中字符的所有排列。
基础解法 - 回溯法
javascript
function permutation(str) {
const result = new Set();
const chars = str.split('');
function backtrack(arr, temp) {
if (temp.length === str.length) {
result.add(temp.join(''));
return;
}
for (let i = 0; i < arr.length; i++) {
const current = [...arr];
const char = current.splice(i, 1)[0];
backtrack(current, [...temp, char]);
}
}
backtrack(chars, []);
return Array.from(result);
}进阶解法 - 字典序法
javascript
function permutation(str) {
const chars = str.split('').sort();
const result = [];
result.push(chars.join(''));
while (true) {
let i = chars.length - 2;
while (i >= 0 && chars[i] >= chars[i + 1]) {
i--;
}
if (i < 0) break;
let j = chars.length - 1;
while (j > i && chars[j] <= chars[i]) {
j--;
}
[chars[i], chars[j]] = [chars[j], chars[i]];
reverse(chars, i + 1);
result.push(chars.join(''));
}
return result;
}
function reverse(arr, start) {
let i = start, j = arr.length - 1;
while (i < j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}思路解析 💡
回溯法：
- 时间复杂度：O(n!)
- 空间复杂度：O(n)
- 适合处理所有类型的排列问题
字典序法：
- 时间复杂度：O(n!)
- 空间复杂度：O(1)
- 特点：可以按字典序生成排列
🔄 数组处理
3. 两数之和
题目描述 📝 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
基础解法 - 暴力遍历
javascript
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}进阶解法 - 哈希表
javascript
function twoSum(nums, target) {
// 使用Map存储遍历过的数字及其索引
const map = new Map();
for (let i = 0; i < nums.length; i++) {
// 计算当前数字需要的配对数
const complement = target - nums[i];
// 如果配对数已存在，直接返回结果
if (map.has(complement)) {
return [map.get(complement), i];
}
// 将当前数字及索引存入Map
map.set(nums[i], i);
}
return [];
}优化思路详解 💡
哈希表解法的优势：
- 只需要遍历一次数组
- 查找配对数的时间复杂度是O(1)
- 空间换时间的经典应用
实现要点：
- 使用Map而不是普通对象，因为Map的键可以是任意类型
- 边遍历边存储，避免重复遍历
- 先检查配对数，再存储当前数，可以处理重复元素的情况
5. 合并区间
题目描述 📝 给出一个区间的集合，请合并所有重叠的区间。
javascript
function merge(intervals) {
if (!intervals.length) return [];
// 按起始位置排序
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const last = result[result.length - 1];
if (current[0] <= last[1]) {
// 有重叠，更新结束位置
last[1] = Math.max(last[1], current[1]);
} else {
// 无重叠，添加新区间
result.push(current);
}
}
return result;
}6. 旋转数组
题目描述 📝 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
javascript
function rotate(nums, k) {
k = k % nums.length;
// 三次翻转
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
return nums;
}
function reverse(nums, start, end) {
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start++;
end--;
}
}
## 🌳 树结构
### 4. 二叉树的层序遍历
**题目描述** 📝
给你一个二叉树，请你返回其按层序遍历得到的节点值。
例如:3
/
9 20 /
15 7
输出: [[3], [9,20], [15,7]]
**基础解法** - 队列实现
```javascript
function levelOrder(root) {
// 处理空树的边界情况
if (!root) return [];
const result = [];
// 使用队列存储每一层的节点
const queue = [root];
while (queue.length) {
// 记录当前层的节点数,确保一次处理整层
const size = queue.length;
const level = [];
// 处理当前层的所有节点
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
// 将下一层的节点加入队列
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}进阶解法 - DFS实现
javascript
function levelOrder(root) {
const result = [];
// 深度优先遍历函数
function dfs(node, level) {
// 处理空节点
if (!node) return;
// 当前层级还没有数组时,初始化数组
if (result.length === level) {
result.push([]);
}
// 将节点值加入对应级的数组
result[level].push(node.val);
// 递归处理左右子树,层级+1
dfs(node.left, level + 1);
dfs(node.right, level + 1);
}
dfs(root, 0);
return result;
}思路详解 💡
BFS解法要点:
- 使用队列实现层序遍历的核心数据结构
- 通过size变量控制每层的节点数量
- 每次处理完当前层,再处理下一层
- 时间复杂度O(n),空间复杂度O(w),w为树的最大宽度
DFS解法要点:
- 通过level参数记录当前层级
- 提前创建每层的结果数组
- 递归时层级+1
- 时间复杂度O(n),空间复杂度O(h),h为树的高度
5. 二叉树的最近公共祖先
题目描述 📝 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
例如:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3最优解法 - 递归实现
javascript
function lowestCommonAncestor(root, p, q) {
// 基础情况: 空节点或找到目标节点
if (!root || root === p || root === q) {
return root;
}
// 递归搜索左右子树
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 如果左右子树都找到了节点,说明当前root就是LCA
if (left && right) {
return root;
}
// 返回非空的那个子树的结果
return left || right;
}思路详解 💡
递归解法的核心思想:
- 自底向上查找目标节点
- 如果当前节点是目标节点之一,直接返回
- 如果左右子树都找到了节点,说明当前节点就是LCA
- 如果只有一边找到了节点,则返回那一边的结果
实现要点:
- 使用后序遍历的思路
- 利用递归函数的返回值传递信息
- 无需额外的存储空间
- 时间复杂度O(n),空间复杂度O(h)
6. 二叉搜索树的验证
题目描述 📝 给定一个二叉树，判断其是否是一个有效的二叉搜索树(BST)。
javascript
function isValidBST(root) {
// 辅助函数,用于验证节点值是否在有效范围内
function validate(node, min, max) {
// 空节点认为是有效的BST
if (!node) return true;
// 检查当前节点值是否在有效范围内
if (node.val <= min || node.val >= max) {
return false;
}
// 递归验证左右子树
// 左子树的所有节点值必须小于当前节点值
// 右子树的所有节点值必须大于当前节点值
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}思路详解 💡
验证思路:
- BST的每个节点都有一个有效值范围
- 左子树的所有节点值必须小于当前节点
- 右子树的所有节点值必须大于当前节点
- 使用递归时通过参数传递有效范围
关键点:
- 使用-Infinity和Infinity作为初始范围
- 递归时动态更新范围的上下界
- 注意处理相等的情况(BST中不允许重复值)
- 时间复杂度O(n),空间复杂度O(h)
🔄 动态规划专题
7. 爬楼梯问题
题目描述 📝 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例:
输入：n = 3
输出：3
解释：有三种方法��以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶基础解法 - 动态规划
javascript
function climbStairs(n) {
// 处理基础情况
if (n <= 2) return n;
// 初始化dp数组
const dp = new Array(n + 1);
dp[1] = 1; // 爬1阶只有1种方法
dp[2] = 2; // 爬2有2种方法
// 从第3阶开始计算
for (let i = 3; i <= n; i++) {
// 到达第i阶的方法数 = 到达第(i-1)阶的方法数 + 到达第(i-2)阶的方法数
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}优化解法 - 空间优化版本
javascript
function climbStairs(n) {
if (n <= 2) return n;
// 只需要保存前两个状态
let prev2 = 1; // 代表dp[i-2]
let prev1 = 2; // 代表dp[i-1]
let current = 0;
// 从第3阶开始计算
for (let i = 3; i <= n; i++) {
current = prev1 + prev2;
// 更新状态
prev2 = prev1;
prev1 = current;
}
return current;
}思路详解 💡
动态规划解法要点:
- 定义状态: dp[i]表示爬到第i阶的方法数
- 状态转移方程: dp[i] = dp[i-1] + dp[i-2]
- 初始状态: dp[1] = 1, dp[2] = 2
- 时间复杂度O(n), 空间复杂度O(n)
空间优化思路:
- 只需要记录前两个状态
- 使用三个变量代替数组
- 时间复杂度O(n), 空间复杂度O(1)
8. 最长递增子序列
题目描述 📝 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
示例:
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4基础解法 - 动态规划
javascript
function lengthOfLIS(nums) {
if (!nums.length) return 0;
// dp[i]表示以nums[i]结尾的最长递增子序列长度
const dp = new Array(nums.length).fill(1);
let maxLen = 1;
// 对每个位置i，检查前面所有的位置j
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;
}进阶解法 - 二分查找优化
javascript
function lengthOfLIS(nums) {
if (!nums.length) return 0;
// tails[i]存储长度为i+1的递增子序列的最小结尾值
const tails = [nums[0]];
for (let i = 1; i < nums.length; i++) {
// 如果当前数字大于所有tails中的值，直接添加
if (nums[i] > tails[tails.length - 1]) {
tails.push(nums[i]);
continue;
}
// 二分查找第一个大于等于nums[i]的位置
let left = 0;
let 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数组
tails[left] = nums[i];
}
return tails.length;
}思路详解 💡
动态规划解法:
- 状态定义: dp[i]表示以nums[i]结尾的LIS长度
- 状态转移: 对每个j < i，如果nums[i] > nums[j]，则可以接在j后面
- 时间复杂度O(n²)，空间复杂度O(n)
二分查找优化:
- 维护一个tails数组，存储不同长度递增子序列的最小结尾值
- 对每个数字二分查找其在tails中的位置
- 时间复杂度O(nlogn)，空间复杂度O(n)
9. 背包问题
题目描述 📝 给定n个物品，每个物品有重量w和价值v，背包容量为W，求解放入背包的物品的最大价值总和。
javascript
function knapsack(weights, values, W) {
const n = weights.length;
// dp[i][j]表示前i个物品，容量为j时的最大价值
const dp = Array.from({length: n + 1}, () => new Array(W + 1).fill(0));
// 遍历每个物品
for (let i = 1; i <= n; i++) {
// 遍历每种容量
for (let j = 1; j <= W; j++) {
if (weights[i-1] <= j) {
// 可以放入当前物品，取放入或不放入的最大值
dp[i][j] = Math.max(
dp[i-1][j], // 不放入当前物品
dp[i-1][j-weights[i-1]] + values[i-1] // 放入当前物���
);
} else {
// 不能放入当前物品
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
// 空间优化版本
function knapsackOptimized(weights, values, W) {
const n = weights.length;
// 只使用一维数组
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < n; i++) {
// 必须从后向前遍历，避免重复使用物品
for (let j = W; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);
}
}
return dp[W];
}思路详解 💡
动态规划解法要点:
- 状态定义: dp[i][j]表示前i个物品在容量j下的最大价值
- 状态转移: 考虑放入或不放入当前物品两种情况
- 边界条件: dp[0][j] = 0, dp[i][0] = 0
- 时间复杂度O(nW), 空间复杂度O(nW)
空间优化思路:
- 使用一维数组代替二维数组
- 从后向前遍历避免重复计算
- 时间复杂度O(nW), 空间复杂度O(W)
📚 动态规划解题技巧
解题步骤:
- 定义状态（dp数组的含义）
- 找出状态转移方程
- 确定初始状态和边界条件
- 确定计算顺序
- 考虑空间优化可能性
常见优化方向:
- 状态压缩（降维）
- 滚动数组
- 位运算优化
- 数学方法优化
经典问题类型:
- 线性DP（如爬楼梯）
- 区间DP（如矩阵链乘法）
- 背包DP
- 状态压缩DP
- 树形DP
🔍 回溯算法专题
10. N皇后问题
题目描述 📝 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
示例:
输入：n = 4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]回溯解法
javascript
function solveNQueens(n) {
const result = [];
// 初始化棋盘
const board = Array.from({ length: n }, () =>
new Array(n).fill('.')
);
// 检查位置是否有效
function isValid(row, col) {
// 检查同列
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
}
// 检查上对角线
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
// 检查右上对角线
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
function backtrack(row) {
// 找到一个解
if (row === n) {
result.push(board.map(row => row.join('')));
return;
}
// 尝试在当前行的每一列放置皇后
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.'; // 回溯
}
}
}
backtrack(0);
return result;
}思路详解 💡
回溯算法要点:
- 逐行放置皇后
- 检查每个位置的有效性
- 使用递归+回溯探索所有可能性
- 时间复杂度O(N!)，空间复杂度O(N)
优化思路:
- 使用位运算优化判断
- 使用集合记录已占用的列和对角线
- 对称性剪枝
11. 子集���成
题目描述 📝 给定一组不含重复元素的整数数组 nums，返回该数组有可能的子集。
示例:
输入：nums = [1,2,3]
输出：[
[],
[1],
[2],
[3],
[1,2],
[1,3],
[2,3],
[1,2,3]
]回溯解法
javascript
function subsets(nums) {
const result = [];
function backtrack(start, current) {
// 每个状态都是一个有效的子集
result.push([...current]);
// 从start开始避免重复
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1, current);
current.pop(); // 回溯
}
}
backtrack(0, []);
return result;
}位运算解法
javascript
function subsets(nums) {
const n = nums.length;
const result = [];
// 使用位运算生成所有可能的状态
// 总共有2^n种可能
for (let i = 0; i < (1 << n); i++) {
const subset = [];
// 检查每一位是否为1
for (let j = 0; j < n; j++) {
if (i & (1 << j)) {
subset.push(nums[j]);
}
}
result.push(subset);
}
return result;
}思路详解 💡
回溯解法:
- 每个元素都有选择和不选择两种状态
- 使用start参数避免重复
- 时间复杂度O(2^n)，空间复杂度O(n)
位运算解法:
- 使用二进制位表示选择状态
- 更直观且高效
- 时间复杂度O(n*2^n)，空间复杂度O(1)
12. 组合总和
题目描述 📝 给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
示例:
输入: candidates = [2,3,6,7], target = 7
输出: [[7], [2,2,3]]回溯解法
javascript
function combinationSum(candidates, target) {
const result = [];
function backtrack(start, current, remaining) {
// 找到一个解
if (remaining === 0) {
result.push([...current]);
return;
}
// remaining小于0说明当前组合不可行
if (remaining < 0) return;
for (let i = start; i < candidates.length; i++) {
current.push(candidates[i]);
// 注意这里的start是i而不是i+1，因为可以重复使用元素
backtrack(i, current, remaining - candidates[i]);
current.pop(); // 回溯
}
}
backtrack(0, [], target);
return result;
}优化解法 - 剪枝版本
javascript
function combinationSum(candidates, target) {
// 先排序便于剪枝
candidates.sort((a, b) => a - b);
const result = [];
function backtrack(start, current, remaining) {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
// 剪枝：如果当前数字已经大于remaining，后面的数字更大，直接跳出
if (candidates[i] > remaining) break;
current.push(candidates[i]);
backtrack(i, current, remaining - candidates[i]);
current.pop();
}
}
backtrack(0, [], target);
return result;
}思路详解 💡
基本思路:
- 使用回溯法枚举所有可能的组合
- 通过remaining参数跟踪剩余目标值
- 允许重复使用元素，所以递归时start不变
优化思路:
- 先对数组排序
- 利用排序后的特性进行剪枝
- 当当前数字大于remaining时可以直接结束当前分支
📚 回溯算法解题技巧
解题步骤:
- 确定递归函数参数
- 确定终止条件
- 确定单层递归逻辑
- 考虑剪枝优化
常见优化方向:
- 排序后剪枝
- 去重处理
- 状态压缩
- 记忆化搜索
典型应用场景:
- 排列组合问题
- 集合问题
- 棋盘问题
- 路径问题
💫 贪心算法专题
13. 跳跃游戏
题目描述 📝 给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例:
输入: nums = [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后从位置 1 到最后一个位置跳 3 步即可。
输入: nums = [3,2,1,0,4]
输出: false
解释: 无论如何，总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0，所以永远不可能到达最后一个位置。贪心解法
javascript
function canJump(nums) {
// maxReach表示能够到达的最远位置
let maxReach = 0;
// 遍历数组中的每个位置
for (let i = 0; i <= maxReach; i++) {
// 如果已经能够到达最后一个位置，返回true
if (maxReach >= nums.length - 1) {
return true;
}
// 更新能够到达的最远位置
maxReach = Math.max(maxReach, i + nums[i]);
}
return false;
}优化解法 - 从后向前遍历
javascript
function canJump(nums) {
// lastPos表示需要到达的位置，初始为最后一个位置
let lastPos = nums.length - 1;
// 从倒数第二个位置向前遍历
for (let i = nums.length - 2; i >= 0; i--) {
// 如果当前位置能够到达lastPos，更新lastPos
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
// 如果lastPos为0，说明可以从起点到达终点
return lastPos === 0;
}思路详解 💡
贪心策略:
- 维护当前能够到达的最远位置
- 在遍历过程中不断更新最远位置
- 如果最远位置大于等于数组末尾，说明可以到达
优化思路:
- 从后向前遍历可以减少不必要的计算
- 只需要关注是否能到达最后一个位置
- 时间复杂度O(n)，空间复杂度O(1)
14. 分发糖果
题目描述 📝 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
示例:
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。贪心解法
javascript
function candy(ratings) {
const n = ratings.length;
// 初始化每个孩子至少有一个糖果
const candies = new Array(n).fill(1);
// 从左向右遍历，确保右边评分高的孩子比左边多
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 从右向左遍历，确保左边评分高的孩子比右边多
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// 返回总糖果数
return candies.reduce((sum, num) => sum + num, 0);
}优化解法 - 常数空间
javascript
function candy(ratings) {
const n = ratings.length;
let candies = n; // 基础糖果数（每人至少1个）
let i = 1;
while (i < n) {
if (ratings[i] === ratings[i-1]) {
i++;
continue;
}
// 处理上升序列
let peak = 0;
while (i < n && ratings[i] > ratings[i-1]) {
peak++;
candies += peak;
i++;
}
// 处理下降序列
let valley = 0;
while (i < n && ratings[i] < ratings[i-1]) {
valley++;
candies += valley;
i++;
}
// 只保留最大的坡度
candies -= Math.min(peak, valley);
}
return candies;
}思路详解 💡
基本思路:
- 两次遍历，分别处理左右两个方向
- 确保评分高的孩子获得更多糖果
- 时间复杂度O(n)，空间复杂度O(n)
优化思路:
- 识别上升和下降序列
- 使用数学方法计算序列所需糖果数
- 时间复杂度O(n)，空间复杂度O(1)
15. 加油站
题目描述 📝 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释：
从 3 号加油站(索引为 3 处)出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。贪心解法
javascript
function canCompleteCircuit(gas, cost) {
const n = gas.length;
let totalTank = 0; // 总剩余油量
let currTank = 0; // 当前剩余油量
let startStation = 0; // 起始加油站
for (let i = 0; i < n; i++) {
totalTank += gas[i] - cost[i];
currTank += gas[i] - cost[i];
// 如果当前油量小于0，说明不能从之前的任何一站到达当前站
if (currTank < 0) {
startStation = i + 1;
currTank = 0;
}
}
// 如果总剩余油量大于等于0，则一定有解
return totalTank >= 0 ? startStation : -1;
}思路详解 💡
贪心策略:
- 如果总油量大于等于总消耗，则一定有解
- 如果到达某站时油量小于0，则之前的所有站都不能作为起点
- 因此可以直接从B站开始尝试
证明正确性:
- 如果存在解，则总油量一定大于等于总消耗
- 如果从A站到B站无法到达，则A到B之间的任何站点都不能到达B
- 因此可以直接从B站开始尝试
📚 贪心算法解题技巧
解题步骤:
- 将问题分解为子问题
- 找到局部最优解
- 证明局部最优可以导致全局最优
常见优化方向:
- 预处理数据（如排序）
- 使用额外的数据结构
- 多次遍历转换为单次遍历
- 空间优化
典型应用场景:
- 区间问题
- 排序问题
- 分配问题
- 最大最小值问题
🔄 图论算法专题
16. 岛屿数量
题目描述 📝 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
示例:
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3DFS解法
javascript
function numIslands(grid) {
if (!grid || !grid.length) return 0;
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
// DFS函数用于标记访问过的陆地
function dfs(row, col) {
// 边界检查和水域检查
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === '0') {
return;
}
// 标记当前陆地为已访问
grid[row][col] = '0';
// 访问四个方向的相邻格子
dfs(row - 1, col); // 上
dfs(row + 1, col); // 下
dfs(row, col - 1); // 左
dfs(row, col + 1); // 右
}
// 遍历整个网格
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
count++; // 发现新岛屿
dfs(i, j); // 标记整个岛屿
}
}
}
return count;
}BFS解法
javascript
function numIslands(grid) {
if (!grid || !grid.length) return 0;
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
// 方向数组，用于访问四个相邻位置
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function bfs(row, col) {
const queue = [[row, col]];
grid[row][col] = '0'; // 标记起始点
while (queue.length) {
const [currRow, currCol] = queue.shift();
// 检查四个方向
for (const [dx, dy] of directions) {
const newRow = currRow + dx;
const newCol = currCol + dy;
// 检查边界和是否为陆地
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] === '1') {
queue.push([newRow, newCol]);
grid[newRow][newCol] = '0'; // 标记访问
}
}
}
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
count++;
bfs(i, j);
}
}
}
return count;
}思路详解 💡
DFS解法要点:
- 使用深度优先搜索遍历每个岛屿
- 将访问过的陆地标记为水域，避免重复计数
- 时间复杂度O(mn)，空间复杂度O(mn)
BFS解法要点:
- 使用队列实现广度优先搜索
- 使用方向数组简化相邻位置的访问
- 时间复杂度O(m*n)，空间复杂度O(min(m,n))
17. 课程表
题目描述 📝 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1 。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
判断是否可能完成所有课程的学习？
示例:
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。拓扑排序解法
javascript
function canFinish(numCourses, prerequisites) {
// 构建邻接表和入度数组
const graph = Array.from({ length: numCourses }, () => []);
const inDegree = new Array(numCourses).fill(0);
// 构建图
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
inDegree[course]++;
}
// 将所有入度为0的课程加入队列
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
let count = 0;
// BFS拓扑排序
while (queue.length) {
const curr = queue.shift();
count++;
// 将当前课程的所有后续课程入度减1
for (const next of graph[curr]) {
inDegree[next]--;
// 如果入度变为0，加入队列
if (inDegree[next] === 0) {
queue.push(next);
}
}
}
// 如果能学完所有课程，count应该等于课程总数
return count === numCourses;
}DFS检测环解法
javascript
function canFinish(numCourses, prerequisites) {
// 构建邻接表
const graph = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
// 访问状态数组: 0=未访问, 1=访问中, 2=已完成
const visited = new Array(numCourses).fill(0);
function hasCycle(course) {
// 如果当前课程正在访问中，说明存在环
if (visited[course] === 1) return true;
// 如果已经访问完成，无需重复访问
if (visited[course] === 2) return false;
visited[course] = 1; // 标记为访问中
// 检查所有后续课程
for (const next of graph[course]) {
if (hasCycle(next)) return true;
}
visited[course] = 2; // 标记为已完成
return false;
}
// 检查每个课程
for (let i = 0; i < numCourses; i++) {
if (hasCycle(i)) return false;
}
return true;
}思路详解 💡
拓扑排序解法:
- 使用BFS实现拓扑排序
- 通过入度数组判断课程是否可以学习
- 时间复杂度O(V+E)，空间复杂度O(V+E)
DFS检测环解法:
- 使用DFS检测图中是否存在环
- 使用状态数组标记访问状态
- 时间复杂度O(V+E)，空间复杂度O(V)
📚 图论算法解题技巧
常用图的表示方法:
- 邻接矩阵
- 邻接表
- 边集数组
常见图算法:
- DFS/BFS遍历
- 拓扑排序
- 最短路径
- 并查集
解题要点:
- 正确构建图的数据结构
- 选择合适的遍历方式
- 注意环的处理
- 考虑边界情况
🔄 排序算法专题
18. 快速排序实现
题目描述 📝 实现快速排序算法，对给定数组进行原地排序。
示例:
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]基础实现
javascript
function quickSort(nums, left = 0, right = nums.length - 1) {
if (left >= right) return;
// 获取分区点
const pivotIndex = partition(nums, left, right);
// 递归排序左右两部分
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
return nums;
}
function partition(nums, left, right) {
// 选择最右边的元素作为基准值
const pivot = nums[right];
let i = left - 1; // 小于基准值的区域边界
// 将小于基准值的元素移到左边
for (let j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
// 将基准值放到正确位置
[nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
return i + 1;
}优化版本 - 三路快排
javascript
function quickSort3Way(nums, left = 0, right = nums.length - 1) {
if (left >= right) return;
// 随机选择基准值以避免最坏情况
const randomIndex = left + Math.floor(Math.random() * (right - left + 1));
[nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];
const pivot = nums[left];
let lt = left; // nums[left+1...lt] < pivot
let gt = right; // nums[gt...right] > pivot
let i = left + 1; // nums[lt+1...i-1] == pivot
while (i <= gt) {
if (nums[i] < pivot) {
[nums[lt + 1], nums[i]] = [nums[i], nums[lt + 1]];
lt++;
i++;
} else if (nums[i] > pivot) {
[nums[gt], nums[i]] = [nums[i], nums[gt]];
gt--;
} else {
i++;
}
}
[nums[left], nums[lt]] = [nums[lt], nums[left]];
// 递归排序小于和大于基准值的部分
quickSort3Way(nums, left, lt - 1);
quickSort3Way(nums, gt + 1, right);
return nums;
}思路详解 💡
基本快排思路:
- 选择基准值(pivot)
- 将数组分为小于和大于基准值的两部分
- 递归排序两个子数组
- 时间复杂度平均O(nlogn)，最坏O(n²)
三路快排优化:
- 处理重复元素更高效
- 随机选择基准值避免最坏情况
- 将数组分为小于、等于、大于三部分
- 只需要递归处理小于和大于的部分
19. 归并排序与链表排序
题目描述 📝 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例:
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]归并排序解法
javascript
function sortList(head) {
// 基础情况：空链表或只有一个节点
if (!head || !head.next) return head;
// 使用快慢指针找到中点
let slow = head;
let fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 断开链表
const mid = slow.next;
slow.next = null;
// 递归排序两部分
const left = sortList(head);
const right = sortList(mid);
// 合并有序链表
return mergeTwoLists(left, right);
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}自底向上优化版本
javascript
function sortList(head) {
if (!head || !head.next) return head;
// 计算链表长度
let length = 0;
let current = head;
while (current) {
length++;
current = current.next;
}
const dummy = new ListNode(0);
dummy.next = head;
// 自底向上归并
for (let size = 1; size < length; size = size * 2) {
let prev = dummy;
current = dummy.next;
while (current) {
// 获取并断开第一部分
const left = current;
let right = split(left, size);
current = split(right, size);
// 合并两部分并连接到前面的链表
prev.next = mergeTwoLists(left, right);
// 移动到合并后的链表末尾
while (prev.next) {
prev = prev.next;
}
}
}
return dummy.next;
}
// 分割链表，返回第二部分的头节点
function split(head, size) {
if (!head) return null;
for (let i = 1; head.next && i < size; i++) {
head = head.next;
}
const second = head.next;
head.next = null;
return second;
}思路详解 💡
递归归并排序:
- 使用快慢指针找到中点
- 递归排序左右两部分
- 合并两个有序链表
- 时间复杂度O(nlogn)，空间复杂度O(logn)
自底向上优化:
- 避免递归调用栈
- 逐步增加合并的子链表长度
- 空间复杂度优化到O(1)
- 仍然保持O(nlogn)的时间复杂度
📚 排序算法技巧总结
常见排序算法比较:
- 快速排序：平均最快，原地排序
- 归并排序：稳定排序，链表排序首选
- 堆排序：空间效率高，适合大数据
- 计数排序：适合特定范围的整数
优化方向:
- 随机化避免最坏情况
- 处理重复元素
- 小规模数据使用插入排序
- 空间复杂度优化
实际应用考虑:
- 数据规模
- 稳定性要求
- 空间限制
- 是否需要原地排序
🔍 二分查找专题
20. 搜索旋转排序数组
题目描述 📝 整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例:
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1基础解法
javascript
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
// 判断哪部分是有序的
if (nums[left] <= nums[mid]) { // 左半部分有序
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1; // target在左半部分
} else {
left = mid + 1; // target在右半部分
}
} else { // 右半部分有序
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1; // target在右半部分
} else {
right = mid - 1; // target在左半部分
}
}
}
return -1;
}思路详解 💡
- 二分查找的关键点:
- 每次将数组分成两部分，其中一部分一定是有序的
- 判断目标值是否在有序部分中
- 根据判断结果缩小搜索范围
- 时间复杂度O(logn)，空间复杂度O(1)
21. 寻找两个正序数组的中位数
题目描述 📝 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例:
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3]，中位数 2
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5二分查找解法
javascript
function findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
let left = 0;
let right = m;
while (left <= right) {
const partitionX = Math.floor((left + right) / 2);
const partitionY = Math.floor((m + n + 1) / 2) - partitionX;
const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
const minRightX = partitionX === m ? Infinity : nums1[partitionX];
const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
const minRightY = partitionY === n ? Infinity : nums2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
// 找到正确的分割点
if ((m + n) % 2 === 0) {
return (Math.max(maxLeftX, maxLeftY) +
Math.min(minRightX, minRightY)) / 2;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
right = partitionX - 1;
} else {
left = partitionX + 1;
}
}
}思路详解 💡
二分查找思路:
- 在较短的数组上进行二分查找
- 保证左半部分和右半部分的元素个数相等
- 确保左半部分的最大值小于等于右半部分的最小值
- 时间复杂度O(log(min(m,n)))，空间复杂度O(1)
关键点:
- 处理边界情况
- 考虑奇偶数长度的不同处理方式
- 使用无穷大/无穷小处理边界值
22. 寻找峰值
题目描述 📝 峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
示例:
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2
输入：nums = [1,2,1,3,5,6,4]
输出：5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。二分查找解法
javascript
function findPeakElement(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
// 如果中间元素小于右边元素，峰值在右半部分
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
// 否则峰值在左半部分（包括mid）
right = mid;
}
}
return left;
}思路详解 💡
二分查找思路:
- 利用数组两端是负无穷的特性
- 通过比较中间元素与其右邻居的大小关系
- 沿着上升的方向搜索，必定能找到峰值
- 时间复杂度O(logn)，空间复杂度O(1)
证明正确性:
- 如果mid < mid+1，右边必定存在峰值
- 如果mid > mid+1，左边必定存在峰值
- 由于边界是负无穷，必定存在至少一个峰值
📚 二分查找技巧总结
常见二分查找类型:
- 标准二分查找
- 寻找左边界
- 寻找右边界
- 旋转数组二分
- 二分答案
关键点:
- 确定搜索区间
- 处理边界条件
- 避免死循环
- 处理重复元素
实现要点:
- 使用 left + (right - left) / 2 避免溢出
- 考虑是否需要包含边界
- 循环条件的选择（<= 还是 <）
- 更新区间的方式
🔄 双指针专题
23. 三数之和
题目描述 📝 给你一个整数数组 nums，判断是否存在三个元素 a，b，c ，使得 a + b + c = 0。请找出所有和为 0 且不重复的三元组。
示例:
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
输入：nums = []
输出：[]优化解法
javascript
function threeSum(nums) {
const result = [];
// 先排序,便于去重和使用双指针
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
// 跳过重复元素
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// 跳过重复元素
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}性能优化要点 💡
排序优化:
- 先排序使得相同元素相邻,便于去重
- 排序后可以使用双指针降低时间复杂度
- 时间复杂度从O(n³)降至O(n²)
剪枝优化:
- 跳过重复元素避免重复计算
- 当nums[i] > 0时可以直接break
- 当nums[i] + nums[left] > 0时可以break内层循环
24. 滑动窗口最大值
题目描述 📝 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
示例:
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7单调队列优化解法
javascript
function maxSlidingWindow(nums, k) {
const result = [];
const deque = []; // 存储下标
for (let i = 0; i < nums.length; i++) {
// 移除队列中超出窗口范围的元素
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 移除队列中所有小于当前元素的值
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
// 当窗口形成后,记录最大值
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}性能优化要点 💡
单调队列的优势:
- 维护一个递减的队列
- 队首始终是当前窗口的最大值
- 时间复杂度从O(nk)优化到O(n)
实现细节:
- 使用双端队列存储下标而不是值
- 及时移除过期和无用的元素
- 保持队列的单调性
25. LRU缓存
题目描述 📝 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。
获取数据 get(key) - 如果关键字存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据，从而为新的数据留出空间。
示例:
javascript
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4优化实现
javascript
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
// 更新位置
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
// 如果key存在,先删除
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 如果缓存满了,删除最久未使用的
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
this.cache.set(key, value);
}
}性能优化要点 💡
使用Map的优势:
- Map保持插入顺序
- O(1)的查找和删除操作
- 内置的size属性方便控制容量
实现细节:
- get和put操作都需要更新使用顺序
- 容量满时删除最早的元素
- 避免重复代码
26. 最小栈
题目描述 📝 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
示例:
javascript
const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -2优化实现
javascript
class MinStack {
constructor() {
this.stack = [];
this.minStack = []; // 辅助栈,存储最小值
}
push(x) {
this.stack.push(x);
// 如果辅助栈为空或新元素小于等于当前最小值,则入栈
if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(x);
}
}
pop() {
// 如果弹出的元素是当前最小值,辅助栈也要弹出
if (this.stack.pop() === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}性能优化要点 💡
辅助栈的设计:
- 同步维护最小值栈
- 只在必要时压入新的最小值
- 保证getMin操作O(1)时间复杂度
空间优化:
- 可以只存储差值,节省空间
- 使用单个变量记录最小值
- 通过计算还原原始值
📚 优化技巧总结
数据结构选择:
- 根据操作特点选择合适的数据结构
- 考虑时间和空间的平衡
- 利用内置数据结构的特性
算法优化方向:
- 减少不必要的遍历
- 利用问题特性进行剪枝
- 空间换时间的权衡
代码实现优化:
- 提取公共逻辑
- 使用合适的变量名和注释
- 处理边界情况
📝 字符串算法专题
29. 最长回文子串
题目描述 📝 给你一个字符串 s，找到 s 中最长的回文子串。
示例:
输入：s = "babad"
输出："bab"
解释："aba" 也是一个有效答案。
输入：s = "cbbd"
输出："bb"中心扩展法优化实现
javascript
function longestPalindrome(s) {
if (s.length < 2) return s;
let start = 0, maxLength = 1;
function expandAroundCenter(left, right) {
// 从中心向两边扩展
while (left >= 0 && right < s.length && s[left] === s[right]) {
const currentLength = right - left + 1;
if (currentLength > maxLength) {
start = left;
maxLength = currentLength;
}
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // 奇数长度
expandAroundCenter(i, i + 1); // 偶数长度
}
return s.substring(start, start + maxLength);
}Manacher算法实现(更优)
javascript
function longestPalindrome(s) {
// 预处理字符串
const t = '#' + s.split('').join('#') + '#';
const n = t.length;
const p = new Array(n).fill(0); // 回文半径数组
let center = 0, maxRight = 0;
let maxLen = 0, start = 0;
for (let i = 0; i < n; i++) {
if (i < maxRight) {
p[i] = Math.min(maxRight - i, p[2 * center - i]);
}
// 中心扩展
let left = i - (p[i] + 1);
let right = i + (p[i] + 1);
while (left >= 0 && right < n && t[left] === t[right]) {
p[i]++;
left--;
right++;
}
// 更新中心点和最右边界
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
// 更新最长回文子串
if (p[i] > maxLen) {
maxLen = p[i];
start = Math.floor((i - maxLen) / 2);
}
}
return s.substring(start, start + maxLen);
}性能优化要点 💡
中心扩展法优化:
- 避免子串拷贝,只记录起始位置和长度
- 同时处理奇偶长度的情况
- 时间复杂度O(n²)
Manacher算法优化:
- 利用已有回文信息避免重复计算
- 统一奇偶长度的处理
- 时间复杂度优化到O(n)
30. 字符串匹配(KMP算法)
题目描述 📝 实现 strStr() 函数，找出字符串 haystack 中第一个匹配整个字符串 needle 的子串的起始位置。如果不存在，则返回 -1。
示例:
输入：haystack = "hello", needle = "ll"
输出：2
输入：haystack = "aaaaa", needle = "bba"
输出：-1KMP算法优化实现
javascript
function strStr(haystack, needle) {
if (needle === '') return 0;
// 构建next数组
const next = buildNext(needle);
let i = 0, j = 0;
while (i < haystack.length && j < needle.length) {
if (j === -1 || haystack[i] === needle[j]) {
i++;
j++;
} else {
j = next[j];
}
}
return j === needle.length ? i - j : -1;
}
function buildNext(pattern) {
const next = [-1];
let i = 0, j = -1;
while (i < pattern.length - 1) {
if (j === -1 || pattern[i] === pattern[j]) {
i++;
j++;
// 优化next数组
if (pattern[i] !== pattern[j]) {
next[i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j];
}
}
return next;
}性能优化要点 💡
next数组优化:
- 处理重复字符的情况
- 减少不必要的比较
- 优化失配时的回退位置
匹配过程优化:
- 避免回溯主串指针
- 利用已匹配的信息
- 时间复杂度O(m+n)
31. 数组中的第K个最大元素
题目描述 📝 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
示例:
输入: [3,2,1,5,6,4], k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4快速选择算法优化实现
javascript
function findKthLargest(nums, k) {
// 转换为查找第n-k+1小的元素
k = nums.length - k;
function quickSelect(left, right) {
if (left === right) return nums[left];
// 随机选择基准点
const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
const pivot = nums[pivotIndex];
// 将基准点交换到末尾
[nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
let i = left;
for (let j = left; j < right; j++) {
if (nums[j] <= pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
}
}
[nums[i], nums[right]] = [nums[right], nums[i]];
// 根据i与k的关系决定递归方向
if (i === k) return nums[i];
else if (i < k) return quickSelect(i + 1, right);
else return quickSelect(left, i - 1);
}
return quickSelect(0, nums.length - 1);
}堆排序实现(适用于数据流)
javascript
class MinHeap {
constructor(k) {
this.heap = [];
this.k = k;
}
push(val) {
if (this.heap.length < this.k) {
this.heap.push(val);
this.siftUp(this.heap.length - 1);
} else if (val > this.heap[0]) {
this.heap[0] = val;
this.siftDown(0);
}
}
siftUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex] > this.heap[index]) {
[this.heap[parentIndex], this.heap[index]] =
[this.heap[index], this.heap[parentIndex]];
index = parentIndex;
} else {
break;
}
}
}
siftDown(index) {
while (2 * index + 1 < this.heap.length) {
let minIndex = 2 * index + 1;
if (minIndex + 1 < this.heap.length &&
this.heap[minIndex + 1] < this.heap[minIndex]) {
minIndex++;
}
if (this.heap[index] > this.heap[minIndex]) {
[this.heap[index], this.heap[minIndex]] =
[this.heap[minIndex], this.heap[index]];
index = minIndex;
} else {
break;
}
}
}
getKthLargest() {
return this.heap[0];
}
}
function findKthLargest(nums, k) {
const minHeap = new MinHeap(k);
for (const num of nums) {
minHeap.push(num);
}
return minHeap.getKthLargest();
}性能优化要点 💡
快速选择优化:
- 随机选择基准点避免最坏情况
- 只需要递归一半区间
- 平均时间复杂度O(n)
堆排序优化:
- 维护大小为k的小顶堆
- 适用于数据流场景
- 时间复杂度O(nlogk)
📚 字符串和数组算法技巧总结
常见优化方向:
- 使用合适的数据结构
- 预处理数据
- 空间换时间
- 利用问题特性
实现要点:
- 处理边界情况
- 优化循环结构
- 减少不必要的计算
- 合理使用缓存
性能考虑:
- 时间复杂度优化
- 空间使用优化
- 算法稳定性
- 代码可维护性
📚 扩展阅读
💡 Tips: 刷题时要注意总结思路，培养算法思维，不要死记硬背。建议从简单题开始，循序渐进。