杂项✅

本章涵盖算法面试中的经典问题，包括大数运算、海量数据处理、图论应用等重要主题。

大数字符串运算如何实现？

// 实现大数字符串相加和相乘
// 不能使用任何內建的用于处理大整数的库（比如 BigInteger）
// 也不能直接将输入的字符串转换为整数形式
function addStrings(num1, num2) {
  // 请实现大数字符串相加
}

function multiplyStrings(num1, num2) {
  // 请实现大数字符串相乘  
}

答案

核心概念

大数字符串运算用于处理超出JavaScript数值精度限制的整数运算。通过模拟小学算术运算过程，逐位进行计算并处理进位，实现任意精度的整数运算。

实现策略

大数相加算法：

双指针倒序遍历：从两个数字字符串的末尾开始
逐位相加：对应位数字相加，加上进位
进位处理：和超过9时产生进位，当前位保留余数
长度处理：较长数字的剩余位数继续处理
结果构建：将计算结果从前往后组装成字符串

大数相乘算法：

分解为单位乘法：num2的每一位与num1相乘
位置偏移：根据位数添加相应的0
累加结果：将所有部分积相加得到最终结果
特殊情况：处理0的乘法和单位数乘法

示例实现

/**
 * 大数字符串相加
 * @param {string} num1 - 第一个大数字符串
 * @param {string} num2 - 第二个大数字符串
 * @returns {string} 相加结果
 */
function addStrings(num1, num2) {
  const result = [];
  let carry = 0;
  let i = num1.length - 1;
  let j = num2.length - 1;
  
  while (i >= 0 || j >= 0 || carry) {
    const digit1 = i >= 0 ? Number(num1[i]) : 0;
    const digit2 = j >= 0 ? Number(num2[j]) : 0;
    const sum = digit1 + digit2 + carry;
    
    result.unshift(sum % 10);
    carry = Math.floor(sum / 10);
    
    i--;
    j--;
  }
  
  return result.join('');
}

/**
 * 大数字符串相乘
 * @param {string} num1 - 第一个大数字符串
 * @param {string} num2 - 第二个大数字符串
 * @returns {string} 相乘结果
 */
function multiplyStrings(num1, num2) {
  // 处理特殊情况
  if (num1 === '0' || num2 === '0') {
    return '0';
  }
  
  let result = '0';
  
  // num2的每一位与num1相乘
  for (let i = num2.length - 1; i >= 0; i--) {
    let tempResult = multiplyByDigit(num1, num2[i]);
    
    // 添加对应的0（位数偏移）
    for (let j = 0; j < num2.length - 1 - i; j++) {
      tempResult += '0';
    }
    
    result = addStrings(result, tempResult);
  }
  
  return result;
}

/**
 * 大数字符串与单个数字相乘
 * @param {string} num - 大数字符串
 * @param {string} digit - 单个数字字符
 * @returns {string} 相乘结果
 */
function multiplyByDigit(num, digit) {
  if (digit === '0') return '0';
  
  const result = [];
  let carry = 0;
  const d = Number(digit);
  
  for (let i = num.length - 1; i >= 0; i--) {
    const product = Number(num[i]) * d + carry;
    result.unshift(product % 10);
    carry = Math.floor(product / 10);
  }
  
  if (carry) {
    result.unshift(carry);
  }
  
  return result.join('');
}

/**
 * 大数字符串减法
 * @param {string} num1 - 被减数（应该大于等于减数）
 * @param {string} num2 - 减数
 * @returns {string} 相减结果
 */
