搜索 K
主题
2 周刷完 100 道前端优质面试真题
课程说明
本文是 《2 周刷完 100 道前端优质面试真题》 的课程学习笔记，用于记录学习进度、核心知识点、错题与阶段复盘。
学习目标
学习进度
- 列出所有常见答案，分析逻辑和性能，找出最优解
- 关注代码质量 (编码规范性，功能完整性，鲁棒性)
- 写单元测试来统一验证各个功能
数据结构和算法
- 数据结构与算法是前端大厂面试必考题，用于高效甄别优秀工程师，降低鉴别成本。
- 前端业务范围扩大（服务端、客户端等），要求基本功扎实，并非单纯内卷。
- 学习重点包括算法复杂度、算法思维（贪心、二分、动态规划）及常见数据结构。
- 注意事项：本章难度大，需耐心；强调寻找最优解，避免盲目从众；注重解题思路与方法论的迁移。
算法复杂度
- 核心概念：复杂度指程序执行时的计算量 (时间复杂度) 或内存空间 (空间复杂度)，与代码书写简洁度无关。
- 数量级表示：使用大 O 表示法，如 O(1)、O(log N)、O(N)、O(Nlog N)、O(N^2)。
- O(1): 常数级，计算量固定。
- O(logN): 对数级，随输入增加增长平缓，效率高。
- O(N): 线性级，计算量与输入量成正比。
- O(N^2): 平方级，输入量增加时计算量飙升，通常不可用。
- 代码示例与对应关系：
- O(1): 无循环，直接访问对象属性。
- O(N): 单层循环遍历数组。
- O(N^2): 嵌套循环。
- O(logN): 二分查找思想，每次排除一半数据。
- 空间复杂度：前端重时间轻空间。O(1) 为固定空间，O(N) 为随输入线性增长的空间。
ts
// 无循环，直接访问对象属性
const obj = { name: 'John' }
console.log(obj.name) // O(1)ts
// 单层循环遍历数组
const arr = [1, 2, 3, 4, 5]
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]) // O(N)
}ts
// 嵌套循环
const matrix = [
[1, 2],
[3, 4],
]
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
console.log(matrix[i][j]) // O(N^2)
}
}ts
/**
* 二分查找：每次排除一半数据，O(logN) 的经典代表
* @param arr - 升序排列的数组
* @param target - 要查找的目标值
* @returns 目标值的下标；不存在时返回 -1
*/
export function binarySearch(arr: number[], target: number): number {
let left = 0
let right = arr.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (arr[mid] === target)
return mid
if (arr[mid] < target)
left = mid + 1
else right = mid - 1
}
return -1 // O(logN)
}
// 功能测试（node 直跑时执行；被 vitest 导入时静默）
if (import.meta.main) {
console.info(binarySearch([1, 3, 5, 7, 9, 11], 7)) // 3
}例题一：数组旋转 K 步
- 题目描述：将数组末尾 K 个元素移至头部。
- 思路一 (Pop/Unshift): 循环 K 次，
pop未尾元素并unshift到头部。- 时间复杂度：O(K·N) 即 O(N^2)，因为
unshift需移动所有元素。 - 空间复杂度：0(1)。
- 时间复杂度：O(K·N) 即 O(N^2)，因为
- 思路二 (Slice/Concat): 使用
slice拆分后concat拼接。- 时间复杂度：O(1)(注：此处讲师口误或简化，实际
slice/concat通常为 O(N)，但远优于 N^2) - 空间复杂度：0(N)，因创建新数组。
- 时间复杂度：O(1)(注：此处讲师口误或简化，实际
- 思路三 (三次翻转，课程未讲): 整体翻转后，前 K 段与剩余段各自翻转即得右旋结果（LeetCode 189 经典解法）。
- 时间复杂度：O(N)，每个元素至多被交换两次。
- 空间复杂度：O(1)，原地双指针交换，零额外分配——时间与空间双优的理论最优解。
- 面试语境：给出思路二后面试官常追问「能不能不开新数组」，三次翻转就是标准答案。
- 结论：前端重时间，思路二更优；若再问空间约束，思路三同时占住两个维度的最优。强调
unshift/shift/splice在数组中间操作慢，push/pop快。 - 单元测试覆盖正常、空数组、负数 K、非数字 K、K=0 等情况，休现代码健壮性。
ts
/**
* @description 旋转数组 k 步（第 2 章 · 数据结构和算法）
*
* 语义约定（与课程实现的刻意差异）：课程对负 k 取 `Math.abs`，把 -3 当 3 用；
* 本实现采用欧几里得取模 —— 正 k 右旋、负 k 左旋（-3 ≡ n-3），这是循环移位
* 的数学语义，也与 Python 切片、lodash 等生态直觉一致。
*/
/** k 归一化为 [0, n) 的等效右旋步数；非有限整数视为 0（鲁棒性：k 传入 NaN/小数不崩） */
function normalizeSteps(k: number, length: number): number {
if (length === 0 || !Number.isInteger(k))
return 0
return ((k % length) + length) % length
}
/**
* 思路一：pop + unshift 原地旋转。
* 时间 O(K·N)：unshift 每次整体挪动数组；空间 O(1)。
* @param arr 要旋转的数组（会被原地修改，返回同一引用）
*/
export function rotateArrayPopUnshift(arr: number[], k: number): number[] {
const steps = normalizeSteps(k, arr.length)
for (let i = 0; i < steps; i++) {
const last = arr.pop()
if (last !== undefined)
arr.unshift(last)
}
return arr
}
/**
* 思路二：slice + concat 拼接新数组。
* 时间 O(N)：两次浅拷贝各扫一遍；空间 O(N)。前端重时间轻空间，此为更优解。
* @param arr 要旋转的数组（不会被修改）
*/
export function rotateArraySliceConcat(arr: number[], k: number): number[] {
const steps = normalizeSteps(k, arr.length)
if (steps === 0)
return arr.slice()
return arr.slice(-steps).concat(arr.slice(0, arr.length - steps))
}
/** [from, to] 闭区间原地双指针翻转（不走 Array#reverse——它只能翻转整个数组） */
function reverseRange(arr: number[], from: number, to: number): void {
for (let i = from, j = to; i < j; i++, j--) {
const tmp = arr[i]!
arr[i] = arr[j]!
arr[j] = tmp
}
}
/**
* 思路三：三次翻转（课程未讲的理论最优解，LeetCode 189 经典解法）。
* 整体翻转后，前 steps 段与剩余段各自翻转即得右旋结果：
* [1,2,3,4,5,6,7], k=3 → 全翻 [7,6,5,4,3,2,1] → 前 3 翻 [5,6,7,…] → 后 4 翻 [5,6,7,1,2,3,4]
* 时间 O(N)：每元素至多被交换两次；空间 O(1)：原地无分配 ——
* 同时占住两个复杂度维度的最优，是面试给出思路二后的标准追问答案。
* @param arr 要旋转的数组（会被原地修改，返回同一引用）
*/
export function rotateArrayReverse(arr: number[], k: number): number[] {
const steps = normalizeSteps(k, arr.length)
if (steps === 0)
return arr
reverseRange(arr, 0, arr.length - 1)
reverseRange(arr, 0, steps - 1)
reverseRange(arr, steps, arr.length - 1)
return arr
}
// 功能演示（node 直跑时执行；被 vitest 导入时静默）
if (import.meta.main) {
console.info(rotateArraySliceConcat([1, 2, 3, 4, 5, 6, 7], 3)) // [5, 6, 7, 1, 2, 3, 4]
console.info(rotateArraySliceConcat([1, 2, 3, 4, 5, 6, 7], -3)) // [4, 5, 6, 7, 1, 2, 3]（左旋）
console.info(rotateArrayReverse([1, 2, 3, 4, 5, 6, 7], 3)) // [5, 6, 7, 1, 2, 3, 4]
}ts
import { describe, expect, it } from 'vitest'
import {
rotateArrayPopUnshift,
rotateArrayReverse,
rotateArraySliceConcat,
} from './array-rotate'
/** 朴素参照实现：逐元素按欧几里得取模落位，作为两种解法的对拍基准 */
function rotateReference(arr: number[], k: number): number[] {
const n = arr.length
if (n === 0 || !Number.isInteger(k))
return [...arr]
const steps = ((k % n) + n) % n
const result = Array.from<number>({ length: n })
for (const [i, value] of arr.entries()) result[(i + steps) % n] = value
return result
}
const implementations = [
{
name: 'rotateArrayPopUnshift（思路一：原地修改）',
rotate: rotateArrayPopUnshift,
},
{
name: 'rotateArraySliceConcat（思路二：返回新数组）',
rotate: rotateArraySliceConcat,
},
{
name: 'rotateArrayReverse（思路三：三次翻转原地最优）',
rotate: rotateArrayReverse,
},
] as const
describe.each(implementations)('$name', ({ rotate }) => {
it('正常右旋：末尾 k 个元素移至头部', () => {
expect(rotate([1, 2, 3, 4, 5, 6, 7], 3)).toEqual([5, 6, 7, 1, 2, 3, 4])
})
it('负 k 左旋（欧几里得取模语义，刻意区别于课程的 abs 处理）', () => {
expect(rotate([1, 2, 3, 4, 5, 6, 7], -3)).toEqual([4, 5, 6, 7, 1, 2, 3])
})
it('k 大于数组长度时按模处理', () => {
expect(rotate([1, 2, 3], 5)).toEqual([2, 3, 1])
})
it('k 等于数组长度时结果不变', () => {
expect(rotate([1, 2, 3], 3)).toEqual([1, 2, 3])
})
it('k 为 0 时结果不变', () => {
expect(rotate([1, 2, 3], 0)).toEqual([1, 2, 3])
})
it('空数组原样返回', () => {
expect(rotate([], 3)).toEqual([])
})
it('单元素数组任意旋转均不变', () => {
expect(rotate([42], 7)).toEqual([42])
})
it('k 为小数 / NaN 时视为 0（鲁棒性）', () => {
expect(rotate([1, 2, 3], 1.5)).toEqual([1, 2, 3])
expect(rotate([1, 2, 3], Number.NaN)).toEqual([1, 2, 3])
})
it('对拍：与朴素参照实现在 -2N ~ 2N 步内完全一致', () => {
const sample = [3, 1, 4, 1, 5, 9, 2, 6]
for (let k = -sample.length * 2; k <= sample.length * 2; k++)
expect(rotate([...sample], k)).toEqual(rotateReference(sample, k))
})
})
describe('实现语义差异', () => {
it('思路一原地修改，返回与入参同一引用', () => {
const input = [1, 2, 3, 4, 5]
const output = rotateArrayPopUnshift(input, 2)
expect(output).toBe(input)
expect(input).toEqual([4, 5, 1, 2, 3])
})
it('思路二不修改原数组，恒返回新数组（含 steps 为 0 的分支）', () => {
const input = [1, 2, 3, 4, 5]
const rotated = rotateArraySliceConcat(input, 2)
expect(rotated).not.toBe(input)
expect(input).toEqual([1, 2, 3, 4, 5])
expect(rotateArraySliceConcat(input, 0)).not.toBe(input)
})
it('思路三原地修改，返回与入参同一引用（含 steps 为 0 的短路分支）', () => {
const input = [1, 2, 3, 4, 5]
const output = rotateArrayReverse(input, 2)
expect(output).toBe(input)
expect(input).toEqual([4, 5, 1, 2, 3])
const untouched = [1, 2, 3]
expect(rotateArrayReverse(untouched, 0)).toBe(untouched)
expect(untouched).toEqual([1, 2, 3])
})
it('思路三偶数长度 / steps 恰为半长的边界（翻转区间对称点）', () => {
expect(rotateArrayReverse([1, 2, 3, 4], 2)).toEqual([3, 4, 1, 2])
expect(rotateArrayReverse([1, 2], 1)).toEqual([2, 1])
})
})ts
import { bench, describe } from 'vitest'
import {
rotateArrayPopUnshift,
rotateArrayReverse,
rotateArraySliceConcat,
} from './array-rotate'
/**
* 课程用注释掉的 console.time 做性能对比（10 万元素 ×9 万步：885ms vs 1ms），
* 这里升级为结构化基准 —— `pnpm bench` 一条命令出吞吐报告。
* 规模缩至 4000×3000：保持 O(K·N) 与 O(N) 的量级差距可见，同时让基准秒级完成。
*
* 公平性口径：思路一/三是原地实现，计时内统一做 `[...base]` 拷贝防止
* 已旋转数组被反复旋转；拷贝本身 O(N) 不改变三者量级排序，但意味着
* 一/三的读数含一次拷贝开销，二（内部自建新数组）不含 —— 解读时留意。
*/
const SIZE = 4000
const STEPS = 3000
const base = Array.from({ length: SIZE }, (_, i) => i)
describe(`数组旋转 ${SIZE} 元素 × ${STEPS} 步`, () => {
bench(
'思路一：pop + unshift（O(K·N) / O(1)）',
() => {
rotateArrayPopUnshift([...base], STEPS)
},
{ time: 300 },
)
bench(
'思路二：slice + concat（O(N) / O(N)）',
() => {
rotateArraySliceConcat(base, STEPS)
},
{ time: 300 },
)
bench(
'思路三：三次翻转（O(N) / O(1)，原地最优）',
() => {
rotateArrayReverse([...base], STEPS)
},
{ time: 300 },
)
})