算法笔记

2026-7-17

原始笔记链接：https://cloud.seatable.cn/dtable/external-links/59b453a8639945478de2/

0005 DFS和BFS的区别

以二叉树为例，bfs和dfs的具体区别是什么？他们的性能有什么差距

DFS 使用函数递归调用实现

1
2
3
4
5
6


  runNode = (node) => {
    if (!node) return;
    fn(node.val);
    this.runNode(node.left);
    this.runNode(node.right);
  }

BFS 使用队列实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


  runNode = (node) => {
    let queue = [];
    queue.push(node);
    while (queue.length > 0) {
      let curr = queue.shift();
      fn(curr.val);
      queue.push(curr.left)
      queue.push(curr.right);
    }
  }

性能上都一样，一个按照深度节点遍历，一个优先按照层遍历。

BFS 会用到一个额外的数组，存放队列，所以占用内存稍微多一点。

0006 DFS和BFS分别实现深拷贝一个对象

不考虑环形引用，那么就循环对象的键值对，然后分别拷贝即可（函数递归调用自己）

0036 使用递归迭代两种办法，实现数组flat函数

递归就是在一个函数内部调用这个函数

1
2
3


fn(node) {
	return fn(node.val)
}

迭代就是一个变量，等于某个函数执行这个变量后的结果

1
2
3
4
5
6


arr = fn(arr)

const fn = (arr) => {
    if (!arr.some(item => Array.isArray(item))) return arr;
	return [].concat(...arr);
}

0054 冒泡排序，时间复杂度

冒泡排序的时间复杂度是n^2，循环两次实现

改进方法：并归排序，快速排序，时间复杂都是 nlogn

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = i; j < len; j++) {
      // compare arr[i] and arr[j] and change their position
      if (arr[i] > arr[j]) {
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
    }
  }
  return arr;
}

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let left = [];
  let right = [];
  let tmp = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > tmp) {
      right.push(arr[i]);
    } else {
      left.push(arr[i]);
    }
  }
  return quickSort(left).concat(tmp).concat(quickSort(right));
}

0059 两个数组的最长公共子序列怎么计算

最长公共子序列——动态规划，参考这里 https://blog.csdn.net/hj7jay/article/details/79350978 子序列不一定连续

最长公共子串，公共子串是连续的，直接循环子串即可满足

0067 把一个离散的数组变成子序列，连续的数组

数组都是整数，那么先排序，然后循环一下

设置一个start end 然后循环原始数组，如果是连续的，继续循环；如果不是连续的，设置 end 然后把子数组创建一个新的数组，放在原始数组中，最后就是二维的连续数组

0071 设计字符串匹配算法

算法要求：判断A字符串中是否有B字符串。如果有返回所在的位置。

思路1：使用 indexOf 字符串内置的方法实现

1

return str1.indexOf(str2)

思路2：循环字符串，然后依次比较子字符串是否相等

1
2
3
4
5
6
7


  checkStr = (str1, str2) => {
    let len = str2.length;
    for (let i = 0; i < str1.length; i++) {
      if (str1.slice(i, i + len) === str2) return true;
    }
    return false;
  }

0081 打印对称数

对称数：也就是回文数，就是数字转换成字符串，然后转换成数组，翻转后和原数字一样

这里就是循环 0-10000 然后判断每一个是否是回文数

数字-字符串-数组转换比较耗时，如果追求时间快速，那么直接循环字符串比较更快

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


  getNumber = () => {
    let result = [];
    for (let i = 1; i <= 10000; i++) {
      if (checkNumber(i)) {
        result.push(i);
      }
    }
    return result;
  }

  checkNumber = (n) => {
    return String(n).split('').reverse().join('') === String(n);
  }

0082 移动数组中的0到末尾

把一个数组中的0，全部移动到最后，需要原地算法

时间复杂度是N

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


  moveZero = (arr) => {
    let timer = 0;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0);
        i--;
        timer++;
      }
      if (timer >= arr.length) {
        return arr;
      }
    }
    return arr;
  }

改进版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


  moveZero = (arr) => {
    let timer = 0;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        timer++;
        i--;
      }
    }
    for (let i = 0; i < timer; i++) {
      arr.push(0);
    }
    return arr;
  }

0085 两数之和