function subtractStrings(num1, num2) {
  // 确保num1 >= num2
  if (compareStrings(num1, num2) < 0) {
    throw new Error('被减数应该大于等于减数');
  }
  
  const result = [];
  let borrow = 0;
  let i = num1.length - 1;
  let j = num2.length - 1;
  
  while (i >= 0) {
    let digit1 = Number(num1[i]) - borrow;
    const digit2 = j >= 0 ? Number(num2[j]) : 0;
    
    if (digit1 < digit2) {
      digit1 += 10;
      borrow = 1;
    } else {
      borrow = 0;
    }
    
    result.unshift(digit1 - digit2);
    i--;
    j--;
  }
  
  // 移除前导零
  while (result.length > 1 && result[0] === 0) {
    result.shift();
  }
  
  return result.join('');
}

/**
 * 比较两个大数字符串
 * @param {string} num1 - 第一个数
 * @param {string} num2 - 第二个数
 * @returns {number} 1表示num1>num2，-1表示num1<num2，0表示相等
 */
function compareStrings(num1, num2) {
  // 移除前导零
  num1 = num1.replace(/^0+/, '') || '0';
  num2 = num2.replace(/^0+/, '') || '0';
  
  if (num1.length > num2.length) return 1;
  if (num1.length < num2.length) return -1;
  
  return num1.localeCompare(num2);
}

/**
 * 大数字符串除法（整数除法）
 * @param {string} dividend - 被除数
 * @param {string} divisor - 除数
 * @returns {Object} {quotient: 商, remainder: 余数}
 */
function divideStrings(dividend, divisor) {
  if (divisor === '0') {
    throw new Error('除数不能为0');
  }
  
  if (compareStrings(dividend, divisor) < 0) {
    return { quotient: '0', remainder: dividend };
  }
  
  let quotient = '';
  let remainder = '';
  
  for (let i = 0; i < dividend.length; i++) {
    remainder += dividend[i];
    remainder = remainder.replace(/^0+/, '') || '0';
    
    let count = 0;
    while (compareStrings(remainder, divisor) >= 0) {
      remainder = subtractStrings(remainder, divisor);
      count++;
    }
    
    quotient += count.toString();
  }
  
  quotient = quotient.replace(/^0+/, '') || '0';
  return { quotient, remainder };
}

module.exports = {
  addStrings,
  multiplyStrings,
  multiplyByDigit,
  subtractStrings,
  compareStrings,
  divideStrings
};

扩展功能

大数减法：借位处理，注意被减数必须大于减数
大数除法：长除法模拟，返回商和余数
大数比较：长度优先，同长度时字典序比较
大数幂运算：快速幂算法优化

性能优化

Karatsuba乘法：分治算法，时间复杂度O(n^1.585)
FFT乘法：快速傅里叶变换，适用于超大数
内存优化：避免频繁字符串拼接，使用数组操作
并行计算：将大数分块并行处理

面试官视角

该题考察候选人的算法实现能力和细节处理：

要点清单: 理解进位借位机制；正确处理边界情况；掌握字符串操作技巧；能分析时间空间复杂度
加分项: 了解多种乘法算法；能优化性能；处理负数情况；有实际项目应用经验
常见失误: 进位处理错误；字符串索引越界；忽视前导零；不处理特殊情况（如0）

延伸阅读

高精度运算详解 — 算法竞赛中的大数处理
Karatsuba算法 — 高效大数乘法

海量数据中如何找TopK？

答案

核心概念

海量数据TopK问题是在大规模数据集中找出最大（或最小）的K个元素。由于数据量巨大，无法全部加载到内存，需要使用特殊的算法和数据结构来高效解决。

解决方案

1. 小顶堆方法（内存足够时）

维护一个大小为K的小顶堆
遍历数据，如果新元素大于堆顶，则替换堆顶
时间复杂度：O(N log K)，空间复杂度：O(K)

2. 分治法（海量数据）

将大数据集分成多个小块
对每个小块分别求TopK
合并所有小块的TopK结果，再求TopK

3. 快速选择算法

类似快排的分区思想
平均时间复杂度：O(N)，但需要随机访问数据

4. 外部排序

适用于数据无法完全加载到内存的情况
使用归并排序的思想处理大文件

