峰间的云

外观

算法 ​

算法入门 ​

算法工程师的分类 ​

算法工程师大体上分科研型、工程型、业务型三种，技能点分别侧重在算法思维、工程能力、业务知识。

算法五大特性 ​

算法的五大特征（有穷性、确定性、可行性、输入、输出）是判断一个操作序列是否为“合格算法” 的核心标准，也是算法设计、优化、验证的基础。

有穷性（Finiteness）

有穷性（Finiteness）是指算法必须在执行有限个步骤后终止，且每个步骤的执行时间都有明确的上限。换句话说，算法不能陷入无限循环或无限递归，必须存在一个 “终止条件”，确保在有限时间内输出结果。

确定性（Definiteness）

确定性（Definiteness）是指算法中的每一个步骤都必须有明确的、无歧义的定义，对于相同的输入，算法总能产生相同的操作序列和输出结果。换句话说，算法的每一步都不存在 “二选一” 的模糊性，计算机能够严格按照步骤执行。

可行性（Feasibility）

可行性（Feasibility）是指算法中的每一个步骤都必须能够通过计算机的基本操作（如算术运算、逻辑运算、数据存储 与读取）在有限时间内完成。换句话说，算法的步骤必须是 “可实现” 的，而不是抽象的、无法落地的理论构想。

输入（Input）

输入（Input）是指算法执行前需要从外部获取的初始数据。输入可以是 0 个或多个，且输入数据的格式、范围必须有明确的定义。0 个输入意味着算法不需要外部数据，直接通过内部逻辑产生输出（如生成固定序列的算法）。

输出（Output）

输出（Output）是指算法执行完成后产生的结果，用于解决特定问题。输出必须是 1 个或多个，且输出结果必须与输入数据存在明确的对应关系（即算法的 “问题解决目标”）。

算法性能评价标准 ​

时间复杂度
空间复杂度

最好、最坏、平均、均摊复杂度 ​

常见复杂度曲线 O(1) O(n) O(logn) O(n²) ​

六大算法思想 ​

暴力枚举思想（基础兜底） ​

分治思想（拆分、递归、合并） ​

贪心思想（局部最优） ​

动态规划DP（保存子问题） ​

回溯思想（深度优先、试错回退） ​

分支限界（广度优先最优解） ​

核心基础算法 ​

查找算法 ​

顺序查找 ​

Dichotomy 二分法查找 ​

左边界、右边界、精准匹配。

在已从小到大排序的数组（数组内元素均为数字）中找到给定的数字对应的下标
javascript
function dichotomySearch(arr, num) {
  var low = 0;
  var high = arr.length - 1;
  var mid = Math.floor((low + high) / 2);

  // while循环的判断条件是high - low > 1
  while (high - low > 1) {
    if (num === arr[low]) {
      return low;
    }
    if (num === arr[high]) {
      return high;
    }
    if (num === arr[mid]) {
      return mid;
    }
    if (num > arr[mid]) {
      low = mid;
      mid = Math.floor((low + high) / 2);
    } else {
      high = mid;
      mid = Math.floor((low + high) / 2);
    }
  }

  // 如果没找到，则返回-1
  return -1;
}
求一个数n的平方根
javascript
/**
 * 计算平方根
 * @param  {number} n         需要求平方根的目标数字
 * @param  {number} deviation 偏离度（允许的误差范围）
 * @return {number}           返回平方根
 */
function square(n, deviation) {
  let max = n;
  let min = 0;
  let mid = (max - min) / 2;
  const isAlmost = (val) =>
    val * val - n <= deviation && n - val * val <= deviation;
  while (isAlmost(mid) === false) {
    if (mid * mid > n) {
      max = mid;
      mid = (max + min) / 2;
    } else if (mid * mid < n) {
      min = mid;
      mid = (max + min) / 2;
    }
  }
  return mid;
}

哈希查找 ​

树形查找 ​

各查找算法工程选型对比 ​

排序算法 ​

简单排序：冒泡、选择、插入 ​

Bubble Sort 冒泡排序 ​

冒泡排序的思想是，比较相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过n-1轮，就完成了所有数的排序。

基本实现
javascript
function bubbleSort(arr) {
  let len = arr.length;
  while (len > 0) {
    for (let i = 0; i < len - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        const temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
    len--;
  }
  return arr;
}
优化思路

在上面的方案中，如果我们经过第一轮排序就成功将所有元素正确排好序了的话，仍然会继续遍历。 这里可以每一轮开始遍历时，加一个初始值为false的changeFlag标记， 当本轮有进行过换位的话，就接着遍历下一轮。 当本轮没有进行过换位操作的话，则说明已经排序完毕，就可以直接退出循环，没必要接着遍历了。

具体实现还是比较简单的，大家自行尝试，这里就不写了。

选择排序 ​
插入排序 ​

高级排序：希尔、归并、快速排序 ​

希尔排序 ​
归并排序 ​
快速排序 ​
快速排序

快速排序由于排序效率在同为 O(N\*logN) 的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想——分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个。

分治法

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conquer Method)。

快排的实现

该方法的基本思想是：

  • 先从数列中取出一个数作为基准数（一般是以中间项为基准）；
  • 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
  • 再对左右区间重复第二步，直到各区间只有一个数。

代码实现

javascript
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  // pivot：枢纽、中心点
  var pivotIndex = Math.floor(arr.length / 2);
  // 找基准，并把基准从原数组中删除
  var pivot = arr.splice(pivotIndex, 1)[0];
  // 定义左右数组
  var left = [];
  var right = [];

  // 比基准小的放在left，比基准大的放在right
  arr.forEach(function (val) {
    if (val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  });

  // 递归
  return quickSort(left).concat([pivot], quickSort(right));
}

堆排序 ​