数组中，某两数之和是 sum 求这两个数的位置

1、入门思路，两层循环 N * N

2、进阶思路，外层循环N，内层使用二分法循环，这个复杂度是 N * logN

对应的四数之和，三数之和也是类似的原理（当然时间复杂度就变化了）

0087 把一个部门的 array 转换成部门的 tree 结构

先假设全部的数据都是正确的，只有一个根节点，不存在部门互相引用（不是图，不需要标记）

每一个部门有 parent_dep 和 child_dep 父节点和子节点

1、首先把数组循环一次，关系存放在对象中，保存父节点和子节点的对象，并找到根节点

2、把根节点找到，然后新建树的根节点，然后获取子节点，DFS 找到子部门

3、最后返回整个树节点

0099 输入整数，输出一个反转后的字符串

数字转换成字符串，字符串分割成数组，数组反转，合并成字符串

0218 原地算法

不使用额外的堆内存空间（不使用数组和对象，可以使用简单变量）

使用：倒转数组；判断回文（双指针算法）

0219 笛卡尔积

数学中，两个集合的乘积，叫做笛卡尔积

拼音中，A 集合是声母的集合，B集合是韵母的集合，那么 A 和 B 的笛卡尔积就是全部读音的集合（不考虑特殊情况）

可以是 N 个集合的笛卡尔积

运算规则：不符合交换律和结合律，求并集和交集满足分配率

详情参考：

https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E4%B9%98%E7%A7%AF

1
2
3


举例：集合 A = {1, 2}, B = {a, b, c};
笛卡尔积 A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
笛卡尔积 B x A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}

0220 最小花费爬楼梯

最小花费爬楼梯：这是经典DP算法，最小花费，也就是爬上一个楼梯，还是跳过一个，也就是可以转换成递推公式

Fn = min(Fn-2 + An-2, Fn-1 + An-1)

这样就可以算出最的花费（类似最小花费买卖股票）。

注意细节：开始的前两个可以直接跳上去，所以 F0 = F1 = 0。然后爬上去，最后需要计算 Fn 的结果，爬到楼梯顶端。

0223 回溯算法

核心代码：循环数组，然后把当前项一次放到临时数组中，然后判断临时数组是否满足条件。

如果满足条件，直接放到结果数组中。
如果不满足条件，如果没有达到条件，那么进一步回溯。
如果超过条件，那么返回，继续循环下一个条件。

注意点：目标数组中使用允许重复，全部样本中是否有重复的对象。

备注：如果要求全部样本中没有重复的对象，尽量避免使用 array.includes 判断 tmp 中是否存在另一个元素，这样算法复杂度较差。最好使用对象索引判断一下，减少复杂度。

应用：大部分排列组合问题、硬币找零问题（不能使用贪心算法）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


if (tmp.length > K || sum(tmp) > K) {
  let item = [...tmp];
  list.push(item);
  return;
}

for (let i = start; i < end; i++) {
  tmp.push(arr[i]);
  backtrack(tmp, list);
  tmp.pop(arr[i]);
}

0224 动态规划

动态规划小结

核心代码：当前的结果可以使用前面的结果表示。那么获取初始状态，以及获取递推公式，然后执行一次循环，即可算出N次结果的值。

1

f(n) = F(a * f(n - 1) + b * f(n - 2) +);

动态规划的实质是，把一个实际问题，转换成数学的递推公式（通项公式），然后使用排列组合或者递推的方式计算结果。

应用：斐波那契函数、打家劫舍问题，背包问题，复杂排列组合问题

难点：把一个实际问题，转换成数学的递推公式

例子：排列组合数据量较大时，回溯方法内存溢出，使用DP解决

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


var fn = (nums, target) => {
  nums.sort((a, b) => b - a);
  let dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 1; i <= target; i++) {
    let tmp = 0;
    // 这里可以优化
    nums.forEach(num => {
      if (i - num >= 0) {
        tmp += dp[i - num];
      }
    });
    dp [i] = tmp;
  }
  return dp[target];
}

动态规划处理最大子序和（给定一个数组，求最大自序和）

1. 一个数组最大的自序和，那么等于每一个项结尾的自序和的最大值

1
2


maxList = [max1, max2, max3,,, maxn];
Math.max(...maxList)