示例实现

/**
 * 最小堆实现（用于Top K最大值问题）
 */
class MinHeap {
  constructor() {
    this.heap = [];
  }

  // 获取父节点索引
  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  leftChild(index) {
    return 2 * index + 1;
  }

  // 获取右子节点索引
  rightChild(index) {
    return 2 * index + 2;
  }

  // 交换两个元素
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // 向上调整堆
  heapifyUp(index) {
    if (index === 0) return;
    
    const parentIndex = this.parent(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.heapifyUp(parentIndex);
    }
  }

  // 向下调整堆
  heapifyDown(index) {
    let minIndex = index;
    const left = this.leftChild(index);
    const right = this.rightChild(index);

    if (left < this.heap.length && this.heap[left] < this.heap[minIndex]) {
      minIndex = left;
    }

    if (right < this.heap.length && this.heap[right] < this.heap[minIndex]) {
      minIndex = right;
    }

    if (minIndex !== index) {
      this.swap(index, minIndex);
      this.heapifyDown(minIndex);
    }
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  // 删除并返回最小元素
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  // 获取最小元素
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // 获取堆大小
  size() {
    return this.heap.length;
  }

  // 判断堆是否为空
  isEmpty() {
    return this.heap.length === 0;
  }
}

/**
 * 使用小顶堆找出数组中最大的K个数
 * 时间复杂度: O(n log k)
 * 空间复杂度: O(k)
 * @param {number[]} nums - 输入数组
 * @param {number} k - 需要找出的最大值个数
 * @returns {number[]} 最大的K个数
 */
function topKLargest(nums, k) {
  if (k <= 0 || nums.length === 0) return [];
  
  const heap = new MinHeap();
  
  for (const num of nums) {
    if (heap.size() < k) {
      heap.insert(num);
    } else if (num > heap.peek()) {
      heap.extractMin();
      heap.insert(num);
    }
  }
  
  const result = [];
  while (!heap.isEmpty()) {
    result.unshift(heap.extractMin()); // unshift保持降序
  }
  
  return result;
}

/**
 * 快速选择算法找第K大的数
 * 平均时间复杂度: O(n)
 * 最坏时间复杂度: O(n²)
 * @param {number[]} nums - 输入数组
 * @param {number} k - 第k大的数（1-indexed）
 * @returns {number} 第k大的数
 */
function quickSelect(nums, k) {
  if (k < 1 || k > nums.length) return null;
  
  // 转换为0-indexed，找第k-1大的数在排序后数组中的位置
  return quickSelectHelper(nums.slice(), 0, nums.length - 1, nums.length - k);
}

function quickSelectHelper(nums, left, right, k) {
  if (left === right) return nums[left];
  
  // 选择随机pivot避免最坏情况
  const randomIndex = left + Math.floor(Math.random() * (right - left + 1));
  [nums[randomIndex], nums[right]] = [nums[right], nums[randomIndex]];
  
  const pivot = partition(nums, left, right);
  
  if (k === pivot) {
    return nums[k];
  } else if (k < pivot) {
    return quickSelectHelper(nums, left, pivot - 1, k);
  } else {
    return quickSelectHelper(nums, pivot + 1, right, k);
  }
}

function partition(nums, left, right) {
  const pivot = nums[right];
  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]];
  return i;
}

/**
 * 海量数据TopK问题的分治解决方案模拟
 * 将大数据分块处理，每块找TopK，然后合并
 * @param {number[]} nums - 模拟的大数据数组
 * @param {number} k - 需要找的TopK
 * @param {number} chunkSize - 每块的大小
 * @returns {number[]} TopK结果
 */
