余山郡

深浅模式

常用算法题与解析 ​

一、排序算法 ​

1. 冒泡排序 ​

题目描述 ​

给定一个数组，使用冒泡排序对其进行排序。

算法思路 ​

  1. 比较相邻的元素，如果前一个比后一个大，则交换它们。
  2. 对每一对相邻元素执行同样的操作，从开始第一对到结尾的最后一对。
  3. 每一轮比较后，最大的元素会“冒泡”到数组的末尾。
  4. 重复以上步骤，每次比较的元素数量减少一个，直到没有任何一对数字需要比较。

代码实现 ​

javascript
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换元素
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

时间复杂度 ​

  • 最好情况：O(n)，当数组已经有序时
  • 最坏情况：O(n²)，当数组逆序时
  • 平均情况：O(n²)

2. 选择排序 ​

题目描述 ​

给定一个数组，使用选择排序对其进行排序。

算法思路 ​

  1. 从未排序部分找到最小（或最大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
  3. 重复步骤 2，直到所有元素均排序完毕。

代码实现 ​

javascript
function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换元素
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

时间复杂度 ​

  • 最好情况：O(n²)
  • 最坏情况：O(n²)
  • 平均情况：O(n²)

3. 插入排序 ​

题目描述 ​

给定一个数组，使用插入排序对其进行排序。

算法思路 ​

  1. 将第一个元素视为已排序部分。
  2. 取出下一个元素，在已排序部分从后向前扫描。
  3. 如果已排序部分的元素大于新元素，则将该元素向右移动一位。
  4. 重复步骤 3，直到找到已排序部分中小于或等于新元素的位置。
  5. 将新元素插入到该位置。
  6. 重复步骤 2-5，直到所有元素都插入完毕。

代码实现 ​

javascript
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

时间复杂度 ​

  • 最好情况：O(n)，当数组已经有序时
  • 最坏情况：O(n²)，当数组逆序时
  • 平均情况：O(n²)

4. 快速排序 ​

题目描述 ​

给定一个数组，使用快速排序对其进行排序。

算法思路 ​

  1. 选择一个基准元素（通常是数组的第一个或最后一个元素）。
  2. 将数组分为两部分，小于基准的元素放在左边，大于基准的元素放在右边。
  3. 对左右两部分递归应用快速排序。

代码实现 ​

javascript
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

时间复杂度 ​

  • 最好情况：O(n log n)
  • 最坏情况：O(n²)，当数组已经有序时
  • 平均情况：O(n log n)

5. 归并排序 ​

题目描述 ​

给定一个数组，使用归并排序对其进行排序。

算法思路 ​

  1. 将数组分成两半。
  2. 对每一半递归地应用归并排序。
  3. 将两个已排序的半数组合并成一个有序数组。

代码实现 ​

javascript
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let 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++;
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

时间复杂度 ​

  • 最好情况：O(n log n)
  • 最坏情况：O(n log n)
  • 平均情况：O(n log n)

二、查找算法 ​

1. 线性查找 ​

题目描述 ​

在数组中查找指定元素的位置。

算法思路 ​

从数组的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个数组。

代码实现 ​

javascript
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

时间复杂度 ​

  • 最好情况：O(1)，目标元素在数组的第一个位置
  • 最坏情况：O(n)，目标元素在数组的最后一个位置或不存在
  • 平均情况：O(n)

2. 二分查找 ​

题目描述 ​

在有序数组中查找指定元素的位置。

算法思路 ​

  1. 找到数组的中间元素。
  2. 如果中间元素等于目标元素，则返回其位置。
  3. 如果中间元素大于目标元素，则在左半部分继续查找。
  4. 如果中间元素小于目标元素，则在右半部分继续查找。
  5. 重复步骤 1-4，直到找到目标元素或确定目标元素不存在。

代码实现 ​

javascript
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

时间复杂度 ​

  • 最好情况：O(1)，目标元素是数组的中间元素
  • 最坏情况：O(log n)
  • 平均情况：O(log n)

三、链表操作 ​

1. 反转链表 ​

题目描述 ​

反转一个单链表。

算法思路 ​

  1. 初始化三个指针：prev（前一个节点）、current（当前节点）和 next（下一个节点）。
  2. 遍历链表，对于每个节点：
    • 保存 next 节点
    • 将 current 节点的 next 指向 prev
    • 将 prev 移动到 current
    • 将 current 移动到 next
  3. 当遍历完成后，prev 指向新的头节点。

代码实现 ​