2. 每一个项为结尾的最大自序和，可能是当前的 nums[i] 或者是 f(n - 1) + nums[i]

1
2
3
4
5
6
7
8
9


function fn(nums) {
  let tmp = 0;
  let maxList = [];
  for (let i = 0; i < nums.length; i++) {
    tmp = Math.max(tmp + nums[i], nums[i]);
    maxList.push(tmp);
  }
  return Math.max(...maxList);
}

0225 获取字符串数组中，不重复字符串长度的最大值

获取字符串数组中，不重复字符串长度的最大值

基本算法是字符串算法，进阶算法是位运算，关键是判断两个字符串是否有相同的字母

1、先把字符串数组转换成对象数组，对象包括字符串的长度，字符串本身

2、双层循环这个对象数组，把每一个组合拿出来，作为新的数组（每一项是对象，包括长度的乘积，两个子字符串）

3、这个数组根据长度的乘积排序

4、循环数组，如果两个字符串没有公共字母，那么直接返回。如果有，继续下一个

判断两个字符串是否有公共的字母？

先把字符串遍历一次，获取字典。然后遍历这两个字典的 key 如果有重复，就是有公共的字母。

可以做一个临时变量 dict: {} key 是字符串，value 是字典，这样可以减少计算字符串的字符的数量。

0226 滑动窗口双端队列

滑动窗口双端队列（求滑动窗口的最大值-最小值）

数据结构：一个滑动窗口数组存放数组下标，一个结果数组

算法：循环数组，将窗口外部的下标去掉，将窗口中小于当前数字的项去掉，然后把当前的数组的项放进去，这样始终保证窗口第一项对应的数组的值是最大的。当滑动到窗口区间时，把窗口的数字放入结果数组中。

0227 二分算法

二分算法

二分，判断，然后递归或者while循环；

二分前提是排序的数组；确定二分的边界和最终条件，避免死循环；

二分算法可以用来快速查找数组中是否有指定元素；或者快速排序法（选择数组中第一个元素作为根元素，然后定义两个空数组，分别存放比根元素大的元素和小的元素，然后遍历数组剩下的项和根元素对比，当道两个空数组中，然后把大数组，根元素，小数组合并起来即可）大数组和小数组继续执行二分法排序。

0228 贪心算法

贪心算法

主要用于可以把问题逐步分解的情况，贪心算法可能不是最好的办法，所以需要考虑是否适合使用贪心算法。

主要可以解决的问题是背包问题（重量有限，尽量装价值最多的商品）那么可以计算不同产品的价格重量比值，然后存放不同的商品，或者硬币找零问题等等。

0229 二叉树的层序遍历

1、基本二叉树的层序遍历：使用BFS遍历，设置临时队列，每次循环临时队列，放置每一层的元素。

2、二叉树的锯齿层序遍历：遍历一层后，如果是奇数或者偶数，然后把结果数组 reverse 一下

3、二叉图的左视图右视图：BFS遍历每一层，获取每一层的第一个节点的 value 即可（使用DFS比较复杂）

0230 拼图算法和思路

如何用算法完成一个10000块的拼图？

1、复杂问题简单化：100块拼图，规范的拼图，没有重复的拼图，存储不限制，时间不限制

2、解决简单的问题

思路1：图 BFS 或者 DFS 算法

给出全部的拼图数组 arr，每一项是一个对象。对象的 ID 是某一块的唯一标识。四个边是某个属性值，全部拼图只有另一个和某一个完全一样

1
2
3
4
5
6
7
8
9


let arr = [
  {
    id: '',
    left: '',
    right: '',
    top: '',
    bottom: '',
  }
];

关键是从某一个节点开始，然后获取相邻的节点（单项指针，或者对象的唯一键值对）。

把全部的节点遍历一次，存放在对象中。对象的键是属性，值是 ID。

1
2
3
4
5
6
7


let dict = [];
for (let i = 0; i < arr.length; i++) {
  let { left, right, top, bottom, id } = arr[i];
  // 把这些属性全部存放到字典中(先假设属性都不同)
  dict[left] = id;
  dict[right] = id;
}

然后任意选择一个节点，DFS 获取邻接节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