function massiveDataTopK(nums, k, chunkSize = 1000) {
  const chunks = [];
  
  // 分块
  for (let i = 0; i < nums.length; i += chunkSize) {
    chunks.push(nums.slice(i, i + chunkSize));
  }
  
  // 每块找TopK
  const allTopK = [];
  for (const chunk of chunks) {
    const chunkTopK = topKLargest(chunk, Math.min(k, chunk.length));
    allTopK.push(...chunkTopK);
  }
  
  // 合并所有块的TopK，再找最终TopK
  return topKLargest(allTopK, k);
}

module.exports = { 
  MinHeap, 
  topKLargest, 
  quickSelect, 
  massiveDataTopK 
};

实际应用场景

搜索引擎: 找出热门搜索词
推荐系统: 选择用户最感兴趣的内容
监控系统: 找出访问量最大的IP地址
数据分析: 销量最高的商品统计
网络安全: 检测异常流量模式

海量数据处理策略

分布式处理：

使用一致性哈希将数据分布到多台机器
每台机器处理自己的数据块，得到局部TopK
汇总所有机器的结果，计算全局TopK

内存优化：

使用位图、布隆过滤器等节省内存的数据结构
分批次处理数据，避免内存溢出
使用压缩算法减少数据存储空间

面试官视角

该题考察候选人对大数据处理的理解：

要点清单: 理解不同算法适用场景；能分析时间空间复杂度；掌握堆数据结构；了解分治思想
加分项: 有大数据处理经验；了解分布式算法；能优化内存使用；知道实际工程问题
常见失误: 只知道排序解法；不考虑内存限制；堆操作实现错误；忽视数据分布特点

延伸阅读

海量数据处理算法 — 经典算法总结
分布式系统原理 — MIT分布式系统课程

岛屿数量问题如何解决？

// 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量
// 输入：grid = [
//   ["1","1","1","1","0"],
//   ["1","1","0","1","0"], 
//   ["1","1","0","0","0"],
//   ["0","0","0","0","0"]
// ]
// 输出：1
function numIslands(grid: string[][]): number {
  // 请使用BFS或DFS实现
}

答案

核心概念

岛屿数量问题是图论中的连通分量问题。每个岛屿是由相邻（水平或垂直相邻）的陆地'1'组成的连通区域。需要遍历整个网格，统计独立的岛屿数量。

算法思路

广度优先搜索（BFS）方案：

遍历网格：扫描每个位置
发现陆地：遇到'1'时，岛屿计数+1
BFS标记：使用队列遍历整个岛屿，将所有'1'标记为'0'
四方向搜索：检查上下左右四个相邻位置
避免重复：已访问的陆地标记为'0'防止重复计算

深度优先搜索（DFS）方案：

使用递归替代队列
更简洁但可能栈溢出（深度过大时）

时间复杂度：O(M×N)，其中M和N分别是网格的行数和列数 空间复杂度：O(min(M,N))，队列最大大小

示例实现

/**
 * 岛屿数量问题 - BFS解法
 * @param {string[][]} grid - 二维网格，'1'表示陆地，'0'表示水
 * @returns {number} 岛屿数量
 */
function numIslandsBFS(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  // BFS遍历岛屿
  const bfs = (startRow, startCol) => {
    const queue = [[startRow, startCol]];
    grid[startRow][startCol] = '0'; // 标记为已访问

    while (queue.length > 0) {
      const [row, col] = queue.shift();

      // 四个方向：上、下、左、右
      const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;

        // 检查边界和是否为陆地
        if (newRow >= 0 && newRow < rows && 
            newCol >= 0 && newCol < cols && 
            grid[newRow][newCol] === '1') {
          queue.push([newRow, newCol]);
          grid[newRow][newCol] = '0'; // 标记为已访问
        }
      }
    }
  };

  // 遍历整个网格
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        count++;
        bfs(row, col);
      }
    }
  }

  return count;
}

/**
 * 岛屿数量问题 - DFS解法
 * @param {string[][]} grid - 二维网格
 * @returns {number} 岛屿数量
 */
function numIslandsDFS(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  const 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 row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        count++;
        dfs(row, col);
      }
    }
  }

  return count;
}

