算法笔记¶
统计信息：字数 28787 阅读58分钟
原始笔记链接：https://cloud.seatable.cn/dtable/external-links/59b453a8639945478de2/
0005 DFS和BFS的区别¶
以二叉树为例，bfs和dfs的具体区别是什么？他们的性能有什么差距
DFS 使用函数递归调用实现
runNode = (node) => {
if (!node) return;
fn(node.val);
this.runNode(node.left);
this.runNode(node.right);
}
BFS 使用队列实现
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);
}
}
性能上都一样，一个按照深度节点遍历，一个优先按照层遍历。时间复杂度和空间复杂度差不多。
0006 DFS和BFS分别实现深拷贝一个对象¶
不考虑环形引用，那么就循环对象的键值对，然后分别拷贝即可
0017 两个数组的交集怎么计算¶
循环第一个数组，记录在字典中；循环第二个数组，然后把重复出现的拿出来返回
0036 使用递归迭代两种办法，实现数组flat函数¶
递归就是在一个函数内部调用这个函数
fn(node) {
return fn(node.val)
}
迭代就是一个变量，等于某个函数执行这个变量后的结果
arr = fn(arr)
const fn = (arr) => {
if (!arr.some(item => Array.isArray(item))) return arr;
return [].concat(...arr);
}
0054 冒泡排序的时间复杂度是多少¶
冒泡排序的时间复杂度是n^2，循环两次实现
改进方法：并归排序或者快速排序，时间复杂都是 nlogn
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 字符串内置的方法实现
return str1.indexOf(str2)
思路2：循环字符串，然后依次比较子字符串是否相等
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 然后判断每一个是否是回文数
数字-字符串-数组转换比较耗时，如果追求时间快速，那么直接循环字符串比较更快
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
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;
}
改进版
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、最后返回整个树节点
0093 找出一个有序数组的中位数¶
二分法查找中位数
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
举例：集合 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 中是否存在另一个元素，这样算法复杂度较差。最好使用对象索引判断一下，减少复杂度。
应用：大部分排列组合问题、硬币找零问题（不能使用贪心算法）
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次结果的值。
f(n) = F(a * f(n - 1) + b * f(n - 2) +);
动态规划的实质是，把一个实际问题，转换成数学的递推公式（通项公式），然后使用排列组合或者递推的方式计算结果。
应用：斐波那契函数、打家劫舍问题，背包问题，复杂排列组合问题
难点：把一个实际问题，转换成数学的递推公式
例子：排列组合数据量较大时，回溯方法内存溢出，使用DP解决
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. 一个数组最大的自序和，那么等于每一个项结尾的自序和的最大值
maxList = [max1, max2, max3,,, maxn];
Math.max(...maxList)
2. 每一个项为结尾的最大自序和，可能是当前的 nums[i] 或者是 f(n - 1) + nums[i]
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 是某一块的唯一标识。四个边是某个属性值，全部拼图只有另一个和某一个完全一样
let arr = [
{
id: '',
left: '',
right: '',
top: '',
bottom: '',
}
];
关键是从某一个节点开始，然后获取相邻的节点（单项指针，或者对象的唯一键值对）。
把全部的节点遍历一次，存放在对象中。对象的键是属性，值是 ID。
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 获取邻接节点
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、把简答的解法复杂化（考虑数量级，考虑内存，考虑多维数据，考虑特殊值极端值影响）
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，这样可以指向不同的数组，进行处理
快慢指针¶
// 需要预处理next下一个节点是否存在等
let a = head.next;
let b = head.next.next;
while (a.next) {
a = a.next;
b = b.next.next;
}
对撞指针¶
在一个排序数组中，找到两个数字，使得其中的和等于 target
// 输入: 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 有序数组转换成等高的二叉搜索树¶
等高的二叉搜索树，那么根节点必然是数组的中位数。数组已经排序，那么使用递归的思路直接将排序的有序数组转换成二叉搜索树，基本思路如下：
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实现希尔排序的一个简单例子：
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
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 是一种在图形平面上，有多个节点的路径，求出最低通过成本的演算法。
使用场景：电子地图的导航功能。只需要输入起点和终点，电子地图就会快速的为我们规划出一条最短路线。
基础算法是网格寻路算法：
A* 算法的基本思想是：通过启发式公式，对当前搜索状态的下界进行估计，并且优先搜索更有潜力的解（根据估计的下界来确定）。
如果是传统的 BFS 算法，那么在队列中还没有遍历的节点权重都是一样的（也就是遍历全部的节点，广度优先）。在放入节点时，如果先计算一下当前节点的下界（下界，就是当前已经行走的步数+当前节点到终点的距离，不考虑障碍物），然后给出下界，那么由于障碍物，实际的距离要大于等于这个下界。
那么我们对需要遍历的节点，都计算出当前的下界，然后放在优先队列中，优先处理下界最小（即性能潜力最高的节点），就实现了 A star 算法的基本思路。
# 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 官方公众号文章链接
0335 网格寻路算法¶
问题：从无数条线路中找到最短路径（中等）
给你一个网格，其中每个单元格不是空就是障碍物。每一步，您都可以在空白单元格中上、下、左、右移动。请找出从左上角到右下角最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 null。
解决：BFS
我们可以使用队列，来实现广度优先搜索算法：首先将起点插入队列，然后循环的从队列首部取出一个点作为当前访问点，并将当前访问点的各个邻居点依次插入到队列的尾部，直到遇到终点或是队列为空。此外，我们还需要记录已经被访问过的点，以免算法陷入死循环。
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 算法
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 距离
const D = Math.abs(x1 - x2) + Math.abs(y1 - y2);
主要用于网格算法（国际象棋，网格寻址，最短路径等）
0710 数据结构的概念补充¶
下面的概念不难，平时可能用的不多，考试会考。
1、稀疏矩阵的压缩：一个二维矩阵大部分是0，少量有内容，就是稀疏矩阵。可以通过三元组表的顺序结构存储（i, j, value）进行压缩，三元组表的链式存储就是十字链表。稀疏矩阵的压缩算法，常用栅格图的压缩（相同的色值）可以使用同一个位置进行标记，避免使用原始图片。
2、节点的度：结点拥有的子树个数，称为结点的度。
3、树的度：树内各结点的度的最大值,也就是树内结点拥有子树的最大值。
4、满二叉树：二叉树节点都是满的（高度是H，节点确定 2h - 1）。
5、完全二叉树：最下面一层可能部分空的。满二叉树是完全二叉树。