javascript
function reverseList(head) {
  let prev = null;
  let current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

时间复杂度 ​

  • O(n)，其中 n 是链表的长度

2. 检测链表环 ​

题目描述 ​

判断一个链表是否有环。

算法思路 ​

使用快慢指针：

  1. 初始化两个指针，slow 和 fast，都指向链表的头节点。
  2. slow 指针每次移动一步，fast 指针每次移动两步。
  3. 如果链表有环，fast 指针会追上 slow 指针。
  4. 如果链表没有环，fast 指针会先到达链表的末尾。

代码实现 ​

javascript
function hasCycle(head) {
  if (!head || !head.next) {
    return false;
  }
  let slow = head;
  let fast = head.next;
  while (slow !== fast) {
    if (!fast || !fast.next) {
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
}

时间复杂度 ​

  • O(n)，其中 n 是链表的长度

四、树操作 ​

1. 二叉树的前序遍历 ​

题目描述 ​

给定一个二叉树，返回其节点值的前序遍历。

算法思路 ​

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

代码实现 ​

javascript
// 递归实现
function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node) {
      result.push(node.val);
      traverse(node.left);
      traverse(node.right);
    }
  }
  traverse(root);
  return result;
}

// 迭代实现
function preorderTraversal(root) {
  const result = [];
  const stack = [];
  if (root) {
    stack.push(root);
  }
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) {
      stack.push(node.right);
    }
    if (node.left) {
      stack.push(node.left);
    }
  }
  return result;
}

时间复杂度 ​

  • O(n)，其中 n 是二叉树的节点数

2. 二叉树的中序遍历 ​

题目描述 ​

给定一个二叉树，返回其节点值的中序遍历。

算法思路 ​

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

代码实现 ​

javascript
// 递归实现
function inorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node) {
      traverse(node.left);
      result.push(node.val);
      traverse(node.right);
    }
  }
  traverse(root);
  return result;
}

// 迭代实现
function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

时间复杂度 ​

  • O(n)，其中 n 是二叉树的节点数

3. 二叉树的后序遍历 ​

题目描述 ​

给定一个二叉树，返回其节点值的后序遍历。

算法思路 ​

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

代码实现 ​

javascript
// 递归实现
function postorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node) {
      traverse(node.left);
      traverse(node.right);
      result.push(node.val);
    }
  }
  traverse(root);
  return result;
}

// 迭代实现
function postorderTraversal(root) {
  const result = [];
  const stack = [];
  let lastVisited = null;
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack[stack.length - 1];
    if (!current.right || current.right === lastVisited) {
      result.push(current.val);
      stack.pop();
      lastVisited = current;
      current = null;
    } else {
      current = current.right;
    }
  }
  return result;
}

时间复杂度 ​

  • O(n)，其中 n 是二叉树的节点数

4. 二叉树的层序遍历 ​

题目描述 ​

给定一个二叉树，返回其节点值的层序遍历。

算法思路 ​

使用队列进行广度优先搜索（BFS）：

  1. 将根节点加入队列。
  2. 当队列不为空时，执行以下操作：
    • 记录当前队列的长度（即当前层的节点数）
    • 遍历当前层的所有节点，将它们的值加入结果，并将它们的左右子节点加入队列
    • 将当前层的结果加入总结果

代码实现 ​

javascript
function levelOrder(root) {
  const result = [];
  if (!root) {
    return result;
  }
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; 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;
}

时间复杂度 ​

  • O(n)，其中 n 是二叉树的节点数

五、动态规划 ​

1. 爬楼梯 ​

题目描述 ​

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

算法思路 ​

  • 状态定义：dp[i] 表示爬到第 i 阶的方法数。
  • 状态转移方程：dp[i] = dp[i-1] + dp[i-2]，因为爬到第 i 阶的方法数等于爬到第 i-1 阶的方法数（再爬 1 阶）加上爬到第 i-2 阶的方法数（再爬 2 阶）。
  • 初始条件：dp[1] = 1, dp[2] = 2。

代码实现 ​

javascript
function climbStairs(n) {
  if (n === 1) {
    return 1;
  }
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

时间复杂度 ​

  • O(n)

2. 最大子数组和 ​

题目描述 ​

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

算法思路 ​

  • 状态定义：dp[i] 表示以 nums[i] 结尾的最大子数组和。
  • 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])，因为以 nums[i] 结尾的最大子数组和要么是 nums[i] 本身，要么是 nums[i] 加上以 nums[i-1] 结尾的最大子数组和。
  • 初始条件：dp[0] = nums[0]。
  • 最终结果：max(dp)。

代码实现 ​