let init = arr[0];
let res = [];
res.push(init);
while(res[res.length - 1].right) {
  let next = dict[res[res.length - 1].right];
  if (next) {
    res.push(next);
  }
}
console.log(res);
// 先把一行拼出来
// 然后继续遍历其他几个方向

这个方法可以解决问题。因为已经在字典中存放了属性值，那么查找的速度比较快，时间复杂度可以接受。

实际我们拼图时，人脑不会采用这样的思路

因为遍历全部的节点需要时间，短时间内不能记住全部的节点属性，从一个点，找到四个相邻节点比较困难。

那么可以采用下面的算法改进

思路2：聚类算法

实际拼图时，往往先根据拼图上的一些特点（颜色相同，某些曲线相同，都含有某个图案，是否是边界点等特点），进行人脑聚类处理。

我们假设相邻的图片相似度很高，然后可以用聚类的算法，把全部图案分成若干群，每一个群组内部根据取值直接拼接，最后组合成较大的部分。可能有一些边缘的极端值，最后处理，这个符合人脑的思路

归纳：解决问题的思路

1、把复杂的问题简单化（10000的拼图，简化成100个，数量级的简化；四边凹凸不平的拼图，简化成规范的拼图，难度的简化；可能重复的拼图，简化成完全无重复的拼图，极端值边界值的简化；拼图是2维的，可以简化成1维的链表排序或者节点排序）

2、解决这个简单的问题（核心拼图算法）；或者拆成多个步骤解决；或者递推解决

3、把简答的解法复杂化（考虑数量级，考虑内存，考虑多维数据，考虑特殊值极端值影响）

1
2
3
4
5
6
7
8
9


let arr = [
  {
    id: '',
    color: 'red' | 'blue' | 'green' | null,
    graph: 'line' || 'circle' | null,
    is_icon: boolean,
    is_boundary: boolean,
  }
];

思考3：不完美状态下的拼图

实际上，很多情况并不是完美的拼图，也就是存在某个区块缺少，或者相邻的区块不匹配的情况。

那么这时候就不能直接使用精确匹配，可以使用模糊匹配，即寻找一个图片的下一个图片，那么剩余的图片中，哪一个图片和当前图片的匹配度最高，就选择哪一个。当然这是贪心算法的实现。如果某个节点存在多个选择，那么就是回溯算法实现。

0233 双指针算法

双指针算法

使用条件：有序数组（无序数组先排序）。

分类：快慢指针和对撞指针。对撞指针用于小船载人问题；快慢指针用于判断链表中是否有环，排序数组去重操作等。

判断链表中是否有环，也可以使用对象唯一性判断；

排序数组去重操作，可以使用一次循环，然后splice操作；或者使用对象唯一性操作；或者使用 set 操作（后两种较复杂，适应于无序数组的去重）。两数之和、两数乘积之和，回文字符串等都可以使用双指针算法。

数组中指针用法：for循环数组，一个是当前的i，设置另一个指针pointer，这样可以指向不同的数组，进行处理

快慢指针

1
2
3
4
5
6
7


// 需要预处理next下一个节点是否存在等
let a = head.next;
let b = head.next.next;
while (a.next) {
  a = a.next;
  b = b.next.next;
}

对撞指针

在一个排序数组中，找到两个数字，使得其中的和等于 target

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// 输入: numbers = [2, 7, 11, 15], target = 9
// 输出: [1,2]
let fn = (numbers, target) => {
	let left = 0;
	let right = numbers.length - 1;
	while (left < right) {
		let tmp = numbers[left] + numbers[right];
		if (tmp === target) {
			return [left, right];
		}
		if (tmp < target) {
			left++;
		}
		if (tmp > target) {
			right--;
		}
	}
	// 不满足的情况下，返回 null
	return null;
}

console.log(fn([2, 7, 11, 15], 9));
console.log(fn([2, 7, 10, 11, 15], 21));

0234 有序数组转换成等高的二叉搜索树

等高的二叉搜索树，那么根节点必然是数组的中位数。数组已经排序，那么使用递归的思路直接将排序的有序数组转换成二叉搜索树，基本思路如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