非比较排序：计数、桶、基数排序 ​

十大排序复杂度、稳定性、场景终极对比表 ​

递归与回溯算法 ​

递归思维、递归栈、终止条件 ​

回溯模板（万能模板） ​

组合、子集、全排列问题 ​

迷宫、八皇后经典案例 ​

贪心算法 ​

贪心核心思想与适用条件 ​

区间调度问题 ​

哈夫曼编码 ​

贪心经典面试题汇总 ​

动态规划DP ​

DP核心：重叠子问题、最优子结构 ​

DP万能解题步骤 ​

一维DP：爬楼梯、最大子数组 ​

二维DP：最长公共子序列、最短路径 ​

背包问题（01、完全、多重） ​

图论经典算法 ​

最短路径 Dijkstra ​

Floyd 多源最短路 ​

拓扑排序 ​

最小生成树 Prim / Kruskal ​

工程级算法 ​

哈希与一致性哈希 ​

普通哈希原理与缺陷 ​

一致性哈希算法（分布式必备） ​

虚拟节点解决倾斜问题 ​

工程应用：分库分表、Redis集群 ​

海量数据工程算法 ​

布隆过滤器（去重、判存在） ​

LRU、LFU 缓存淘汰算法 ​

滑动窗口算法 ​

限流算法：漏桶、令牌桶 ​

字符串匹配算法 ​

暴力匹配 ​

KMP 算法（工程重点） ​

Rabin-Karp 滚动哈希 ​

各类算法万能解题模板 ​

二分模板 ​

快慢指针模板 ​

滑动窗口模板 ​

DFS/BFS 模板 ​

回溯模板 ​

DP状态转移模板 ​

高频面试题分类精讲 ​

高频面试题 ​

画星号 ​

问题描述

实现一个函数，入参为数字 n，输出如下图所示的字符串。

解决方案
javascript
function drawAsterisk(n) {
  function getRepeatStr(num, repeatStr) {
    return new Array(num).fill(repeatStr).join("");
  }
  function log(str) {
    console.log(str);
  }

  const arr = [];
  const sumLength = 2 * n - 1;
  for (let i = 0; i < n - 1; i++) {
    const numOfStar = 2 * i + 1;
    const numOfSpaces = sumLength - numOfStar;
    const sideSpaces = getRepeatStr(numOfSpaces / 2, " ");
    arr.push(sideSpaces + getRepeatStr(numOfStar, "*") + sideSpaces);
  }
  // 画上半部分
  arr.forEach(log);
  // 画中间一行
  console.log(getRepeatStr(2 * n - 1, "*"));
  // 下半部分与上半部分层是轴对称的，直接 `reverse()` 反转下就可以直接用
  arr.reverse();
  // 画下半部分
  arr.forEach(log);
}
drawAsterisk(2);

90度旋转二维数组 ​

问题描述

javascript
const rawArr = [
  ["1", "2", "3", "4", "5"],
  ["6", "7", "8", "9", "a"],
  ["b", "c", "d", "e", "f"],
  ["g", "h", "i", "j", "k"],
  ["l", "m", "n", "o", "p"],
];

修改 rawArr，使达到如下所示的 90 度旋转效果

json
[
  ["l", "g", "b", "6", "1"],
  ["m", "h", "c", "7", "2"],
  ["n", "i", "d", "8", "3"],
  ["o", "j", "e", "9", "4"],
  ["p", "k", "f", "a", "5"]
]
解决方案

使用新数组再覆盖原数组

如果直接先生成一个新数组， 然后逐个将旧数组里的元素赋值到新数组中的对应位置，那就很简单了。

先列数据看规律：

  • (0, 0) => (0, 4)
  • (0, 1) => (1, 4)
  • (0, 2) => (2, 4)
  • (0, 3) => (3, 4)
  • (0, 4) => (4, 4)
  • ...
  • (2, 0) => (0, 2)
  • (2, 1) => (1, 2)
  • (2, 2) => (2, 2)
  • (2, 3) => (3, 2)
  • (2, 4) => (4, 2)
  • ...
  • (4, 0) => (0, 0)
  • (4, 1) => (1, 0)
  • (4, 2) => (2, 0)
  • (4, 3) => (3, 0)
  • (4, 4) => (4, 0)

可以看出规律是：oldArray(x, y) => newArray(y, 5 - 1 - x)

javascript
const rawArr = [
  ["1", "2", "3", "4", "5"],
  ["6", "7", "8", "9", "a"],
  ["b", "c", "d", "e", "f"],
  ["g", "h", "i", "j", "k"],
  ["l", "m", "n", "o", "p"],
];

function rotate90(arr) {
  const length = arr.length;
  // 直接这样写是不行的，5个子数组实际对应的是同一个对象，修改一个其实是5个子数组里的值都变了
  // const tempArr = new Array(length).fill(new Array(length))
  // 这里去掉fill(1)的话就无法构造成二维数组了
  const tempArr = new Array(5).fill(1).map(() => new Array(5));
  arr.forEach((row, rowIdx) => {
    row.forEach((col, colIdx) => {
      tempArr[colIdx][length - rowIdx - 1] = arr[rowIdx][colIdx];
      console.log(
        `(${rowIdx}, ${colIdx}) => (${colIdx}, ${length - rowIdx - 1})`,
      );
    });
  });
  return tempArr;
}
console.log(rotate90(rawArr));

业务架构中的算法落地 ​

MySQL索引与B+树算法落地 ​

分库分表与哈希、RANGE分区算法 ​

负载均衡算法原理与选型 ​

限流、熔断、削峰算法 ​

缓存体系背后的算法思想 ​

天上的神明与星辰，人间的艺术和真纯，我们所敬畏和热爱的，莫过于此。

Copyright © 2009-2026 Yakima Teng. All rights reserved.