javascript
function maxSubArray(nums) {
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  let max = dp[0];
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    max = Math.max(max, dp[i]);
  }
  return max;
}

时间复杂度 ​

  • O(n)

3. 0-1 背包问题 ​

题目描述 ​

给定 n 个物品，每个物品有一个重量 w[i] 和一个价值 v[i]，以及一个容量为 C 的背包。问如何选择物品，使得放入背包的物品总价值最大，且总重量不超过 C。

算法思路 ​

  • 状态定义：dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。
  • 状态转移方程：
    • 如果 w[i-1] > j（当前物品重量超过背包容量），则 dp[i][j] = dp[i-1][j]
    • 否则，dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
  • 初始条件：dp[0][j] = 0（没有物品时，价值为 0）。

代码实现 ​

javascript
function knapsack(w, v, C) {
  const n = w.length;
  const dp = new Array(n + 1).fill().map(() => new Array(C + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= C; j++) {
      if (w[i - 1] > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
      }
    }
  }
  return dp[n][C];
}

时间复杂度 ​

  • O(nC)，其中 n 是物品数量，C 是背包容量

六、图算法 ​

1. 深度优先搜索（DFS） ​

题目描述 ​

给定一个图，使用深度优先搜索遍历所有节点。

算法思路 ​

  1. 从起始节点开始，访问该节点。
  2. 递归地访问该节点的所有未访问过的邻居节点。
  3. 重复步骤 2，直到所有节点都被访问。

代码实现 ​

javascript
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
  return visited;
}

时间复杂度 ​

  • O(V + E)，其中 V 是节点数，E 是边数

2. 广度优先搜索（BFS） ​

题目描述 ​

给定一个图，使用广度优先搜索遍历所有节点。

算法思路 ​

  1. 从起始节点开始，将其加入队列。
  2. 当队列不为空时，执行以下操作：
    • 取出队列中的第一个节点，访问它。
    • 将该节点的所有未访问过的邻居节点加入队列。
  3. 重复步骤 2，直到所有节点都被访问。

代码实现 ​

javascript
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);
  while (queue.length) {
    const node = queue.shift();
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return visited;
}

时间复杂度 ​

  • O(V + E)，其中 V 是节点数，E 是边数

3. 最短路径算法（Dijkstra） ​

题目描述 ​

给定一个带权有向图，找到从起始节点到所有其他节点的最短路径。

算法思路 ​

  1. 初始化一个距离数组，将起始节点的距离设为 0，其他节点的距离设为无穷大。
  2. 使用优先队列（最小堆）来选择当前距离最小的节点。
  3. 对于当前节点，遍历其所有邻居节点，计算从起始节点经过当前节点到邻居节点的距离，如果这个距离比邻居节点当前的距离小，则更新邻居节点的距离。
  4. 重复步骤 2-3，直到所有节点都被处理。

代码实现 ​

javascript
function dijkstra(graph, start) {
  const distances = {};
  const priorityQueue = [];
  
  // 初始化距离
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;
  
  // 优先队列初始化
  priorityQueue.push({ distance: 0, node: start });
  
  while (priorityQueue.length) {
    // 按距离排序，取出距离最小的节点
    priorityQueue.sort((a, b) => a.distance - b.distance);
    const { distance, node } = priorityQueue.shift();
    
    // 如果当前距离大于记录的距离，跳过
    if (distance > distances[node]) {
      continue;
    }
    
    // 遍历邻居节点
    for (const [neighbor, weight] of Object.entries(graph[node])) {
      const newDistance = distance + weight;
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        priorityQueue.push({ distance: newDistance, node: neighbor });
      }
    }
  }
  
  return distances;
}

时间复杂度 ​

  • O((V + E) log V)，其中 V 是节点数，E 是边数

七、字符串处理 ​

1. 最长回文子串 ​

题目描述 ​

给定一个字符串 s，找到 s 中最长的回文子串。

算法思路 ​

使用中心扩展法：

  1. 遍历字符串的每个字符，将其作为回文的中心。
  2. 对于每个中心，向两边扩展，检查是否是回文。
  3. 记录最长的回文子串。

代码实现 ​

javascript
function longestPalindrome(s) {
  if (s.length < 2) {
    return s;
  }
  
  let start = 0;
  let maxLength = 1;
  
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLength) {
        maxLength = right - left + 1;
        start = left;
      }
      left--;
      right++;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    // 奇数长度的回文
    expandAroundCenter(i, i);
    // 偶数长度的回文
    expandAroundCenter(i, i + 1);
  }
  
  return s.substring(start, start + maxLength);
}

