1. 数组与字符串：滑动窗口
题目描述：
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
JavaScript解决方案：
/**
* @param {string} s
* @return {number}
*/
function lengthOfLongestSubstring(s) {
// 使用Map存储字符及其最后出现的位置
const charIndexMap = new Map();
let left = 0; // 滑动窗口左边界
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
const currentChar = s[right];
// 如果字符已在窗口内，移动左边界
if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
left = charIndexMap.get(currentChar) + 1;
}
// 更新字符位置
charIndexMap.set(currentChar, right);
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// 测试
console.log("最长无重复子串:");
console.log('"abcabcbb" ->', lengthOfLongestSubstring("abcabcbb")); // 3
console.log('"bbbbb" ->', lengthOfLongestSubstring("bbbbb")); // 1
console.log('"pwwkew" ->', lengthOfLongestSubstring("pwwkew")); // 3
2. 链表：反转链表
题目描述：
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例：
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
JavaScript解决方案：
/**
* 链表节点定义
*/
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const nextNode = current.next; // 暂存下一个节点
current.next = prev; // 反转当前节点的指针
prev = current; // 移动prev到当前节点
current = nextNode; // 移动current到下一个节点
}
return prev; // prev最终成为新的头节点
}
// 辅助函数：创建链表
function createList(arr) {
if (arr.length === 0) return null;
const head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
// 辅助函数：打印链表
function printList(head) {
const result = [];
let current = head;
while (current !== null) {
result.push(current.val);
current = current.next;
}
return result;
}
// 测试
console.log("\n反转链表:");
const head = createList([1, 2, 3, 4, 5]);
console.log("原始链表:", printList(head)); // [1,2,3,4,5]
const reversed = reverseList(head);
console.log("反转后:", printList(reversed)); // [5,4,3,2,1]
3. 栈：有效的括号
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入: s = "()"
输出: true
示例 2：
输入: s = "()[]{}"
输出: true
示例 3：
输入: s = "(]"
输出: false
JavaScript解决方案：
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const stack = [];
const bracketPairs = {
')': '(',
'}': '{',
']': '['
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
// 如果是右括号
if (bracketPairs[char]) {
// 检查栈顶元素是否匹配
const topElement = stack.length === 0 ? '#' : stack.pop();
if (topElement !== bracketPairs[char]) {
return false;
}
}
// 如果是左括号，压入栈
else {
stack.push(char);
}
}
// 如果栈为空，说明所有括号都匹配
return stack.length === 0;
}
// 测试
console.log("\n有效的括号:");
console.log('"()" ->', isValid("()")); // true
console.log('"()[]{}" ->', isValid("()[]{}")); // true
console.log('"(]" ->', isValid("(]")); // false
console.log('"([)]" ->', isValid("([)]")); // false
console.log('"{[]}" ->', isValid("{[]}")); // true
4. 哈希表：两数之和
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用同一个元素两次。
你可以按任意顺序返回答案。
示例 1：
输入: nums = [2,7,11,15], target = 9
输出: [0,1]
解释: 因为 nums[0] + nums[1] = 2 + 7 = 9
示例 2：
输入: nums = [3,2,4], target = 6
输出: [1,2]
JavaScript解决方案：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
// 使用Map存储数字和对应的索引
const numMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
// 检查补数是否已在Map中
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
// 将当前数字和索引存入Map
numMap.set(nums[i], i);
}
return []; // 根据题目描述，总会有一个解
}
// 测试
console.log("\n两数之和:");
console.log("nums = [2,7,11,15], target = 9 ->", twoSum([2,7,11,15], 9)); // [0,1]
console.log("nums = [3,2,4], target = 6 ->", twoSum([3,2,4], 6)); // [1,2]
console.log("nums = [3,3], target = 6 ->", twoSum([3,3], 6)); // [0,1]
5. 二叉树：二叉树的最大深度
题目描述：
给定一个二叉树 root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例：
3
/ \
9 20
/ \
15 7
输入: root = [3,9,20,null,null,15,7]
输出: 3
解释: 最大深度为3，路径为 3→20→7 或 3→20→15
JavaScript解决方案：
/**
* 二叉树节点定义
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* @param {TreeNode} root
* @return {number}
*/
function maxDepth(root) {
// 递归解法：深度优先搜索
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// 广度优先搜索解法
function maxDepthBFS(root) {
if (root === null) return 0;
const queue = [root];
let depth = 0;
while (queue.length > 0) {
depth++;
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return depth;
}
// 创建测试二叉树
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
// 测试
console.log("\n二叉树的最大深度:");
console.log("递归解法:", maxDepth(root)); // 3
console.log("BFS解法:", maxDepthBFS(root)); // 3
6. 堆：数组中的第K个最大元素
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1：
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
解释: 排序后数组是 [1,2,3,4,5,6]，第2个最大元素是5
示例 2：
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
JavaScript解决方案：
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 方法1：使用内置排序（简单但效率较低）
function findKthLargestSort(nums, k) {
nums.sort((a, b) => b - a); // 降序排序
return nums[k - 1];
}
// 方法2：最小堆（推荐面试使用）
function findKthLargestHeap(nums, k) {
// 最小堆实现
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._sinkDown(0);
}
return min;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
_bubbleUp(index) {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (element >= parent) break;
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex;
}
}
_sinkDown(index) {
const length = this.heap.length;
const element = this.heap[index];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let swap = null;
let leftChild, rightChild;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild < element) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild < element) ||
(swap !== null && rightChild < leftChild)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap;
}
}
}
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.push(num);
// 保持堆的大小为k
if (minHeap.size() > k) {
minHeap.pop(); // 移除最小的元素
}
}
return minHeap.peek(); // 堆顶就是第k个最大元素
}
// 测试
console.log("\n数组中的第K个最大元素:");
const nums1 = [3,2,1,5,6,4];
console.log("排序方法:", findKthLargestSort([...nums1], 2)); // 5
console.log("最小堆方法:", findKthLargestHeap([...nums1], 2)); // 5
const nums2 = [3,2,3,1,2,4,5,5,6];
console.log("排序方法:", findKthLargestSort([...nums2], 4)); // 4
console.log("最小堆方法:", findKthLargestHeap([...nums2], 4)); // 4
7. 回溯：全排列
题目描述：
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入: nums = [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入: nums = [0,1]
输出: [[0,1],[1,0]]
JavaScript解决方案：
/**
* @param {number[]} nums
* @return {number[][]}
*/
function permute(nums) {
const result = [];
// 回溯函数
function backtrack(currentPermutation, used) {
// 如果当前排列长度等于原数组长度，说明找到了一个排列
if (currentPermutation.length === nums.length) {
result.push([...currentPermutation]); // 深拷贝
return;
}
for (let i = 0; i < nums.length; i++) {
// 如果数字已使用，跳过
if (used[i]) continue;
// 选择当前数字
used[i] = true;
currentPermutation.push(nums[i]);
// 递归探索
backtrack(currentPermutation, used);
// 撤销选择（回溯）
currentPermutation.pop();
used[i] = false;
}
}
backtrack([], new Array(nums.length).fill(false));
return result;
}
// 测试
console.log("\n全排列:");
console.log("输入: [1,2,3]");
console.log("输出:", permute([1,2,3]));
console.log("\n输入: [0,1]");
console.log("输出:", permute([0,1]));
8. 分治：归并排序
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入: nums = [5,2,3,1]
输出: [1,2,3,5]
示例 2：
输入: nums = [5,1,1,2,0,0]
输出: [0,0,1,1,2,5]
JavaScript解决方案：
/**
* @param {number[]} nums
* @return {number[]}
*/
function mergeSort(nums) {
// 分治法的典型应用
if (nums.length <= 1) {
return nums;
}
// 1. 分：将数组分成两半
const mid = Math.floor(nums.length / 2);
const left = nums.slice(0, mid);
const right = nums.slice(mid);
// 2. 治：递归排序左右两半
const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
// 3. 合：合并两个有序数组
return merge(sortedLeft, sortedRight);
}
/**
* 合并两个有序数组
*/
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// 比较两个数组的元素，将较小的放入结果
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 将剩余元素添加到结果
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
// 测试
console.log("\n归并排序:");
console.log("输入: [5,2,3,1]");
console.log("输出:", mergeSort([5,2,3,1])); // [1,2,3,5]
console.log("\n输入: [5,1,1,2,0,0]");
console.log("输出:", mergeSort([5,1,1,2,0,0])); // [0,0,1,1,2,5]
9. BFS：二叉树的层序遍历
题目描述：
给你二叉树的根节点 root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
示例：
3
/ \
9 20
/ \
15 7
输入: root = [3,9,20,null,null,15,7]
输出: [[3],[9,20],[15,7]]
JavaScript解决方案：
/**
* @param {TreeNode} root
* @return {number[][]}
*/
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
// 创建测试二叉树
const tree = new TreeNode(3);
tree.left = new TreeNode(9);
tree.right = new TreeNode(20);
tree.right.left = new TreeNode(15);
tree.right.right = new TreeNode(7);
// 测试
console.log("\n二叉树的层序遍历:");
console.log("输出:", levelOrder(tree)); // [[3],[9,20],[15,7]]
10. 动态规划：爬楼梯
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
JavaScript解决方案：
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
if (n <= 2) return n;
// dp[i] 表示爬到第i阶楼梯的方法数
const dp = new Array(n + 1).fill(0);
dp[1] = 1; // 爬1阶有1种方法
dp[2] = 2; // 爬2阶有2种方法
for (let i = 3; i <= n; i++) {
// 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 空间优化版本
function climbStairsOptimized(n) {
if (n <= 2) return n;
let prev1 = 2; // dp[i-1]，从i=3开始，prev1=dp[2]=2
let prev2 = 1; // dp[i-2]，从i=3开始，prev2=dp[1]=1
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// 测试
console.log("\n爬楼梯:");
console.log("n=1 ->", climbStairs(1)); // 1
console.log("n=2 ->", climbStairs(2)); // 2
console.log("n=3 ->", climbStairs(3)); // 3
console.log("n=4 ->", climbStairs(4)); // 5
console.log("n=5 ->", climbStairs(5)); // 8
console.log("\n空间优化版本:");
console.log("n=5 ->", climbStairsOptimized(5)); // 8
11. 贪心算法：分发饼干
题目描述：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1：
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2：
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2。
JavaScript解决方案：
/**
* @param {number[]} g - 孩子的胃口值
* @param {number[]} s - 饼干的尺寸
* @return {number}
*/
function findContentChildren(g, s) {
// 贪心策略：用小饼干满足小胃口的孩子
g.sort((a, b) => a - b); // 孩子按胃口排序
s.sort((a, b) => a - b); // 饼干按尺寸排序
let childIndex = 0;
let cookieIndex = 0;
let satisfiedCount = 0;
while (childIndex < g.length && cookieIndex < s.length) {
if (s[cookieIndex] >= g[childIndex]) {
// 当前饼干可以满足当前孩子
satisfiedCount++;
childIndex++;
cookieIndex++;
} else {
// 当前饼干太小，尝试下一块饼干
cookieIndex++;
}
}
return satisfiedCount;
}
// 测试
console.log("\n分发饼干:");
console.log("g=[1,2,3], s=[1,1] ->", findContentChildren([1,2,3], [1,1])); // 1
console.log("g=[1,2], s=[1,2,3] ->", findContentChildren([1,2], [1,2,3])); // 2
12. 双指针：盛最多水的容器
题目描述：
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例：
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
JavaScript解决方案：
/**
* @param {number[]} height
* @return {number}
*/
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
// 计算当前容器的水量
const width = right - left;
const currentHeight = Math.min(height[left], height[right]);
const currentWater = width * currentHeight;
// 更新最大水量
maxWater = Math.max(maxWater, currentWater);
// 移动较矮的指针，因为移动较高的指针不会增加水量
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
// 测试
console.log("\n盛最多水的容器:");
const heights = [1,8,6,2,5,4,8,3,7];
console.log("height =", heights);
console.log("最大水量 =", maxArea(heights)); // 49
13. 排序：快速排序
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入: nums = [5,2,3,1]
输出: [1,2,3,5]
示例 2：
输入: nums = [5,1,1,2,0,0]
输出: [0,0,1,1,2,5]
JavaScript解决方案：
/**
* @param {number[]} nums
* @return {number[]}
*/
function quickSort(nums) {
if (nums.length <= 1) return nums;
// 选择基准元素
const pivotIndex = Math.floor(nums.length / 2);
const pivot = nums[pivotIndex];
// 分割数组
const left = [];
const right = [];
for (let i = 0; i < nums.length; i++) {
if (i === pivotIndex) continue;
if (nums[i] < pivot) {
left.push(nums[i]);
} else {
right.push(nums[i]);
}
}
// 递归排序并合并
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 原地快速排序（更高效）
function quickSortInPlace(nums, left = 0, right = nums.length - 1) {
if (left >= right) return;
const pivotIndex = partition(nums, left, right);
quickSortInPlace(nums, left, pivotIndex - 1);
quickSortInPlace(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;
}
// 测试
console.log("\n快速排序:");
console.log("简单版本:");
console.log("[5,2,3,1] ->", quickSort([5,2,3,1])); // [1,2,3,5]
console.log("[5,1,1,2,0,0] ->", quickSort([5,1,1,2,0,0])); // [0,0,1,1,2,5]
console.log("\n原地排序版本:");
const arr1 = [5,2,3,1];
quickSortInPlace(arr1);
console.log("[5,2,3,1] ->", arr1); // [1,2,3,5]
const arr2 = [5,1,1,2,0,0];
quickSortInPlace(arr2);
console.log("[5,1,1,2,0,0] ->", arr2); // [0,0,1,1,2,5]
14. 二分查找
题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
JavaScript解决方案：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// 防止整数溢出
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 二分查找变种：查找左边界
function searchLeftBound(nums, target) {
let left = 0;
let right = nums.length; // 注意
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 检查left是否越界或找到target
if (left < 0 || left >= nums.length || nums[left] !== target) {
return -1;
}
return left;
}
// 测试
console.log("\n二分查找:");
const nums = [-1,0,3,5,9,12];
console.log("nums =", nums);
console.log("target = 9 ->", search(nums, 9)); // 4
console.log("target = 2 ->", search(nums, 2)); // -1
console.log("\n二分查找左边界:");
const nums2 = [1,2,2,2,3,4,5];
console.log("nums =", nums2);
console.log("target = 2 ->", searchLeftBound(nums2, 2)); // 1
console.log("target = 6 ->", searchLeftBound(nums2, 6)); // -1
总结
现在每个算法题目都有了：
- 完整的题目描述 - 理解问题在问什么
- 清晰的示例 - 了解输入输出格式
- JavaScript解决方案 - 具体的实现代码
- 测试代码 - 验证解决方案的正确性
这些题目覆盖了算法面试中最核心的14个知识点，掌握了这些题目，你就有了应对大多数算法面试的基础。记住，不仅要会写代码，更要理解算法背后的思想和原理！