function transArrayToBST (arr) {
  // 辅助函数
  const trans = (start, end) => {
    if (start > end) {
      return null;
    }
    if (start === end) {
      return new TreeNode(arr[start]);
    }
    // start < end 递归
    let mid = Math.floor((start + end) / 2);
    const midNode = new TreeNode(arr[mid]);
    midNode.left = trans(start, mid - 1);
    midNode.right = trans(mid + 1, end);
    return midNode;
  }
  return trans(0, arr.length - 1);
}

0235 无重叠区间算法

无重叠区间

可以使用贪心算法，或者DP算法。因为区间的顺序可以变化，那么就优先使用贪心算法。可以先按照右侧区间排序，然后循环数组。如果前一项和后一项没有交集（也就是前一项的右侧区间 <= 后一项的左侧区间，那么这一项就是不重复区间，可以保留。如果重复，那么这一项就需要去掉）

0240 完全平方数

1、完全平方数：判断一个数 N 能被多少个完全平方数表示例如 8 = 4 + 4 最少就是2个。

思路：先设置一个队列 queue = [], queue.push([n, 0])，当队列长度大于1时，从队列第一个拿出来，然后循环 for i= 0； i < item; i++ 然后判断结果是否满足，然后继续循环。如果结果恰好是0，那么完成递归，返回最小的个数即可。

优化：如果队列中已经有K这个数字，那么不需要再次push，如果N很大，这样时间太差了

（使用一个 MAP 记录已经存入的数字，再次push前判断即可）。

https://github.com/Michael18811380328/LeetCode/commit/eaceede8c35e9c92019391c18c2d9a318bda2b89#diff-0d424506e331420140e047a67d11a38d28c481d4645c5c4fb5ecd4bd1046c43c

0243 单词最短路径

2、单词最短路径给定输入和输入单词 input output 还有一个单词列表，每次转换一个单词，判断最少多少次能够转换完成。

思路：先优化一下字典，把原来的单词去掉（如果存在）

辅助函数：判断两个单词是否只有一个字母不同

把开始的单词放在队列中，当队列的长度大于0，把队列中当期的元素拿出来，然后循环单词列表，如果有满足的单词（只有一个字母不同）把这个单词继续放在临时队列中。循环一次队列后，然后次数加1，把临时队列中全部的新单词，放在原始队列中。

循环结束条件：如果某个单词等于结果单词，那么就结束。如果最后没有相邻的单词，那么返回0。优化：在单词放入前，先记录到map中，避免两个单词互相为相邻单词，造成死循环问题。

https://github.com/Michael18811380328/LeetCode/commit/eaceede8c35e9c92019391c18c2d9a318bda2b89#diff-6b11e7950a42293fd05aa8fb0a0d3c22e0064f96bd7b8bdde504c09df544b652

0349 希尔排序算法

希尔排序（Shell Sort）是一种基于插入排序的算法，属于就地排序算法，即不需要额外的存储空间进行排序。希尔排序是直接插入排序算法的一种更高效的改进版本。

以下是使用JavaScript实现希尔排序的一个简单例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


