1.位运算
- 左移<<
- 右移>> ：可以用在二分算法中取中间值，比如
13>>1
2.按位操作
- 按位与
&：每一位都为1，结果才为1 - 按位或
|：其中一位为1，结果就是1 - 按位异或
^：每一位都不同，结果才为1
3.栈
- 特点：后进先出（LIFO）
- 算法基本思想：因为只能从栈的顶部压入数据也只能从栈的顶部弹出数据，所以可以用一个单链表实现。因为只针对栈顶元素操作，所以借用单链表的头可以让所有的操作在O(1)的时间内完成
- 场景：在解决问题时，只关心上一次的操作，处理完上一次的操作后，能在O(1)时间内查找到更前一次的操作。比如leecode20题（有效的括号）、739题（每日温度）
- 使用栈解决迷宫问题
let maze=[
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
]
function maza_path(){
let stack=[],nextNode
stack.append((x1,y1))
while(stack.length>0){
let curNode=stack[-1] //当前的节点
if(curNode[0]==x2&&curNode[1]==y2){
//走到终点了
for(P in stack){
console.log(p)
}
return true
}
//x,y四个方向 x-1，y; x+1,y; x,y-1; x,y+1
for(dir in dirs){
nextNode=dir(curNode[0],curNode[1])
//如果下一个节点能走
if(maze[nextNode[0][nextNode[1]]]==0){
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]]==2 //2表示为已经走过
break
}
}
maza[nextNode[0][nextNode[1]]==2
stack.pop()
}else{
console.log('没有路')
return false
}
}
复制代码4.队列
- 特点：先进先出（FIFO）,在队尾查看和添加数据，在队头查看和删除数据
- 实现：用双链表
- 场景：按照一定顺序处理数据且数据不断变化时，比如广度优先搜索。
广度优先搜索的思路是：（1）从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口（2）使用队列存储当前正在考虑的节点
（1）队列的实现方式--环形队列
环形队列：当队尾指针
front==Maxsize+1时，再前进一个位置就自动到0
- 队首指针前进1：
front=(front+1)% Maxsize - 队尾指针前进1：
rear=(rear+1)% Maxsize - 队空条件：
rear==front - 队满条件：
(rear+1)% Maxsize==front
Queue(){
function init(self,size=100){
self.queue=[0,size.random()]
self.size=size
self.rear=0 //队尾指针
self.front=0 //队首指针
}
function push(self,element){
self.rear=(self.rear+1)%self.size
self.queue[self.rear]=element
}
function pop(self){
if(!self.isEmpty()){
self.front=(self.front+1) % self.size
return self.queue[self.front]
}else{
console.log('error')
}
}
function isEmpty(self){
return self.rear==self.front
}
function isFilled(self){
return (self.rear+1)%self.size==self.front
}
}
复制代码（2）双端队列：
- 可以利用一个双链表
- 队列的头尾两端能在O(1)的时间内进行数据的查看、添加和删除
- 场景：实现一个长度动态变化的窗口或者连续区间。leecode239题（滑动窗口最大值）
（3）优先队列：
- 与普通队列区别：保证每次取出的元素是队列中优先级最高的、优先级别可自定义
- 最常用的场景：从杂乱无章的数据中按照一定顺序（或者优先级）筛选数据
- 本质：二叉堆的结构，堆在英文里叫Binary Heap，利用一个数组结构来实现完全二叉树
- 特性：数组里的第一个元素
array[0]拥有最高优先级
- 给定一个下标
i，那么对于元素array[i]而言- 父节点对应的元素下标是
(i-1)/2- 左侧子节点对应的元素下标是
2*i+1- 右侧子节点对应的元素下标是
2*i+2- 数组中每个元素的优先级都必须高于它两侧子节点
- 基本操作：向上筛选、向下筛选
- 时间复杂度：
O(logk) - 初始化一个大小为n的堆，时间复杂度为
O(n)。leetcode347题
5.排序
冒泡排序、选择排序、插入排序的时间复杂度都为O(n*n)
- 冒泡排序：从第一个元素开始，和下一个索引元素比较大小。如果当前元素大就交换位置，重复操作直到最后一个元素。那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作，但是此时最后一个元素已经是最大数了，所以不需要再比较最后一个元素，只需要比较到
length-2的位置- 时间复杂度为O(n*n)
//使用双循环来进行排序。外部循环控制所有的回合，内部循 环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换
function sort(array){
let tmp = 0;
for(let i = 0; i < array.length; i++){
for(let j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j+1]){
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
return array
}
let array =[5,8,6,3,9,2,1,7];
sort(array);
复制代码优化：
如果我们能判断出数列已经有序，并且做出标记（使 用一个变量判断），剩下的几轮排序就可以不必执行，提早结 束工作
function sort(array){
let tmp = 0;
for(let i = 0; i < array.length; i++) {
//有序标记，每一轮的初始是true
let isSorted = true;
for(let j = 0; j < array.length - i - 1; j++)
{
if(array[j] > array[j+1]){
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
isSorted = false; //有元素交换，所以不是有序，标记变为 false
}
}
if(isSorted){
break;
}
}
}
let array = [5,8,6,3,9,2,1,7];
sort(array);
复制代码如果数组中后部分是有序的，可以这样优化
* 设置一个无序序列的边界，每次排序到这里就停止
function sort(array){
let tmp = 0;
let lastExchangeIndex = 0; //记录最后一次交换的位置
let sortBorder = array.length - 1; //无序数列的边界，每次比较只需要比到这里为止
for(let i = 0; i < array.length; i++){
let isSorted = true; //有序标记，每一轮的初始是true
for(let j = 0; j < sortBorder; j++){
if(array[j] > array[j+1]){
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
isSorted = false; //有元素交换，所以不是有序，标记变 为false
lastExchangeIndex = j; //把无序数列的边界更新为最后一次交 换元素的位置
}
}
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
}
}
let array = [3,4,2,1,5,6,7,8];
sort(array);
复制代码- 插入排序：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。比如：
[3,38,5,47,36,26]- 时间复杂度为O(n*n)：leetcode 147题
//可以想象要插入的值为从别的地方抽取的牌，与手里的牌做比较
function insert_sort(li){
for (var i in (1, li.length)){
let tmp=li[i]
j=i-1
while(j>=0 && tmp<li[j]){ //当满足这两个条件时，说明还没找到适合抽取的牌插入的位置
li[j+1] =li[j]
j=j-1
}
li[j+1]=tmp //当j<0或者tmp>li[j]时把牌插入j+1的位置
}
return li
}
复制代码- 选择排序：遍历数组，设置最小值的索引为0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引1开始重复上述操作。比如：
[3,38,5,47,36,26]- 时间复杂度为O(n*n)
//因为每次遍历都能得到无序区的最小值，所以交换后的值所在的区域为有序区，剩余的位置在无序区（以i为划分线）
function select_sort(li){
for (var i in li.length-1){
let min_loc= i //最小元素的位置，首先假设它在无序区的第一位
for(var j;j>=i+1 && j<li.length；j++){ //无序区遍历出最小元素,j从i+1开始算可以减少一次i和自身比较的次数
if(li[j]<li[min_loc]){
min_loc=j
}
}
li[i]=li[min_loc] //无序区第一位和最小元素所在的位置交换
li[min_loc]=li[i]
}
return li
}
复制代码归并排序，快速排序，堆排序 —-三种排序算法的时间复杂度都是O(nlogn)
- 一般情况下，就运行时间而言：快速排序<归并排序<堆排序
- 三种排序算法的缺点：
- 快速排序：极端情况下排序效率低
- 归并排序：需要额外的内存开销
- 堆排序：在快的排序算法中相对较慢
- 归并排序：数组先切分成两个元素一组的多个数组，再按顺序合成一个大数组
- 时间复杂度为O(N*logN),空间复杂度O(n)
- 步骤
- 分解：将列表越分越小，至分成一个元素
- 终止条件：一个元素是有序的
- 合并：将两个有序列表归并，列表越来越大
function merge(li,low,mid,high){ let i=low, j=mid+1 ltmp=[] while(i<=mid&&j<=high){ //只要左右两边都有数 if(li[i]<=li[j]){ ltmp.append(li[i]) i+=1 }else{ ltmp.append(li[j]) j+=1 } } //while执行完，肯定有一部分没数了，下边的两个while，只会执行其中一个 while(i<=mid){ ltmp.append(li[i]) i+=1 } while(j<=high){ ltmp.append(li[j]) j+=1 } li[low,high+1]=ltmp } function mergesort(li,low,high){ if(low<high){ mid=(low+high)/2 mergesort(li,low,mid) mergesort(li,mid+1,high) merge(li,low,mid,high) } } 复制代码
- 快排：先取出一个基准值，比基准值大的放右边，比基准值小的放左边，对比完成后将基准值和第一个比基准值大的值交换位置，然后将数组以基准值的位置分为两部分，继续递归以上操作。
快速排序一般时间复杂度为nlogn，最坏时间复杂度为n*n(当每次递归时只能多增加一个有序区的值即每次只能为一个值排序)
function partition(li,left,right){
let tmp=li[left]
while(left < right){
while(left<right && li[right]>=tmp){//从右边找比tmp小的数
right-=1 //往左走一步
}
li[left]=li[right] //把右边的值写到左边空位上
while(left<right && li[right]<=tmp){
left+=1
}
li[right]=li[left] //把左边的值写到右边空位上
}
li[left]=tmp //把tmp归位
return left
}
function quick_sort(li,left,right){
if(left<right){ //列表至少有两个元素
mid=partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
}
}
复制代码- 堆排序：先遍历出最大值放到数组的首位，然后将数组首位和末尾交换位置并将数组长度减一，然后重复以上操作，得到一个大根堆（某个节点的所有子节点的值都比他小）
- 建立堆
- 得到堆顶元素，为最大元素
- 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
- 堆顶元素为第二大元素
- 重复步骤3，直到堆变空
堆的向下调整性质:1.假设根节点的左右子树都是堆，但根节点不满足堆的性质；2.可以通过一次向下调整来将其变成一个堆
时间复杂度nlogn
//创建一个大根堆
function sift(data,low,high){
let i=low, //i最开始指向根节点
j=2*i+1, //j最开始是根节点的左孩子
tmp=data[i] //把堆顶存起来
while(j<=high){ //只要j位置有数
if(j<high&&data[j]<data[j+1]){ //如果有右孩子并且比较大
j+=1 //j指向右孩子
}
if(temp<data[j]){
data[i]=data[j]
i=j //往下看一层
j=2*i+1
}else{ //tmp更大，把tmp放到i的位置上
break
}
}
data[i]=tmp //把tmp放到叶子节点上
}
function heap_sort(data){
let n=data.length
for(let i in range(n/2-1,-1,-1)){
sift(data,i,n-1) //i表示建堆的时候调整的部分的根的下标
}
// 以上部分建堆完成
for(let j in range(n-1,-1,-1)){
//i指向当前堆的最后一个元素
data[0]=data[i]
data[i]=data[0]
sift(data,0,i-1) //i-1是新的high
}
}
复制代码延伸：topK问题：现在有n个数，设计算法得到前k大的数(k<n)（比如微博热搜）
- 解决思路
- 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整
- 遍历列表所有元素后，倒序弹出堆顶
- 解决方法
- 排序后切片
O(nlogn) - 冒泡排序、选择排序、插入排序
O(kn) - 堆排序思路
O(nlogk)
- 排序后切片
//创建一个小根堆
function sift(data,low,high){
let i=low, //i最开始指向根节点
j=2*i+1, //j最开始是根节点的左孩子
tmp=data[i] //把堆顶存起来
while(j<=high){ //只要j位置有数
if(j<high&&data[j]>data[j+1]){
j+=1 //j指向右孩子
}
if(temp>data[j]){
data[i]=data[j]
i=j //往下看一层
j=2*i+1
}else{
break
}
}
data[i]=tmp //把tmp放到叶子节点上
}
function topk(li,k){
let heap=li[0,k]
for(let i in range((k-2/2),-1,-1)){
sift(heap,i,k-1)
}
//1.建堆
for(let i in range(k,li.length-1)){
if(li[i]>heap[0]){
heap[0]=li[i]
sift(heap,0,k-1)
}
}
//2.遍历
for(let i in range(k-1,-1,-1)){
heap[0],heap[i]=heap[i],heap[0]
sift(heap,0,i-1)
}
//3.出数
return heap
}
复制代码6.链表
- 链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域
item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表
class Node(object){
function init(self,item){
self.item=item
self.next=None
}
}
function create_linklist(li){
let head=Node(li[0])
for(element in li){
node=Node(element)
node.next=head
head=node
}
return head
}
function create_linklist_tail(li){
let head=Node(li[0]),
tail=head
for(element in li){
node=Node(element)
tail.next=node
tail=node
}
return head
}
lk=create_linklist_tail([1,2,3,5,6])
复制代码- 创建链表：头插法，尾插法
- 链表节点的插入、删除
- 插入：
p.next=curNode.next curNode.next=p 复制代码
- 删除
p=curNode.next
curNode.next=curNode.next.next
del p
复制代码
- 双链表：双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点
- 双链表节点的插入
p.next=curNode.next curNode.next.prior=p p.prior=curNode curNode.next=p 复制代码
- 双链表节点的删除
p=curNode.next
curNode.next=p.next
p.next.prior=curNode
del p
复制代码
-
链表与顺序表
- 链表在插入和删除的操作上明显快于顺序表
- 链表的内存可以更灵活的分配（试利用链表重新分配栈和队列）
- 链表这种链式存储的数据结构对树和图的结构有很大的启发性
-
数组和链表有什么区别，链表有什么特点？
- 数组静态分配内存，链表动态分配内存；
- 数组在内存中连续，链表不连续；
- 数组元素在栈区，链表元素在堆区；
- 数组可以根据下标进行快速定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)（因为链表访问元素需要移动指针）；
- 数组插入或删除元素的时间复杂度O(n)（因为需要移动大量的元素），链表的时间复杂度O(1)（因为只需要修改指针即可）。
参考链接：javascript实现链表数据结构和反转单链表方法
function myReverse (linkedList) {
// 1 拿到传参链表的head
var head = linkedList.head
// 2 边界判断 如果头结点是空 或者只有一个结点 那还反转个啥
if(head === null || head.next === null) return linkedList
// 3 用三个指针
var current = head
var pre = null
var next = null
#判断当前节点是否为空
#不为空就先获取当前节点的下一节点
#然后把当前节点的next设为上一个节点
#然后把current设为下一个节点，pre设为当前节点
while(current != null) {
next = current.next
current.next = pre
pre = current
current = next
}
linkedList.head = pre
}
复制代码引申：获取链表倒数第k个节点、链表中间节点及判断链表是否有环
blog.csdn.net/qq_40608516…
7.树
- 树是一种数据结构，比如：目录结构
- 树是一种可以递归定义的数据结构
- 树是由n个节点组成的集合：如果n=0，那这是一颗空树；如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树
- 树的度：树中某个节点最多叉的个数为树的度
- 树的共性：结构直观、通过树问题来考察递归算法掌握的熟练程度
- 面试中常考的树的形状有：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树、多叉树
特殊的树：红黑树、自平衡二叉搜索树
（1）二叉树
首先了解下什么是二叉树
- 二叉树
- 二叉树：度不超过2的树
- 每个节点最多有两个孩子节点
- 两个孩子节点被区分为左孩子节点和右孩子节点
- 满二叉树：一个二叉树，如果每一个层的节点树都达到最大值，则这个二叉树就是满二叉树
- 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树
- 大根堆：一棵完全二叉树，满足任一节点都比其他孩子节点大
- 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
二叉树的存储方式（表示方式）
- 链式存储方式：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接
- 顺序存储方式（用列表）
二叉树的先序，中序，后序遍历
- 先序遍历表示先访问根节点，然后访问左节点，最后访问右节点：应用场景（在树里搜索或创建一颗新树）
- 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点：应用场景（二叉搜索树：根节点大于左边小于右边，一般不出现重复的值），leetcode第230题
- 后序遍历表示先访问左节点，然后访问右节点，最后访问根节点：比如leetcode250题
具体介绍参考：二叉树遍历(先序、中序、后序)
中序遍历的前驱后继节点：
前驱节点：就是中序遍历排序中相对的前一个
后继节点：就是中序遍历排序中相对的后一个
树的深度
（2）前缀树（也称字典树）：这种数据结构被广泛地运用在字典查找当中
什么是字典查找？例如/；给定一系列构成字典的字符串，要求在字典当中找出所有以“ABC”开头的字符串
-
- 方法一：暴力搜索法
时间复杂度：O(M*N )开头长度为M
- 方法二：前缀树
时间复杂度：O(M)
- 应用场景：
- 搜索框输入搜索文字，回罗列以搜索词开头的相关搜索
- 汉语拼音输入法
- 重要性质：
- 每个节点至少包含两个基本属性
- children：数组或者集合，罗列出每个分支当中包含的所有字符
- isEnd：布尔值，表示该节点是否为某字符串的结尾
- 根节点是空的
- 除了根节点，其他所有节点都可能是单词的结尾，叶子节点一定都是单词的结尾
4.最基本的操作
- 创建 ，方法为
- 遍历一遍输入的字符串，对每个字符串的字符进行遍历
- 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中
- 如果字符集已经包含了这个字符，跳过
- 如果当前字符是字符串的最后一个，把当前节点的isEnd标记为真
- 搜索，方法为
- 从前缀树的根节点出发，逐个匹配输入的前缀字符
- 如果遇到了，继续往下一层搜索
- 如果没遇到，立即返回
leetcode212题（可以使用深度优先算法）
（3）线段树
假设求数组任意一段区间里元素的总和（或者平均值）
- 方法一：遍历一遍数组：时间复杂度为O(n)
- 方法二：线段树：时间复杂度为O(logn)—依赖于树的高度
线段树是什么？一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和
例如
（4）树状数组
8.递归和回溯
- 递归：自顶向下 leetcode 247题（中心对称树）
- 回溯： leetcode 39题（组合总和）
可以用在下列算法中：
- 二叉树的定义和遍历
- 归并排序、快速排序
- 动态规划
- 二分搜索
引申1:递归有什么优缺点
优点：
代码简洁。
易于理解
缺点：
- 时间和空间的消耗比较大：
递归由于是函数调用自身，而函数调用是消耗时间和空间的。每一次函数调用，都需要在内存栈中分配空间以保存参数，返回值和临时变量。而往栈中压入和弹出数据也都需要时间，所以降低了效率。
- 重复计算：
递归中又很多计算都是重复的，递归的本质时把一个问题分解成两个或多个问题，多个问题存在重叠的部分，即存在重复计算。如斐波那契数列的递归实现。
- 栈溢出：
递归可能存在栈溢出，每次调用时都会在内存栈中分配空间。而栈空间的容量是有限的，当调用的次数太多，就可能会超出栈的容量，造成调用栈溢出
引申2:从有序数组中找出某个数出现的次数：
- 可以使用二分查找
- 直接比较
int findCount(int a[],int len ,int key)
{
int i,count = 0;
for(i=0;i<len;i++)
{
if(key==a[i])
count++;
}
return count;
}
复制代码9.动态规划
动态规划当中包含三个重要的概念：
- 最优子结构
- 边界
- 状态转移公式
动态规划的本质其实就是两点：
1.自底向上分解子问题
2.通过变量存储已经计算过的解
- 斐波那契数列的动态规划思路：
- 斐波那契数列从0和1开始，那么这就是这个子问题的最底层
- 通过数组来存储每一位所对应的斐波那契数列的值
- 0-1背包问题：参考算法题之动态规划-01背包问题
10.哈希表
哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
- insert(key,value)：插入键值对（key,value）
- get(key)：如果存在键为key的键值对则返回其value，否则返回空值
- delete(key)：删除键为key的键值对
- 数组里面有10万个数据，取第一个元素和第10万个元素的时间相差多少
JavaScript没有真正意义上的数组，所有的数组其实是对象，其“索引”看起来是数字，其实会被转换成字符串，作为属性名（对象的key）来使用。所以无论是取第 1 个还是取第10万个元素，都是用key精确查找哈希表的过程，其消耗时间大致相同。 - 给定两个数组，写一个方法来计算它们的交集
空间换时间的思路是用个Hash表来存数组1的元素以及出现的个数（此处需要遍历n次，并存一个n级别的空间）。
遍历数组2，发现数组2里有Hash表里的值就存到Result数组里，并把Hash表内该值次数减一（为0之后就Delete）。如果不存在Hash表里，就跳过。这样时间复杂度就是(m+n)
另一个方法有两个数组m,n。遍历n的时候，判断值在不在m里，如果在，把m里的该值push到Result数组里，并将该值从m数组里删掉（用splice）。这样就是不用额外空间，但是提高了时间复杂度。
const intersect = (nums1, nums2) => {
const map = {}
const res = []
for (let n of nums1) {
if (map[n]) {
map[n]++
} else {
map[n] = 1
}
}
for (let n of nums2) {
if (map[n] > 0) {
res.push(n)
map[n]--
}
}
return res
}
复制代码- 连续数值简化
请写一个函数，完成以下功能:
输入 '1, 2, 3, 5, 7, 8, 10' 输出 '1~3, 5, 7~8, 10'
输入描述
输入'1, 2, 3, 5, 7, 8, 10'
输出描述
输出'1~3, 5, 7~8, 10'
示例1
输入
1,2,3,5,7,8,10
输出
1~3,5,7~8,10
复制代码答案：
function transformStr(str) {
let arr = str.split(',')
let i = 0
let ret = []
for (let j = 1; j <= arr.length; j++) {
if (arr[j] - arr[j - 1] !== 1) {
ret.push(j - i === 1 ? arr[i] : `${arr[i]}~${arr[j - 1]}`)
i = j
}
}
return ret.join(',')
}
或者
function simplifyStr(num) {
var result = [];
var temp = num[0]
num.forEach((value, index) => {
if (value + 1 !== num[index + 1]) {
if (temp !== value) {
result.push(`${temp}~${value}`)
} else {
result.push(`${value}`)
}
temp = num[index + 1]
}
})
return result;
}
复制代码- 数据转换
function commonSearch(target, id, mode) {
const staskOrQuene = [...target]
do {
const current = staskOrQuene[mode === 'dfs' ? 'pop' : 'shift']()
if (current.children) {
staskOrQuene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(staskOrQuene.length)
return undefined
}
var aa = [
{
id: 1,
name: '广东省',
children: [
{
id: '11',
name: '深圳市',
children: [
{
id: '111',
name: '南山区'
},
{
id: '112',
name: '福田区'
}
]
}
]
}
]
commonSearch(aa,112)
复制代码11.图
最基本知识点：
- 阶、度（出度、入度）
- 树、森林、环
- 有向图、无向图、完全有向图、完全无向图
- 连通图、连通分量
- 图的存储和表达方式：邻接矩阵、邻接链表
围绕图的算法：
- 图的遍历：深度优先、广度优先
- 环的检测：有向图、无向图
- 拓扑排序
- 最短路径算法
- 连通性相关算法
- 图的着色、旅行商问题等
必须掌握的知识点：
- 图的存储和表达方式：邻接矩阵、邻接链表
- 图的遍历：深度优先、广度优先
- 二部图的检测、树的检测、环的检测：有向图、无向图
- 拓扑排序
- 联合查找算法
- 最短路径
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