时间复杂度 ​

  • O(n²)，其中 n 是字符串的长度

2. 字符串匹配（KMP 算法） ​

题目描述 ​

给定一个文本串 text 和一个模式串 pattern，在文本串中找到模式串的第一次出现位置。

算法思路 ​

KMP 算法的核心是构建部分匹配表（next 数组），用于在匹配失败时快速回退模式串的指针。

代码实现 ​

javascript
function kmpSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  
  if (m === 0) {
    return 0;
  }
  
  // 构建 next 数组
  const next = new Array(m).fill(0);
  for (let i = 1, j = 0; i < m; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = next[j - 1];
    }
    if (pattern[i] === pattern[j]) {
      j++;
    }
    next[i] = j;
  }
  
  // 匹配过程
  for (let i = 0, j = 0; i < n; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = next[j - 1];
    }
    if (text[i] === pattern[j]) {
      j++;
    }
    if (j === m) {
      return i - m + 1;
    }
  }
  
  return -1;
}

时间复杂度 ​

  • O(n + m)，其中 n 是文本串的长度，m 是模式串的长度

八、贪心算法 ​

1. 活动选择问题 ​

题目描述 ​

给定一组活动，每个活动有开始时间和结束时间，选择最多的活动，使得这些活动不重叠。

算法思路 ​

贪心策略：每次选择结束时间最早的活动，这样可以为后续活动留出更多时间。

代码实现 ​

javascript
function activitySelection(activities) {
  // 按结束时间排序
  activities.sort((a, b) => a.end - b.end);
  
  const selected = [];
  let lastEnd = -Infinity;
  
  for (const activity of activities) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }
  
  return selected;
}

时间复杂度 ​

  • O(n log n)，其中 n 是活动数量（排序的时间复杂度）

2. 零钱兑换 ​

题目描述 ​

给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

算法思路 ​

贪心策略：每次选择面值最大的硬币，尽可能多的使用它。

代码实现 ​

javascript
function coinChange(coins, amount) {
  // 按面值从大到小排序
  coins.sort((a, b) => b - a);
  
  let result = Infinity;
  
  function dfs(index, currentAmount, count) {
    const coin = coins[index];
    
    // 如果已经找到一个比当前结果更好的解，直接返回
    if (count >= result) {
      return;
    }
    
    // 计算最多可以使用多少个当前硬币
    const maxCoins = Math.floor(currentAmount / coin);
    
    // 如果已经到了最后一种硬币
    if (index === coins.length - 1) {
      if (currentAmount % coin === 0) {
        result = Math.min(result, count + maxCoins);
      }
      return;
    }
    
    // 尝试使用不同数量的当前硬币
    for (let i = maxCoins; i >= 0; i--) {
      dfs(index + 1, currentAmount - i * coin, count + i);
    }
  }
  
  dfs(0, amount, 0);
  return result === Infinity ? -1 : result;
}

时间复杂度 ​

  • O(S^n)，其中 S 是最大硬币面值，n 是硬币种类数（最坏情况）

九、位运算 ​

1. 位 1 的个数 ​

题目描述 ​

编写一个函数，输入一个无符号整数，返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

算法思路 ​

使用位运算：

  • n & 1 可以获取 n 的最低位
  • n >> 1 可以将 n 右移一位

代码实现 ​

javascript
function hammingWeight(n) {
  let count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

时间复杂度 ​

  • O(1)，因为无符号整数的位数是固定的

2. 两数之和 ​

题目描述 ​

给你两个整数 a 和 b，不使用运算符 + 和 -，计算并返回两数之和。

算法思路 ​

使用位运算：

  • a ^ b 计算无进位的和
  • (a & b) << 1 计算进位
  • 重复上述过程，直到进位为 0

代码实现 ​

javascript
function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

时间复杂度 ​

  • O(1)，因为整数的位数是固定的

十、总结 ​

以上是一些常用的算法题及其解析，涵盖了排序、查找、链表、树、动态规划、图、字符串处理、贪心算法和位运算等多个领域。掌握这些算法对于提高编程能力和解决实际问题非常重要。

在学习算法时，建议：

  1. 理解算法的基本思路和原理
  2. 掌握算法的代码实现
  3. 分析算法的时间复杂度和空间复杂度
  4. 多做练习，熟悉不同类型的算法问题
  5. 尝试优化算法，提高效率

通过不断学习和实践，你将能够更高效地解决各种算法问题，提升自己的编程能力。

Released under the MIT License.

Copyright © 2025-present China Carlos