function shellSort(arr) {
    var len = arr.length;
    var gap = Math.floor(len / 2);

    // 逐步缩小间隔，进行插入排序
    while (gap > 0) {
        for (var i = gap; i < len; i++) {
            var temp = arr[i];
            var j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap = Math.floor(gap / 2);  // 间隔缩小
    }
    return arr;
}

// 使用例子：
var arr = [5, 3, 7, 4, 6, 8];
console.log("Original array: " + arr);
shellSort(arr);
console.log("Sorted array: " + arr);

案例2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


function shellSort(arr) {
  let len = arr.length;
  let gap = Math.floor(len / 2);
  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      let temp = arr[i];
      let j = i - gap;
      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j];
        j = j - gap;
      }
      arr[j + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

在这个代码中，首先创建一个数组 `arr`，然后逐步减小间隔值 `gap`，对每个间隔值下的元素进行插入排序。在每次迭代中，通过比较和交换元素来对当前间隔内的元素进行排序。当间隔值减小到0时，整个数组就被排序好了。

需要注意的是，希尔排序的时间复杂度在最好和最坏的情况下可能达到 O(n^2)，但在平均情况下可以接近 O(n log n)，因此它通常在内存和性能要求较高的场合使用。

实际使用不多，目前面试题见到的不多（主要是快排和并归），了解即可。

0245 链表转换

常规思路，因为不能直接获取链表的长度，先把链表转换成数组，这样可以获取到不同节点的索引，以及总长度，然后使用双指针，把链表从开头和结尾加入，重新构建新链表）

高级思路：先用快慢指针获取链表的中间节点，把链表分成两个子链表，然后把后面的链表反转，把两个链表合并即可。——并归

0289 链表常见考点

链表：

1、链表有环，那么使用快慢指针判断是否有环。快慢指针肯定存在一个重合的时刻

2、链表找中间的节点，也使用快慢指针。当快指针结束时，慢指针所在的位置就是中间的节点。基于中间的节点，可以判断链表是否回文等操作。

3、双指针：快慢指针、对撞指针。链表优化可以考虑使用快慢指针。

0334 A star 算法

A* 寻路算法：A-star search algorithm 是一种在图形平面上，有多个节点的路径，求出最低通过成本的演算法。

使用场景：电子地图的导航功能。只需要输入起点和终点，电子地图就会快速的为我们规划出一条最短路线。

基础算法是网格寻路算法：

https://cloud.seatable.cn/workspace/32/dtable/%E9%AB%98%E9%A2%91%E7%9F%A5%E8%AF%86%E7%82%B9/?tid=0000&vid=Dj51&row-id=BFdHRc_tS3CM17g3FB8QqQ

A* 算法的基本思想是：通过启发式公式，对当前搜索状态的下界进行估计，并且优先搜索更有潜力的解（根据估计的下界来确定）。

如果是传统的 BFS 算法，那么在队列中还没有遍历的节点权重都是一样的（也就是遍历全部的节点，广度优先）。在放入节点时，如果先计算一下当前节点的下界（下界，就是当前已经行走的步数+当前节点到终点的距离，不考虑障碍物），然后给出下界，那么由于障碍物，实际的距离要大于等于这个下界。

那么我们对需要遍历的节点，都计算出当前的下界，然后放在优先队列中，优先处理下界最小（即性能潜力最高的节点），就实现了 A star 算法的基本思路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


# A* 搜索算法伪代码
queue = PriorityQueue()
queue.put(start)

while queue not empty:
    (_, cur) = queue.get()
    
    # 这里的 hamiltonDistance 函数用于计算两点之间的哈密顿距离。
    lower_bound = hamiltonDistance(start, cur) + hamiltonDistance(cur, end)
    if cur == end: break
    for node in cur.neighbors():
        if IsInGrid(node) and not IsVisited(node):
            queue.put((lower_bound, node))
            MarkVisited(node)

参考：leetcode 官方公众号文章链接

https://mp.weixin.qq.com/s?__biz=Mzg5MjcwMDc3MQ==&mid=2247500779&idx=1&sn=34f744c61f2e21076debf37de126245e&chksm=c03892e7f74f1bf15bd60394c29656d9fba6e405515bc015289220a81c46e8b40d9a72d5207d

0335 网格寻路算法

问题：从无数条线路中找到最短路径（中等）

给你一个网格，其中每个单元格不是空就是障碍物。每一步，您都可以在空白单元格中上、下、左、右移动。请找出从左上角到右下角最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 null。

解决：BFS

我们可以使用队列，来实现广度优先搜索算法：首先将起点插入队列，然后循环的从队列首部取出一个点作为当前访问点，并将当前访问点的各个邻居点依次插入到队列的尾部，直到遇到终点或是队列为空。此外，我们还需要记录已经被访问过的点，以免算法陷入死循环。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


queue = Queue()
queue.put(start)

while queue not empty:
    cur = queue.get()
    if cur == end：
	    break
    for node in cur.neighbors():
        if IsInGrid(node) and not IsVisited(node):
            queue.put(node)
            MarkVisited(node)

改写后的 JS 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


const start = new Node({
	x: 0,
	y: 0,
	visited: true, // 是否走过
	length: 1, // 当前走过的步数
});

let queue = [];
queue.push(start);

while(queue.length > 0) {
	let current = queue.shift();
	// 已经遍历到最后一个节点，直接返回
	if (current === end) {
		break;
	}
	let neiborhoods = getNeiborhood(current);
	for (let i = 0; i < neiborhoods.length; i++) {
		let node = neiborhoods[i];
		// 或者在这里判断是否到达终止节点
		if (!node.isvisited) {
			queue.push(node);
			node.isvisited = true;
		}
	}
}

广度优先搜索算法在访问了网格中的所有点之后，才找到最短路径。这种搜索效率似乎并不高。

优化算法就是 A star 算法，https://cloud.seatable.cn/workspace/32/dtable/%E9%AB%98%E9%A2%91%E7%9F%A5%E8%AF%86%E7%82%B9/?tid=0000&vid=Dj51&row-id=JKvrS6J3SYiIhzExsgWIGw

0336 哈密尔顿距离

哈密顿距离定义是：对于二维平面上的两点A，B，那么它们的哈密顿距离D表示为：

hamilton 距离

1

const D = Math.abs(x1 - x2) + Math.abs(y1 - y2);

主要用于网格算法（国际象棋，网格寻址，最短路径等）

0808 滑动窗口算法

TCP 中的滑动窗口（Sliding Window）算法的复杂度，主要取决于窗口的大小，和数据包的传输频率。

在理想情况下，滑动窗口算法的时间复杂度为 O(1)，因为发送方和接收方只需要维护一个窗口的状态，发送和接收数据包时只需要更新窗口的边界。

但是，在实际实现中，滑动窗口算法的复杂度可能会受到以下因素的影响：

窗口大小的调整：当窗口大小需要调整时，发送方和接收方需要更新窗口的状态，这可能会导致 O(log n) 的复杂度，其中 n 是窗口大小。
数据包的传输频率：当数据包的传输频率很高时，发送方和接收方需要频繁地更新窗口的状态，这可能会导致 O(n) 的复杂度，其中 n 是数据包的数量。
丢包和重传：当数据包丢失或需要重传时，发送方和接收方需要更新窗口的状态并重新发送数据包，这可能会导致 O(n) 的复杂度，其中 n 是数据包的数量。

综上所述，TCP 中的滑动窗口算法的复杂度主要取决于窗口大小和数据包传输频率，在理想情况下为 O(1)，但在实际实现中可能会受到窗口大小调整、数据包传输频率和丢包重传等因素的影响，导致复杂度为 O(log n) 或 O(n)。

0710 数据结构的概念

下面的概念不难，平时可能用的不多，考试会考。

1、稀疏矩阵的压缩：一个二维矩阵大部分是0，少量有内容，就是稀疏矩阵。可以通过三元组表的顺序结构存储（i, j, value）进行压缩，三元组表的链式存储就是十字链表。稀疏矩阵的压缩算法，常用栅格图的压缩（相同的色值）可以使用同一个位置进行标记，避免使用原始图片。

2、节点的度：结点拥有的子树个数，称为结点的度。

3、树的度：树内各结点的度的最大值,也就是树内结点拥有子树的最大值。

4、满二叉树：二叉树节点都是满的（高度是H，节点确定 2h - 1）。

5、完全二叉树：最下面一层可能部分空的。满二叉树是完全二叉树。

0745 Dijkstra 最短路径算法

狄克斯特拉算法：是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近，且未访问过的顶点的邻接节点，直到扩展到终点为止。

假设我们有一个无向图，边的权重为正值，并且我们将使用一个邻接矩阵来表示图。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


function dijkstra(graph, src) {
    const V = graph.length;
    let dist = new Array(V).fill(Infinity);
    let sptSet = new Array(V).fill(false);
 
    dist[src] = 0;
 
    for (let i = 0; i < V; i++) {
        let u = -1;
        let min = Infinity;
        for (let j = 0; j < V; j++) {
            if (!sptSet[j] && dist[j] <= min) {
                u = j;
                min = dist[j];
            }
        }
 
        if (u === -1) {
            break;
        }
 
        sptSet[u] = true;
 
        for (let v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] !== Infinity && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    return dist;
}
 
// 示例用法
const graph = [
    [0, 4, 0, 0, 0, 0],
    [4, 0, 8, 0, 0, 0],
    [0, 8, 0, 9, 0, 0],
    [0, 0, 9, 0, 7, 0],
    [0, 0, 0, 7, 0, 2],
    [0, 0, 0, 0, 2, 0]
];
 
const src = 0; // 起点
const dist = dijkstra(graph, src);
 
console.log(dist);