/**
 * 岛屿的最大面积
 * @param {number[][]} grid - 二维网格，1表示陆地，0表示水
 * @returns {number} 最大岛屿面积
 */
function maxAreaOfIsland(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let maxArea = 0;

  const dfs = (row, col) => {
    if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === 0) {
      return 0;
    }

    grid[row][col] = 0; // 标记为已访问
    
    return 1 + dfs(row - 1, col) + dfs(row + 1, col) + 
           dfs(row, col - 1) + dfs(row, col + 1);
  };

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 1) {
        maxArea = Math.max(maxArea, dfs(row, col));
      }
    }
  }

  return maxArea;
}

/**
 * 岛屿的周长
 * @param {number[][]} grid - 二维网格
 * @returns {number} 岛屿周长
 */
function islandPerimeter(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let perimeter = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 1) {
        // 检查四个方向，如果是边界或者是水，周长+1
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        
        for (const [dr, dc] of directions) {
          const newRow = row + dr;
          const newCol = col + dc;
          
          if (newRow < 0 || newRow >= rows || 
              newCol < 0 || newCol >= cols || 
              grid[newRow][newCol] === 0) {
            perimeter++;
          }
        }
      }
    }
  }

  return perimeter;
}

/**
 * 被围绕的区域（翻转被围绕的'O'为'X'）
 * @param {string[][]} board - 二维字符数组
 */
function solve(board) {
  if (!board || board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;

  // DFS标记边界连通的'O'
  const dfs = (row, col) => {
    if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== 'O') {
      return;
    }

    board[row][col] = 'T'; // 临时标记

    dfs(row - 1, col);
    dfs(row + 1, col);
    dfs(row, col - 1);
    dfs(row, col + 1);
  };

  // 标记边界上的'O'及其连通区域
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if ((row === 0 || row === rows - 1 || col === 0 || col === cols - 1) && 
          board[row][col] === 'O') {
        dfs(row, col);
      }
    }
  }

  // 最终处理：'T'恢复为'O'，'O'变为'X'
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (board[row][col] === 'T') {
        board[row][col] = 'O';
      } else if (board[row][col] === 'O') {
        board[row][col] = 'X';
      }
    }
  }
}

module.exports = {
  numIslandsBFS,
  numIslandsDFS,
  maxAreaOfIsland,
  islandPerimeter,
  solve
};

相关变体问题

岛屿的最大面积: 在找岛屿的同时计算面积，返回最大值
岛屿周长: 计算岛屿边界长度，检查每个陆地格子的四个边
被围绕的区域: 将被岛屿完全包围的水域标记出来
岛屿数量II: 动态添加陆地时实时计算岛屿数量（并查集）

实际应用场景

图像处理: 连通域标记，物体识别
地理信息系统: 地形分析，水域划分
游戏开发: 地图生成，区域划分
网络分析: 社交网络中的群组识别
生物信息: 基因序列中的模式识别

优化策略

原地标记: 直接修改原网格避免额外的visited数组
并查集优化: 适用于动态增删岛屿的场景
多线程处理: 将大网格分块并行处理
压缩存储: 使用位图压缩大型稀疏网格

面试官视角

该题考察候选人对图遍历算法的掌握：

要点清单: 理解BFS和DFS区别；正确处理边界条件；能优化空间复杂度；掌握相关变体
加分项: 了解并查集解法；能分析复杂度；有实际应用经验；能处理大规模数据
常见失误: 边界检查遗漏；重复访问未处理；递归栈溢出；不理解连通性概念

延伸阅读

图论基础 — 图遍历算法详解
并查集详解 — 动态连通性问题解决方案

大数字符串运算如何实现？​

海量数据中如何找TopK？​

岛屿数量问题如何解决？​

大数字符串运算如何实现？

海量数据中如何找TopK？

岛屿数量问题如何解决？