数组与链表核心技巧 🚀
一、双指针技巧精讲 👆
1. 什么是双指针? 🤔
想象你在读一本书:
- 一个手指指着当前页的第一行(左指针)
- 另一个手指指着最后一行(右指针)
- 通过移动这两个手指来定位要找的内容
这就是双指针技巧的核心思想 - 通过两个指针的配合来解决问题。
💡 重要提示：双指针用在数组题目时,数组必须是有序的。这就像在字典中查找单词,只有按字母排序才能通过移动手指快速定位。
2. 链表中的双指针应用
2.1 虚拟头节点技巧
虚拟头节点就像是链表的"引导员",它站在链表的最前面:
- 统一了所有节点的操作逻辑
- 不用再特殊处理第一个节点
- 让代码更简洁优雅
js
/**
* LeetCode 86: 分隔链表
* @param {ListNode} head - 链表头节点
* @param {number} x - 分隔的基准值
* @return {ListNode} - 重组后的链表
*/
function partition(head, x) {
// 创建两个虚拟头节点
const dummy1 = new ListNode(-1); // 存放小于x的节点
const dummy2 = new ListNode(-1); // 存放大于等于x的节点
// 两个工作指针,就像两个分拣员
let p1 = dummy1; // 负责小于x的链表
let p2 = dummy2; // 负责大于等于x的链表
// 遍历原链表,像流水线一样处理每个节点
let p = head;
while (p !== null) {
// 根据节点值进行分类
if (p.val < x) {
p1.next = p;
p1 = p1.next;
} else {
p2.next = p;
p2 = p2.next;
}
// 断开原链接,准备处理下一个
const temp = p.next;
p.next = null;
p = temp;
}
// 连接两个链表,就像拼接两条绳子
p1.next = dummy2.next;
return dummy1.next;
}2.2 快慢指针技巧
想象两个人在跑步:
- 小明速度快,一次跑两步
- 小红速度慢,一次跑一步
- 他们之间的关系可以帮我们解决很多问题
a) 寻找链表中点
js
/**
* 查找链表的中点
* @param {ListNode} head - 链表头节点
* @return {ListNode} - 中点节点
*/
function findMiddle(head) {
// 快慢指针初始化
let slow = head; // 慢指针小红
let fast = head; // 快指针小明
// 当小明能跑时,就继续跑
while (fast !== null && fast.next !== null) {
slow = slow.next; // 小红跑1步
fast = fast.next.next; // 小明跑2步
}
// 当小明跑到终点时,小红正好在中点
return slow;
}b) 判断链表是否有环
js
/**
* 检测链表是否有环
* @param {ListNode} head - 链表头节点
* @return {boolean} - 是否存在环
*/
function hasCycle(head) {
// 快慢指针初始化
let slow = head;
let fast = head;
// 想象在跑圈
while (fast !== null && fast.next !== null) {
slow = slow.next; // 慢跑者
fast = fast.next.next; // 快跑者
// 如果是在跑圈,快跑者总会追上慢跑者
if (slow === fast) {
return true;
}
}
// 如果快跑者到终点了,说明不是环形跑道
return false;
}3. 实战应用场景 💡
在前端开发中,双指针技巧的应用场景:
- 虚拟列表优化
js
// 使用双指针维护可视区域
let start = 0; // 可视区域起点
let end = visibleCount; // 可视区域终点
function updateVisibleItems() {
// 根据滚动位置更新双指针
start = Math.floor(scrollTop / itemHeight);
end = start + visibleCount;
// 渲染可视区域的内容
renderItems(start, end);
}- 轮播图实现
js
class Carousel {
constructor() {
this.current = 0; // 当前显示的图片
this.prev = -1; // 上一张图片
}
slide() {
// 使用双指针记录图片切换状态
this.prev = this.current;
this.current = (this.current + 1) % total;
// 执行动画
animate(this.prev, this.current);
}
}4. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 数组操作 | 1. 优先考虑是否可以排序后使用双指针 |
| 2. 注意边界条件的处理 | |
| 链表操作 | 1. 使用虚拟头节点简化代码 |
| 2. 先画图理清指针关系 | |
| 代码实现 | 1. 指针命名要有意义 |
| 2. 关键步骤加注释 |
5. 常见误区提醒 ⚠️
- 忘记判断指针是否为null
- 链表操作时忘记断开原有连接
- 快慢指针初始位置设置错误
- 边界条件考虑不周全
二、滑动窗口技巧精讲 🪟
1. 什么是滑动窗口? 🤔
想象你在看风景:
- 你的视野就是一个"窗口"
- 窗口可以左右滑动来观察不同的景色
- 通过控制窗口的大小和移动来找到最佳风景
这就是滑动窗口的核心思想 - 通过维护一个可变窗口来解决子串/子数组的问题。
💡 关键点：滑动窗口通常用于处理连续的序列问题,比如:
- 寻找最长的不重复子串
- 寻找包含特定字符的最小子串
- 寻找定长子数组的最大和
2. 滑动窗口框架 📝
js
/**
* 滑动窗口算法框架
* @param {string} s - 待处理的字符串
* @return {void}
*/
function slidingWindow(s) {
// 1. 初始化窗口计数器
const window = new Map();
// 2. 定义双指针
let left = 0; // 窗口左边界
let right = 0; // 窗口右边界
// 3. 定义其他需要的变量
let valid = 0; // 窗口中的有效数据量
let start = 0; // 结果子串的起始位置
let len = Infinity; // 结果子串的长度
// 4. 移动右边界,扩大窗口
while (right < s.length) {
// 即将进入窗口的字符
const c = s[right];
right++; // 扩大窗口
// 5. 进行窗口内数据的更新
updateWindow(c);
// 6. 判断左侧窗口是否要收缩
while (windowNeedsShrink()) {
// 即将移出窗口的字符
const d = s[left];
left++; // 缩小窗口
// 7. 进行窗口内数据的更新
updateWindow(d);
}
}
}3. 实战案例：最小覆盖子串 💡
js
/**
* LeetCode 76: 最小覆盖子串
* @param {string} s - 源字符串
* @param {string} t - 目标字符串
* @return {string} - 最小覆盖子串
*/
function minWindow(s, t) {
// 1. 统计目标字符串中字符出现次数
const needs = new Map();
for (let c of t) {
needs.set(c, (needs.get(c) || 0) + 1);
}
// 2. 初始化窗口计数器
const window = new Map();
// 3. 定义变量
let left = 0, right = 0;
let valid = 0; // 已经匹配的字符数
let start = 0, len = Infinity;
// 4. 移动右边界
while (right < s.length) {
// 进入窗口的字符
const c = s[right];
right++;
// 5. 更新窗口数据
if (needs.has(c)) {
window.set(c, (window.get(c) || 0) + 1);
if (window.get(c) === needs.get(c)) {
valid++; // 字符 c 的出现次数符合要求
}
}
// 6. 判断是否需要收缩窗口
while (valid === needs.size) {
// 更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// 移出窗口的字符
const d = s[left];
left++;
// 7. 更新窗口数据
if (needs.has(d)) {
if (window.get(d) === needs.get(d)) {
valid--; // 字符 d 的出现次数不再符合要求
}
window.set(d, window.get(d) - 1);
}
}
}
return len === Infinity ? "" : s.substr(start, len);
}4. 前端实战应用 💻
- 图片懒加载
js
class LazyLoader {
constructor(images) {
this.images = images;
this.windowStart = 0; // 可视区域起始位置
this.windowEnd = window.innerHeight; // 可视区域结束位置
}
checkVisible() {
this.images.forEach(img => {
const rect = img.getBoundingClientRect();
// 使用滑动窗口思想判断图片是否在可视区域
if (rect.top >= this.windowStart && rect.bottom <= this.windowEnd) {
this.loadImage(img);
}
});
}
}- 无限滚动列表
js
class InfiniteScroll {
constructor() {
this.data = [];
this.visibleWindow = {
start: 0,
size: 20 // 窗口大小
};
}
updateVisibleItems() {
// 根据滚动位置更新窗口
const scrollTop = document.scrollingElement.scrollTop;
this.visibleWindow.start = Math.floor(scrollTop / itemHeight);
// 只渲染窗口内的数据
this.renderItems(
this.data.slice(
this.visibleWindow.start,
this.visibleWindow.start + this.visibleWindow.size
)
);
}
}5. 性能优化建议 ⚡
| 优化点 | 具体建议 |
|---|---|
| 空间复杂度 | 1. 使用Map/Set代替数组存储窗口数据 |
| 2. 及时清理不需要的窗口数据 | |
| 时间复杂度 | 1. 避免不必要的窗口扩张和收缩 |
| 2. 合理设置窗口的初始大小 | |
| 代码优化 | 1. 抽象公共的窗口操作函数 |
| 2. 使用常量存储固定的窗口大小 |
6. 常见误区 ⚠️
- 窗口更新时机选择错误
- 忘记维护窗口内的计数器
- 窗口收缩条件设置不当
- 边界条件处理不当
三、单调栈技巧精讲 📚
1. 什么是单调栈？🤔
想象你在看一排人站队：
- 如果按照身高从矮到高排，这就是一个单调递增的队伍
- 如果按照身高从高到矮排，这就是一个单调递减的队伍
- 单调栈就是维护这样一个单调序列的数据结构
💡 核心特点：栈内元素始终保持单调递增或单调递减。当新元素破坏这个单调性时，就需要弹出栈顶元素，直到恢复单调性。
2. 单调栈的应用场景
主要用于解决以下类型的问题：
- 寻找下一个更大元素
- 寻找下一个更小元素
- 寻找前一个更大元素
- 寻找前一个更小元素
3. 经典问题：每日温度 🌡️
js
/**
* LeetCode 739: 每日温度
* @param {number[]} temperatures - 温度数组
* @return {number[]} - 等待天数数组
*/
function dailyTemperatures(temperatures) {
const n = temperatures.length;
// 存放结果：对于每个温度，需要等几天才能遇到更高的温度
const res = new Array(n).fill(0);
// 单调栈：存放温度的索引，栈内温度单调递减
const stack = [];
// 从左到右遍历温度数组
for (let i = 0; i < n; i++) {
// 当前温度
const currTemp = temperatures[i];
// 如果栈不为空且当前温度大于栈顶温度
// 说明找到了一个"更暖和的日子"
while (
stack.length > 0 &&
currTemp > temperatures[stack[stack.length - 1]]
) {
// 获取栈顶温度的索引
const prevIndex = stack.pop();
// 计算等待天数
res[prevIndex] = i - prevIndex;
}
// 将当前温度的索引入栈
stack.push(i);
}
return res;
}
// 使用示例
const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
console.log(dailyTemperatures(temperatures));
// 输出: [1, 1, 4, 2, 1, 1, 0, 0]4. 接雨水问题 🌧️
js
/**
* LeetCode 42: 接雨水
* @param {number[]} height - 柱子高度数组
* @return {number} - 可以接的雨水总量
*/
function trap(height) {
let stack = []; // 单调递减栈，存放柱子的索引
let total = 0; // 总雨水量
// 遍历每个柱子
for (let i = 0; i < height.length; i++) {
// 当前柱子可以接住之前的水
while (
stack.length > 0 &&
height[i] > height[stack[stack.length - 1]]
) {
// 获取凹槽底部的索引
const bottom = stack.pop();
// 如果栈空了，说明没有左边界，无法接水
if (stack.length === 0) break;
// 计算凹槽的左右边界
const left = stack[stack.length - 1];
const right = i;
// 计算水的高度和宽度
const h = Math.min(height[left], height[right]) - height[bottom];
const w = right - left - 1;
// 累加这个凹槽能接的水
total += h * w;
}
stack.push(i);
}
return total;
}5. 前端实战应用 💻
- 股票价格监控
js
class StockMonitor {
constructor() {
this.priceStack = []; // 价格单调栈
this.timeStack = []; // 对应的时间戳
}
// 监控价格变化
updatePrice(price, timestamp) {
// 找到第一个比当前价格高的历史价格
while (
this.priceStack.length &&
price > this.priceStack[this.priceStack.length - 1]
) {
this.priceStack.pop();
const prevTime = this.timeStack.pop();
this.notifyPriceIncrease(prevTime, timestamp);
}
this.priceStack.push(price);
this.timeStack.push(timestamp);
}
}- 任务优先级队列
js
class TaskQueue {
constructor() {
this.priorityStack = []; // 优先级单调递减栈
this.tasks = []; // 对应的任务
}
addTask(task, priority) {
// 高优先级任务会打断之前的低优先级任务
while (
this.priorityStack.length &&
priority > this.priorityStack[this.priorityStack.length - 1]
) {
this.priorityStack.pop();
const prevTask = this.tasks.pop();
this.pauseTask(prevTask);
}
this.priorityStack.push(priority);
this.tasks.push(task);
this.executeTask(task);
}
}6. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 空间使用 | 1. 只存储必要的信息（如索引而非完整元素） |
| 2. 及时清理不再需要的栈元素 | |
| 时间效率 | 1. 选择合适的遍历方向（正向/反向） |
| 2. 避免不必要的栈操作 | |
| 代码实现 | 1. 使用数组模拟栈操作 |
| 2. 预先分配合适的数组大小 |
7. 常见误区 ⚠️
- 栈的单调性选择错误（递增/递减）
- 忘记处理栈为空的情况
- 入栈/出栈时机判断失误
- 结果计算逻辑错误
8. 练习题推荐 📝
- LeetCode 496: 下一个更大元素 I
- LeetCode 503: 下一个更大元素 II
- LeetCode 84: 柱状图中最大的矩形
- LeetCode 85: 最大矩形
四、前缀和技巧精讲 📊
1. 什么是前缀和？🤔
想象你是一个会计：
- 需要经常计算从1月到某个月的总收入
- 与其每次都重新计算，不如提前记录每个月的累计收入
- 这就是前缀和的思想：提前计算累加值，以便快速查询区间和
💡 核心思想：
prefix[i]表示数组nums[0..i-1]的累加和。通过prefix[j] - prefix[i]可以快速得到nums[i..j-1]的区间和。
2. 一维前缀和实现
js
/**
* 前缀和数组构建与查询
*/
class PrefixSum {
/**
* 构建前缀和数组
* @param {number[]} nums - 原始数组
*/
constructor(nums) {
const n = nums.length;
// 前缀和数组比原数组多一位，便于计算
this.prefix = new Array(n + 1).fill(0);
// 构建前缀和数组
for (let i = 1; i <= n; i++) {
this.prefix[i] = this.prefix[i-1] + nums[i-1];
}
}
/**
* 查询闭区间 [i,j] 的区间和
* @param {number} i - 起始索引
* @param {number} j - 结束索引
* @return {number} - 区间和
*/
query(i, j) {
return this.prefix[j + 1] - this.prefix[i];
}
}
// 使用示例
const nums = [3, 5, 2, -2, 4, 1];
const prefixSum = new PrefixSum(nums);
console.log(prefixSum.query(0, 2)); // 输出: 10 (3+5+2)
console.log(prefixSum.query(2, 5)); // 输出: 5 (2-2+4+1)3. 二维前缀和实现
js
/**
* 二维前缀和数组构建与查询
*/
class PrefixSum2D {
/**
* 构建二维前缀和数组
* @param {number[][]} matrix - 原始矩阵
*/
constructor(matrix) {
if (matrix.length === 0 || matrix[0].length === 0) return;
const m = matrix.length;
const n = matrix[0].length;
// 构建(m+1)*(n+1)的前缀和数组，便于计算
this.prefix = Array.from(
{length: m + 1},
() => new Array(n + 1).fill(0)
);
// 计算二维前缀和
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
this.prefix[i][j] = (
this.prefix[i-1][j] +
this.prefix[i][j-1] -
this.prefix[i-1][j-1] +
matrix[i-1][j-1]
);
}
}
}
/**
* 查询子矩阵的和 [(r1,c1), (r2,c2)]
* @param {number} r1 - 左上角行索引
* @param {number} c1 - 左上角列索引
* @param {number} r2 - 右下角行索引
* @param {number} c2 - 右下角列索引
* @return {number} - 子矩阵的和
*/
sumRegion(r1, c1, r2, c2) {
return (
this.prefix[r2 + 1][c2 + 1] -
this.prefix[r2 + 1][c1] -
this.prefix[r1][c2 + 1] +
this.prefix[r1][c1]
);
}
}4. 前端实战应用 💻
- 性能监控数据统计
js
class PerformanceMonitor {
constructor() {
this.timeData = [];
this.prefixSum = null;
}
// 记录性能数据
record(timeSpent) {
this.timeData.push(timeSpent);
// 重新构建前缀和
this.prefixSum = new PrefixSum(this.timeData);
}
// 查询某段时间的性能统计
getTimeRange(start, end) {
return {
totalTime: this.prefixSum.query(start, end),
avgTime: this.prefixSum.query(start, end) / (end - start + 1)
};
}
}- 图片像素数据处理
js
class ImageProcessor {
constructor(pixelData) {
// 构建像素数据的二维前缀和
this.prefixSum2D = new PrefixSum2D(pixelData);
}
// 计算区域平均亮度
getRegionBrightness(x1, y1, x2, y2) {
const sum = this.prefixSum2D.sumRegion(x1, y1, x2, y2);
const area = (x2 - x1 + 1) * (y2 - y1 + 1);
return sum / area;
}
}5. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 空间优化 | 1. 对于静态数据，一次性构建前缀和 |
| 2. 对于动态数据，权衡更新成本 | |
| 时间优化 | 1. 避免频繁重建前缀和数组 |
| 2. 合理设计查询接口 | |
| 内存使用 | 1. 及时释放不需要的前缀和数组 |
| 2. 考虑使用类型数组优化 |
6. 常见误区 ⚠️
- 忽略数组越界问题
- 前缀和数组大小设置错误
- 区间计算时索引错误
- 更新操作处理不当
7. 练习题推荐 📝
- LeetCode 303: 区域和检索 - 数组不可变
- LeetCode 304: 二维区域和检索 - 矩阵不可变
- LeetCode 560: 和为K的子数组
- LeetCode 1074: 元素和为目标值的子矩阵数量
五、差分数组技巧精讲 📊
1. 什么是差分数组？🤔
想象你是一个人事经理：
- 每个月都有员工入职和离职
- 你需要知道每个月的员工总数变化
- 与其每次都重新统计，不如记录每月的人数变化（增减）
这就是差分数组的思想：记录相邻元素的差值，用于高效处理区间增减操作。
💡 核心思想：
diff[i]表示nums[i]与nums[i-1]的差值。当我们要对区间[i,j]进行增减操作时，只需要修改diff[i]和diff[j+1]两个位置。
2. 差分数组实现
js
/**
* 差分数组的实现
*/
class Difference {
/**
* 构造差分数组
* @param {number[]} nums - 原始数组
*/
constructor(nums) {
// 差分数组
this.diff = new Array(nums.length);
// 构建差分数组
this.diff[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
this.diff[i] = nums[i] - nums[i - 1];
}
}
/**
* 对区间[i,j]增加val
* @param {number} i - 起始索引
* @param {number} j - 结束索引
* @param {number} val - 增加的值
*/
increment(i, j, val) {
this.diff[i] += val; // 起始位置增加val
if (j + 1 < this.diff.length) {
this.diff[j + 1] -= val; // 结束位置后减少val
}
}
/**
* 返回结果数组
* @return {number[]} - 结果数组
*/
result() {
const res = new Array(this.diff.length);
res[0] = this.diff[0];
// 根据差分数组还原结果
for (let i = 1; i < this.diff.length; i++) {
res[i] = res[i - 1] + this.diff[i];
}
return res;
}
}
// 使用示例
const nums = [8, 2, 6, 3, 1];
const diff = new Difference(nums);
diff.increment(1, 3, 2); // 对区间[1,3]增加2
console.log(diff.result()); // [8, 4, 8, 5, 1]3. 前端实战应用 💻
- 航班预订统计
js
class FlightBooking {
constructor(n) {
this.diff = new Difference(new Array(n).fill(0));
}
// 预订航班
book(start, end, seats) {
// 对区间[start, end]增加seats个座位
this.diff.increment(start, end, seats);
}
// 获取当前航班预订情况
getBookings() {
return this.diff.result();
}
}- 动画帧变化计算
js
class AnimationController {
constructor(duration) {
this.diff = new Difference(new Array(duration).fill(0));
}
// 添加动画效果
addEffect(startFrame, endFrame, value) {
this.diff.increment(startFrame, endFrame, value);
}
// 获取每一帧的状态
getFrameStates() {
return this.diff.result();
}
}4. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 空间优化 | 1. 原地修改差分数组 |
| 2. 避免不必要的数组拷贝 | |
| 时间优化 | 1. 批量处理区间操作 |
| 2. 延迟计算结果数组 | |
| 实现优化 | 1. 使用类型数组提升性能 |
| 2. 预分配合适的数组大小 |
5. 常见误区 ⚠️
- 差分数组大小设置错误
- 区间边界处理不当
- 忘记处理负数情况
- 结果还原时计算错误
6. 实战技巧 💡
- 处理区间重叠
js
// 合并重叠区间的差分处理
function mergeIntervals(intervals, values) {
const diff = new Difference(new Array(maxEnd + 1).fill(0));
intervals.forEach((interval, i) => {
diff.increment(interval[0], interval[1], values[i]);
});
return diff.result();
}- 处理循环数组
js
// 处理循环数组的差分
function handleCircularArray(nums, operations) {
// 复制一份数组处理循环情况
const extendedDiff = new Difference([...nums, ...nums]);
operations.forEach(op => {
const [start, end, val] = op;
if (start <= end) {
extendedDiff.increment(start, end, val);
} else {
// 处理跨越数组末尾的情况
extendedDiff.increment(start, nums.length - 1, val);
extendedDiff.increment(0, end, val);
}
});
return extendedDiff.result().slice(0, nums.length);
}7. 练习题推荐 📝
- LeetCode 1109: 航班预订统计
- LeetCode 1094: 拼车
- LeetCode 1589: 所有排列中的最大和
- LeetCode 370: 区间加法
六、二维数组遍历技巧精讲 🎯
1. 创建二维数组 🏗️
💡 在JavaScript中创建二维数组需要特别注意引用类型的陷阱。
1.1 常见创建方法对比
js
/**
* 方法1: 使用 fill + for循环（推荐）
* 优点：避免引用类型陷阱
* 缺点：代码较长
*/
function createArray1(rows, cols) {
let arr = new Array(rows).fill(0);
for (let i = 0; i < rows; i++) {
arr[i] = new Array(cols).fill(1);
}
return arr;
}
/**
* 方法2: 两层for循环（推荐）
* 优点：最直观，最安全
* 缺点：代码较长
*/
function createArray2(rows, cols) {
let arr = new Array();
for (let i = 0; i < rows; i++) {
arr[i] = new Array();
for (let j = 0; j < cols; j++) {
arr[i][j] = 1;
}
}
return arr;
}
/**
* 方法3: Array.from + fill（推荐）
* 优点：代码简洁
* 缺点：需要理解Array.from的用法
*/
function createArray3(rows, cols) {
return Array.from(new Array(rows), () => new Array(cols).fill(1));
}
/**
* 方法4: fill + map（不推荐）
* 警告：可能导致引用类型问题
*/
function createArray4(rows, cols) {
return new Array(rows).fill(new Array(cols).fill(0));
}1.2 引用类型陷阱示例
js
// ❌ 错误示例
const matrix = new Array(3).fill(new Array(3).fill(0));
matrix[0][0] = 1;
console.log(matrix);
// 输出: [[1,0,0], [1,0,0], [1,0,0]]
// 所有行都被修改，因为它们引用同一个数组！
// ✅ 正确示例
const matrix = Array.from(new Array(3), () => new Array(3).fill(0));
matrix[0][0] = 1;
console.log(matrix);
// 输出: [[1,0,0], [0,0,0], [0,0,0]]2. 遍历技巧 🔄
2.1 常见遍历模式
js
/**
* 1. 按行遍历（最常用）
* @param {number[][]} matrix
*/
function traverseByRow(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
console.log(matrix[i][j]);
}
}
}
/**
* 2. 按列遍历
* @param {number[][]} matrix
*/
function traverseByCol(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for (let j = 0; j < cols; j++) {
for (let i = 0; i < rows; i++) {
console.log(matrix[i][j]);
}
}
}
/**
* 3. 对角线遍历
* @param {number[][]} matrix
*/
function traverseDiagonal(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
// 遍历主对角线及上半部分
for (let i = 0; i < rows; i++) {
let row = i, col = 0;
while (row >= 0 && col < cols) {
console.log(matrix[row][col]);
row--;
col++;
}
}
}2.2 矩阵旋转
js
/**
* 矩阵顺时针旋转90度
* @param {number[][]} matrix
*/
function rotate(matrix) {
const n = matrix.length;
// 1. 先沿对角线翻转
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] =
[matrix[j][i], matrix[i][j]];
}
}
// 2. 再左右翻转
for (let i = 0; i < n; i++) {
for (let j = 0; j < n/2; j++) {
[matrix[i][j], matrix[i][n-1-j]] =
[matrix[i][n-1-j], matrix[i][j]];
}
}
}2.3 螺旋遍历
js
/**
* 矩阵螺旋遍历
* @param {number[][]} matrix
* @return {number[]}
*/
function spiralOrder(matrix) {
if (!matrix.length) return [];
const result = [];
let top = 0,
bottom = matrix.length - 1,
left = 0,
right = matrix[0].length - 1;
while (result.length < matrix.length * matrix[0].length) {
// 向右遍历
if (top <= bottom) {
for (let i = left; i <= right; i++) {
result.push(matrix[top][i]);
}
top++;
}
// 向下遍历
if (left <= right) {
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--;
}
// 向左遍历
if (top <= bottom) {
for (let i = right; i >= left; i--) {
result.push(matrix[bottom][i]);
}
bottom--;
}
// 向上遍历
if (left <= right) {
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++;
}
}
return result;
}3. 前端实战应用 💻
- 图片处理
js
class ImageMatrix {
constructor(imageData) {
this.matrix = this.createImageMatrix(imageData);
}
// 图片旋转
rotate90Degrees() {
rotate(this.matrix);
return this;
}
// 图片区域裁剪
crop(startRow, startCol, endRow, endCol) {
const result = [];
for (let i = startRow; i <= endRow; i++) {
result.push(
this.matrix[i].slice(startCol, endCol + 1)
);
}
return result;
}
}- 游戏地图
js
class GameMap {
constructor(rows, cols) {
this.map = Array.from(
new Array(rows),
() => new Array(cols).fill(0)
);
}
// 获取某点周围的元素
getSurrounding(row, col) {
const directions = [
[-1,-1], [-1,0], [-1,1],
[0,-1], [0,1],
[1,-1], [1,0], [1,1]
];
return directions
.map(([dx, dy]) => {
const newRow = row + dx;
const newCol = col + dy;
if (this.isValid(newRow, newCol)) {
return this.map[newRow][newCol];
}
return null;
})
.filter(val => val !== null);
}
isValid(row, col) {
return row >= 0 &&
row < this.map.length &&
col >= 0 &&
col < this.map[0].length;
}
}4. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 内存优化 | 1. 使用类型数组(TypedArray) |
| 2. 及时释放不用的数组空间 | |
| 遍历优化 | 1. 选择合适的遍历顺序 |
| 2. 避免重复遍历 | |
| 边界处理 | 1. 统一的边界检查函数 |
| 2. 预处理边界条件 |
5. 常见误区 ⚠️
- 创建二维数组时的引用类型问题
- 边界条件处理不当
- 行列索引混淆
- 遍历顺序选择不当
6. 练习题推荐 📝
- LeetCode 48: 旋转图像
- LeetCode 54: 螺旋矩阵
- LeetCode 73: 矩阵置零
- LeetCode 240: 搜索二维矩阵 II
七、堆（Heap）数据结构精讲 🌳
1. 什么是堆？🤔
想象一个公司的组织架构：
- CEO在最顶层
- 经理在中层
- 普通员工在底层 这就像一个最大堆，每个上级都比下级"大"。
💡 堆是一个完全二叉树，分为最大堆和最小堆：
- 最大堆：父节点总是大于等于子节点
- 最小堆：父节点总是小于等于子节点
2. 堆的实现
2.1 最大堆实现
js
/**
* 最大堆的实现
*/
class MaxHeap {
constructor() {
this.heap = [];
}
/**
* 获取父节点索引
* @param {number} i - 当前节点索引
* @return {number} - 父节点索引
*/
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
/**
* 获取左子节点索引
* @param {number} i - 当前节点索引
* @return {number} - 左子节点索引
*/
getLeftIndex(i) {
return 2 * i + 1;
}
/**
* 获取右子节点索引
* @param {number} i - 当前节点索引
* @return {number} - 右子节点索引
*/
getRightIndex(i) {
return 2 * i + 2;
}
/**
* 交换两个节点
* @param {number} i1 - 第一个节点索引
* @param {number} i2 - 第二个节点索引
*/
swap(i1, i2) {
[this.heap[i1], this.heap[i2]] =
[this.heap[i2], this.heap[i1]];
}
/**
* 向上调整
* @param {number} index - 需要调整的节点索引
*/
shiftUp(index) {
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] >= this.heap[index]) {
break;
}
this.swap(index, parentIndex);
index = parentIndex;
}
}
/**
* 向下调整
* @param {number} index - 需要调整的节点索引
*/
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
let largest = index;
if (leftIndex < this.heap.length &&
this.heap[leftIndex] > this.heap[largest]) {
largest = leftIndex;
}
if (rightIndex < this.heap.length &&
this.heap[rightIndex] > this.heap[largest]) {
largest = rightIndex;
}
if (largest !== index) {
this.swap(index, largest);
this.shiftDown(largest);
}
}
/**
* 插入新值
* @param {number} value - 要插入的值
*/
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
/**
* 删除并返回最大值
* @return {number} - 堆顶的最大值
*/
extractMax() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop();
this.shiftDown(0);
return max;
}
}3. 前端实战应用 💻
- 任务优先级队列
js
class PriorityTaskQueue {
constructor() {
this.maxHeap = new MaxHeap();
}
/**
* 添加任务
* @param {Object} task - 任务对象
* @param {number} priority - 优先级
*/
addTask(task, priority) {
this.maxHeap.insert({
task,
priority
});
}
/**
* 执行最高优先级任务
*/
executeHighestPriorityTask() {
const taskObj = this.maxHeap.extractMax();
if (taskObj) {
console.log(`执行任务，优先级：${taskObj.priority}`);
taskObj.task();
}
}
}- 前K个最热门商品
js
class TopKProducts {
constructor(k) {
this.k = k;
this.minHeap = new MinHeap();
}
/**
* 添加商品
* @param {Object} product - 商品对象
* @param {number} heat - 热度值
*/
addProduct(product, heat) {
if (this.minHeap.size() < this.k) {
this.minHeap.insert({ product, heat });
} else if (heat > this.minHeap.peek().heat) {
this.minHeap.extractMin();
this.minHeap.insert({ product, heat });
}
}
/**
* 获取最热门的K个商品
*/
getTopK() {
return this.minHeap.heap
.map(item => item.product)
.sort((a, b) => b.heat - a.heat);
}
}4. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 空间优化 | 1. 使用数组实现而非指针 |
| 2. 预分配合适的数组大小 | |
| 时间优化 | 1. 批量建堆而非逐个插入 |
| 2. 避免频繁的堆调整 | |
| 实现优化 | 1. 使用迭代代替递归 |
| 2. 优化比较函数 |
5. 常见误区 ⚠️
- 混淆最大堆和最小堆的性质
- 忘记维护堆的完全二叉树特性
- 堆化过程中的索引计算错误
- 删除操作后忘记调整堆
6. 练习题推荐 📝
- LeetCode 215: 数组中的第K个最大元素
- LeetCode 347: 前K个高频元素
- LeetCode 23: 合并K个排序链表
- LeetCode 295: 数据流的中位数
八、算法技巧精讲 🎯
1. 预处理数组技巧 📊
💡 核心思想：空间换时间，通过提前计算和存储信息来加速查询。
js
/**
* 示例：前缀和预处理
* 场景：频繁查询数组区间和
*/
class RangeSum {
constructor(nums) {
this.preSum = new Array(nums.length + 1).fill(0);
// 预处理前缀和
for (let i = 0; i < nums.length; i++) {
this.preSum[i + 1] = this.preSum[i] + nums[i];
}
}
/**
* 查询区间和
* @param {number} left - 左边界
* @param {number} right - 右边界
* @return {number} - 区间和
*/
queryRange(left, right) {
return this.preSum[right + 1] - this.preSum[left];
}
}
// 使用示例
const rangeSum = new RangeSum([1, 2, 3, 4, 5]);
console.log(rangeSum.queryRange(1, 3)); // 输出: 9 (2+3+4)2. 等概率生成器 🎲
js
/**
* 将非等概率转换为等概率
* 核心思想：通过组合两次调用消除概率倾斜
*/
class ProbabilityGenerator {
/**
* 原始函数：以p概率返回1，1-p概率返回0
*/
random() {
return Math.random() < 0.7 ? 1 : 0; // 假设p=0.7
}
/**
* 转换为等概率0/1生成器
*/
generateEqual() {
let result;
do {
const a = this.random();
const b = this.random();
// 01组合返回0，10组合返回1
if (a === 0 && b === 1) {
result = 0;
break;
}
if (a === 1 && b === 0) {
result = 1;
break;
}
// 00和11的情况继续循环
} while (true);
return result;
}
}3. 打表法技巧 📝
js
/**
* 打表法示例：计算斐波那契数列
* 适用场景：输入范围小，计算规律明显
*/
class FibonacciTable {
constructor(maxN) {
this.table = new Map();
// 预计算所有可能的结果
this.generateTable(maxN);
}
generateTable(n) {
let a = 0, b = 1;
this.table.set(0, a);
this.table.set(1, b);
for (let i = 2; i <= n; i++) {
const c = (a + b) % 1000000007;
this.table.set(i, c);
a = b;
b = c;
}
}
/**
* O(1)时间复杂度获取结果
*/
getFib(n) {
return this.table.get(n);
}
}4. 子串子数组技巧 📊
js
/**
* 示例：最长递增子数组
* 核心思想：以每个位置结尾的最优解
*/
function longestIncreasingSubarray(nums) {
if (!nums.length) return 0;
// dp[i]表示以nums[i]结尾的最长递增子数组长度
const dp = new Array(nums.length).fill(1);
let maxLen = 1;
for (let i = 1; i < nums.length; i++) {
// 如果当前数字大于前一个数字，可以接在前面的子数组后面
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}5. Map的巧妙应用 🗺️
js
/**
* 示例：两数之和
* 核心思想：将查找问题转化为求差问题
*/
function twoSum(nums, target) {
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.set(nums[i], i);
}
return [];
}
/**
* 示例：连续子数组和
* 核心思想：前缀和 + Map
*/
function checkSubarraySum(nums, k) {
const map = new Map();
map.set(0, -1);
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
// 当k不为0时，我们关心的是余数
const remainder = k !== 0 ? sum % k : sum;
if (map.has(remainder)) {
if (i - map.get(remainder) >= 2) {
return true;
}
} else {
map.set(remainder, i);
}
}
return false;
}6. 性能优化建议 ⚡
| 技巧类型 | 优化建议 |
|---|---|
| 预处理数组 | 1. 合理选择预处理的数据范围 |
| 2. 权衡空间成本和查询效率 | |
| 概率生成器 | 1. 尽量减少循环次数 |
| 2. 考虑边界情况的处理 | |
| 打表法 | 1. 仅在输入范围有限时使用 |
| 2. 注意表的大小和生成成本 | |
| 子数组处理 | 1. 善用动态规划思想 |
| 2. 考虑滑动窗口优化 |
7. 常见误区 ⚠️
- 过度预处理导致空间浪费
- 忽略边界条件和特殊情况
- 打表范围选择不当
- Map使用时的键值选择错误
8. 练习题推荐 📝
- LeetCode 560: 和为K的子数组
- LeetCode 525: 连续数组
- LeetCode 974: 和可被K整除的子数组
- LeetCode 523: 连续的子数组和
九、大数处理与模运算精讲 🔢
1. 为什么需要模运算？🤔
想象你在计算一个巨大的阶乘数：
- 20! 就已经是 2432902008176640000
- 100! 更是一个有158位的巨大数字
- 这些数字可能超出JavaScript的Number类型范围（2^53 - 1）
💡 使用模运算可以：
- 防止数字溢出
- 保持计算结果在可控范围内
- 满足特定题目的要求
2. 模运算的性质 📐
js
/**
* 模运算的基本性质
* 1. (a + b) % p = (a % p + b % p) % p
* 2. (a - b) % p = (a % p - b % p + p) % p
* 3. (a * b) % p = ((a % p) * (b % p)) % p
*/
class ModOperations {
constructor(mod = 1000000007) {
this.MOD = mod;
}
/**
* 加法运算
*/
add(a, b) {
return ((a % this.MOD) + (b % this.MOD)) % this.MOD;
}
/**
* 减法运算
*/
subtract(a, b) {
return ((a % this.MOD) - (b % this.MOD) + this.MOD) % this.MOD;
}
/**
* 乘法运算
*/
multiply(a, b) {
return ((a % this.MOD) * (b % this.MOD)) % this.MOD;
}
}3. 为什么选择1000000007？🎯
js
/**
* 1000000007的特点：
* 1. 是一个质数
* 2. 足够大，可以避免大多数整数溢出
* 3. 在int32范围内
* 4. 平方后在int64范围内，便于中间计算
*/
class ModCalculator {
static MOD = 1000000007;
/**
* 斐波那契数列示例
*/
static fibonacci(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
const next = (prev + curr) % this.MOD;
prev = curr;
curr = next;
}
return curr;
}
}4. 大数处理技巧 💡
4.1 字符串加法
js
/**
* 大数加法
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function addStrings(num1, num2) {
let i = num1.length - 1;
let j = num2.length - 1;
let carry = 0;
let result = '';
while (i >= 0 || j >= 0 || carry > 0) {
const digit1 = i >= 0 ? parseInt(num1[i]) : 0;
const digit2 = j >= 0 ? parseInt(num2[j]) : 0;
const sum = digit1 + digit2 + carry;
result = (sum % 10) + result;
carry = Math.floor(sum / 10);
i--;
j--;
}
return result;
}4.2 字符串乘法
js
/**
* 大数乘法
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function multiply(num1, num2) {
if (num1 === '0' || num2 === '0') return '0';
const m = num1.length;
const n = num2.length;
const result = new Array(m + n).fill(0);
// 逐位相乘
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const product = parseInt(num1[i]) * parseInt(num2[j]);
const p1 = i + j;
const p2 = i + j + 1;
const sum = product + result[p2];
result[p2] = sum % 10;
result[p1] += Math.floor(sum / 10);
}
}
// 去除前导零
while (result[0] === 0) {
result.shift();
}
return result.length ? result.join('') : '0';
}5. 前端实战应用 💻
- 精确金额计算
js
class PreciseCalculator {
/**
* 处理JavaScript浮点数精度问题
*/
static add(num1, num2) {
const scale = Math.max(
(num1.toString().split('.')[1] || '').length,
(num2.toString().split('.')[1] || '').length
);
const factor = Math.pow(10, scale);
return (Math.round(num1 * factor) +
Math.round(num2 * factor)) / factor;
}
}- 大数据统计
js
class DataStatistics {
constructor() {
this.count = '0';
this.MOD = 1000000007;
}
/**
* 增加统计数量
*/
increment(value) {
this.count = addStrings(this.count, value.toString());
// 需要时进行取模
if (this.count.length > 15) {
this.count = (BigInt(this.count) % BigInt(this.MOD)).toString();
}
}
}6. 性能优化建议 ⚡
| 场景 | 优化建议 |
|---|---|
| 模运算 | 1. 及时取模避免溢出 |
| 2. 利用模运算性质简化计算 | |
| 大数处理 | 1. 使用字符串存储大数 |
| 2. 合理使用BigInt | |
| 精度处理 | 1. 统一小数位数 |
| 2. 使用整数计算代替浮点数 |
7. 常见误区 ⚠️
- 忘记处理负数情况
- 模运算顺序错误
- 溢出检测不完整
- 精度丢失问题
8. 练习题推荐 📝
- LeetCode 415: 字符串相加
- LeetCode 43: 字符串相乘
- LeetCode 306: 累加数
- LeetCode 166: 分数到小数