前端必会算法

algorithm
发布日期:   2020-07-23

前端算法

面试一旦公司算法少，则网络，linux 会增加，统计概率会增加
多练！！！

数据结构与算法

数据结构与算法有什么关系？

可以容纳数据的结构称为数据结构

算法是用来对数据结构进行处理的方法 ；数据结构是静态的，算法是动态的

线性数据结构之数组

一维数据结构：（线性数据结构）

线性的数据结构强调存储与顺序

数组：底层上数组定长

数组特性：

  1. 存储在物理空间上是连续的
  2. 底层的数组长度是不可变的 (JS 引擎做出优化导致学的是可变的)
  3. 数组的变量指向的是数组第一个元素的位置
var a={1,2,3,4,5,6,7,8}
a[1], a[2], a[3]   //方括号表示的是存储地址的偏移。
  1. 操作系统小知识：通过偏移查询数据性能最好
    优点：查询性能最好。指定查询某个位置。
    缺点：
    1. 因为空间必须连续，所以如果数组比较大，当系统的空间碎片较多的时候，容易存不下
    2. 因为数组的长度是固定的，所以数组的内容难以添加和删除

深究操作系统课程

var a = [1, 2, 3, 4, 5];
var arr = new Array(10); //初始化数组长度

线性数据结构之链表

计算机四门专业课自学

演示 demo

var b = {
  value: 2,
  next: null,
};
// 实验得知：b要定义在a声明的前面
var a = {
  value: 1,
  next: b, //不是嵌套关系，而是引用关系
};
console.log(a.next == b); //两个对象比较，比较的是地址

链表的特点：

  1. 空间上不是连续的。
  2. 每存放一个值，都要多开销一个引用空间。

优点：

单链表。我想传递一个链表，我必须传递链表的根节点。
**每一个节点都认为自己是根节点(因为每个节点都记录自己和 next)**。

  1. 只要内存足够大，就能存的下，不用担心空间碎片的问题
  2. 链表的添加和删除非常容易

缺点：

  1. 查询速度慢。(查询某个位置)
  2. 链表每一个节点都需要创建一个指向 next 的引用，浪费一些空间。
  3. 当节点内数据越多的时候(即 value 越多)，这部分多开销(即 next)的内存影响较少。

创建链表

function Node(value) {
  this.value = value;
  this.next = null;
}
var a = new Node(1);
var b = new Node(2);
var c = new Node(3);
var d = new Node(4);
a.next = b;
b.next = c;
c.next = d;
d.next = null;
console.log(a.value);
console.log(a.next.value);
console.log(a.next.next.value);
console.log(a.next.next.next.value);

线性数据结构之遍历

遍历：将集合中的每一个元素进行获取并查看

数组遍历

var arr = [1, 2, 3, 4, 5, 6, 7, 8];
function bianArr(arr) {
  if (arr == null) {
    // undefined==null也会跳出，容错性较好
    return;
  } //算法只要报错就没分	严谨性判断
  for (var i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}
bianArr(arr);

链表遍历

function Node(value) {
  this.value = value;
  this.next = null;
}
var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

function bianLink(root) {
  var temp = root; // 寄存
  while (true) {
    //不知道循环次数，用while(true)
    if (temp != null) {
      console.log(temp.value);
    } else {
      break;
    }
    temp = temp.next;
  }
}
bianLink(node1);

线性数据结构的递归遍历

数组的递归遍历 不推荐

var arr = [1,2,3,4,5,6,7,8];
function bianArr(arr, i){
    if(arr == null || arr.length <= i) return;
    //考虑数组长度和是否为空
    console.log(arr[i]);
    // bianArr(arr,i++);为什么不行
    bianArr(arr,i+1);

}
bianArr(arr, 0);

链表的递归遍历 推荐

function Node(value){
    this.value = value;
    this.next = null;
}
var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
//递归遍历，必须有出口
function bianLink(root){//
    if(root == null) {
        return ;
    }
    console.log(root.value);
    bianLink(root.next);
}
bianLink(node1);

链表的逆置

function Node(value) {
  this.value = value;
  this.next = null;
}
var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

/*
找到最后一个节点
function nizhi(root){
if(root.next != null){
return nizhi(root.next);
}else{
return root;
}
console.log(nizhi(node1))//找到了最后一个节点
}

// 以上行为有缺陷：每个节点都认为自己是根节点，不能实现最后一个节点指向上一个节点
*/
// 思想：递归先找出口
function nizhi(root) {
  if (root.next.next == null) {
    //代表当前节点是倒数第二个节点
    root.next.next = root; //让最后一个节点指向自己(倒数第二个节点)
    return root.next; //return 最后一个节点是root.next
  } else {
    // 当前节点不是倒数第二个节点
    var result = nizhi(root.next); // 不是的话就递归
    root.next.next = root; //老规矩：下一个的指向指向自己
    root.next = null; //第一个必须有指向，指向空
    return result;
  }
}
// console.log(nizhi(node1))

//输出逆置后的顺序
var newRoot = nizhi(node1);
function bianLink(root) {
  if (root == null) return;
  console.log(root.value);
  bianLink(root.next);
}
bianLink(newRoot);

冒泡排序

背景：乱序数组排序

var arr = [4, 1, 6, 9, 3, 2, 7, 8];
function getMin(arr) {
  if (arr == null || arr.length == 0) return;
  var index = -1;
  for (var i = 0; i < arr.length; i++) {
    if (
      (arr[i] != null && arr[i] < arr[index]) ||
      (arr[i] != null && index == -1)
    ) {
      index = i;
    }
  }
  var result = arr[index];
  arr[index] = null;
  return result;
}
function sort(arr) {
  var newArr = new Array(arr.length);
  for (var i = 0; i < newArr.length; i++) {
    newArr[i] = getMin(arr);
  }
  return newArr;
}
console.log(sort(arr));

冒泡排序:每一次循环都把最大的排在最后面

var arr = [4, 1, 6, 9, 3, 2, 7, 8];
// 排序不是比较大小，本质是比较和交换
function compare(a, b) {
  //比较之后需要得出是否需要交换
  if (b < a) return true;
  else return false;
}
function exchange(arr, a, b) {
  //将数组ab位置里面的值交换
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}
function sort(arr) {
  for (var i = 0; i < arr.length; i++) {
    //要进行n次筛选
    for (var j = 0; j < arr.length - 1 - i; j++) {
      //少i圈   里面的for是进行一次筛选选出最大的
      if (compare(arr[j], arr[j + 1])) {
        exchange(arr, j, j + 1);
      }
    }
  }
}
sort(arr);
console.log(arr);

选择排序

var arr = [4, 1, 6, 9, 3, 2, 7, 8];

function compare(a, b) {
  if (a < b) return true;
  else return false;
}
function exchange(arr, a, b) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}
function sort(arr) {
  for (var i = 0; i < arr.length; i++) {
    // 循环全部圈数
    var maxIndex = 0; //最大的数的序号
    for (var j = 0; j < arr.length - i; j++) {
      //一圈下来谁是最大的
      if (compare(arr[maxIndex], arr[j])) {
        maxIndex = j; //j是最大的
      }
    }
    exchange(arr, maxIndex, arr.length - 1 - i);
  }
}
sort(arr);
console.log(arr);
// 任何一种排序算法，都没有优劣之分，只有是否适合的场景 越乱，越适合选择排序；越有序，越适合冒泡排序

简单快速排序

var arr = [4, 1, 6, 9, 3, 2, 8, 7];
function quickSort(arr) {
  if (arr == null || arr.length == 0) return []; //如果不是空数组，则没有对应的push方法，导致报错
  //选班长，小的站在左边，大的站在右边
  var leader = arr[0];
  var left = [];
  var right = [];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] < leader) left.push(arr[i]);
    else right.push(arr[i]);
  }
  left = quickSort(left);
  right = quickSort(right);
  left.push(leader);
  return left.concat(right);
}
console.log(quickSort(arr));

标准快速排序

默认左闭右开

var arr = [4, 1, 6, 9, 3, 2, 8, 7];

function swap(arr, a, b) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

function quickSort2(arr, begin, end) {
  if (begin >= end - 1) return;
  var left = begin;
  var right = end;
  do {
    do left++;
    while (left < right && arr[left] < arr[begin]);
    do right--;
    while (right > left && arr[right] > arr[begin]);
    if (left < right) swap(arr, left, right);
  } while (left < right);
  var swapPoint = left == right ? right - 1 : right;
  swap(arr, begin, swapPoint);
  quickSort2(arr, begin, swapPoint);
  quickSort2(arr, swapPoint + 1, end);
}

function quickSort(arr) {
  quickSort2(arr, 0, arr.length); //取到0 娶不到arr.length
}

quickSort(arr);
console.log(arr);

栈和队列

栈结构：先入后出，类比成一个箱子

队列结构：先入先出，类比成一个管道

栈

function Stack() {
  this.arr = [];
  this.push = function (value) {
    this.arr.push(value);
  };
  this.pop = function () {
    return this.arr.pop();
  };
}
var stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.arr);
stack.pop();
console.log(stack.arr);

队列

function Queue() {
  this.arr = [];
  this.push = function (value) {
    this.arr.push(value);
  };
  this.pop = function () {
    return this.arr.shift();
  };
}
var queue = new Queue();
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.arr);
queue.pop();
console.log(queue.arr);

双向链表

function Node(value) {
  this.value;
  this.next = null;
  this.pre = null;
}

var node1 = new Node(1);
var node2 = new Node(2);
var node3 = new Node(3);
var node4 = new Node(4);
var node5 = new Node(5);

node1.next = node2;
node2.pre = node1;
node2.next = node3;
node3.pre = node2;
node3.next = node4;
node4.pre = node3;
node4.next = node5;
node5.pre = node4;

// 双向链表的优点，无论给出哪一个节点，都能对整个链表进行遍历。
// 双向链表的缺点，多耗费一个引用的空间，而且构建双向链表比较复杂。

二维数据结构

二维数组

二维拓扑结构（图）—离散数学图论

var arr = new Array(4);
for (var i = 0; i < arr.length; i++) {
  arr[i] = new Array(8);
}
function Node(value) {
  this.value = value;
  this.neighbor = [];
}
var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
a.neighbor.push(b);
a.neighbor.push(c);
a.neighbor.push(f);
b.neighbor.push(a);
b.neighbor.push(d);
b.neighbor.push(e);
c.neighbor.push(a);
d.neighbor.push(b);
e.neighbor.push(b);

树形结构

特殊的二维拓扑结构——树形结构

树形结构——有向无环图

树是图的一种

树形结构有一个根节点，树形结构没有回路

叶子节点：下面没有其他节点

节点：既不是根节点，又不是叶子节点的普通节点

树的度：这棵树有最多叉的节点有多少个叉，就有多少度

树的深度：树最深有几层，树的深度就为几

满二叉树

树的度最多为 2 的树形结构

特性

  1. 二叉树的根节点 A
  2. 子节点：某个节点下面的节点
  3. 父节点：上级节点
  4. 叶子节点：CDE
  5. 节点：B

满二叉树：

  1. 所有的叶子节点都在最底层
  2. 每个非叶子节点都有两个子节点

完全二叉树

国内：

  1. 叶子节点都在最后一层或倒数第二层
  2. 叶子节点都向左聚拢

国际:

  1. 叶子节点都在最后一层或倒数第二层
  2. 如果有叶子节点，必然有两个叶子节点

子树的概念

子树：（树枝）二叉树中，每一个节点或叶子节点，都是一棵树的根节点

链表每一个节点都认为自己是根节点

二叉树中每一个节点都认为自己是根节点

左子树、右子树：相对谁而言。

遍历

传递二叉树要传根节点

前序遍历：（先根次序遍历）——根左（左边的子树）右

中序遍历：（中根次序遍历）——左根右

后序遍历：（后根次序遍历）——左右根

前序遍历

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");

a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;
function f1(root) {
  //传入根节点
  if (root == null) return;
  console.log(root.value);
  f1(root.left);
  f1(root.right);
}
f1(a);

二叉树的中序遍历

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");

a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;
function f1(root) {
  //传入根节点
  if (root == null) return;
  f1(root.left);
  console.log(root.value);
  f1(root.right);
}
f1(a);
  1. 给出二叉树，写出前中后序遍历
  2. 写出代码
  3. 给出前中序还原二叉树，写出后序遍历
  4. 给出后中序还原二叉树，写出前序遍历
  5. 代码实现

必须有中序才能还原二叉树

前中序还原二叉树

前序：ACFGBDE  ——  A  CFGBDE（A 是根节点）— A CFG BDE（C B 是根节点）

中序：FCGADBE ——- FCG(左子树 3)  A  DBE(右子树 3)

后序：FGCDEBA

后中序还原二叉树

中序：FCGADBE —— FCG(左子树 3)  A  DBE(右子树 3)

后序：FGCDEBA ——- FGCDEB A（A 是根节点）

前序：ACFGBDE

代码前中序还原二叉树

var qian = ["a", "c", "f", "g", "b", "d", "e"];
var zhong = ["f", "c", "g", "a", "d", "b", "e"];
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
function f1(qian, zhong) {
  if (
    qian == null ||
    zhong == null ||
    qian.length == 0 ||
    zhong.length == 0 ||
    qian.length != zhong.length
  )
    return null;
  var root = new Node(qian[0]);
  var index = zhong.indexOf(root.value); //找到根节点在中序遍历中的位置
  // indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。\
  //slice左闭右开
  var qianLeft = qian.slice(1, 1 + index); //前序遍历的左子树
  var qianRight = qian.slice(1 + index, qian.length); //前序遍历的右子树
  var zhongLeft = qian.slice(0, index); //中序遍历的左子树
  var zhongRight = qian.slice(index + 1, zhong.length); //中序遍历的右子树
  root.left = f1(qianLeft, zhongLeft);
  root.right = f1(qianRight, zhongRight);
  return root;
}
var root = f1(qian, zhong);
console.log(root.left);
console.log(root.right);

代码后中序还原二叉树

var zhong = ["f", "c", "g", "a", "d", "b", "e"];
var hou = ["f", "g", "c", "d", "e", "b", "a"];
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
function f1(zhong, hou) {
  if (
    hou == null ||
    zhong == null ||
    hou.length == 0 ||
    zhong.length == 0 ||
    hou.length != zhong.length
  )
    return null;
  var root = new Node(hou[hou.length - 1]);
  var index = zhong.indexOf(root.value);
  var leftZhong = zhong.slice(0, index);
  var rightZhong = zhong.slice(index + 1, zhong.length);
  var leftHou = hou.slice(0, index);
  var rightHou = hou.slice(index, hou.length - 1);
  root.left = f1(leftZhong, leftHou);
  root.right = f1(rightZhong, rightHou);
  return root;
}
var root = f1(zhong, hou);
console.log(root.left);
console.log(root.right);

二叉树的深搜和广搜

二叉树的搜索：树的搜索、图的搜索、爬虫的逻辑、搜索引擎的爬虫算法

深度优先搜索：更适合探索未知

广度优先搜索：更适合探索局域

代码实现二叉树的深度优先搜索

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");
a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;
//对于二叉树来说，深度优先搜素和前序遍历的顺序一样
function deepSearch(root, target) {
  if (root == null) return false;
  if (root.value == target) return true;
  var left = deepSearch(root.left, target);
  var right = deepSearch(root.right, target);
  return left || right;
}
console.log(deepSearch(a, "f"));

代码实现二叉树的广度优先搜索

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");
a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;
function f1(rootList, target) {
  if (rootList == null || rootList.length == 0) return false;
  var childList = [];
  //当前层所有节点的子节点都在这个list中，这样传入下一层级的时候，就可以遍历整个层级的节点
  for (i = 0; i < rootList.length; i++) {
    console.log(rootList[i].value);
    if (rootList[i] != null && rootList[i].value == target) {
      return true;
    } else {
      childList.push(rootList[i].left);
      childList.push(rootList[i].right);
    }
  }
  return f1(childList, target);
}
console.log(f1([a], "f"));

二叉树的比较

二叉树左右子树互换后不是一颗二叉树

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a1 = new Node("a");
var b1 = new Node("b");
var c1 = new Node("c");
var d1 = new Node("d");
var e1 = new Node("e");
var f1 = new Node("f");
var g1 = new Node("g");
a1.left = c1;
a1.right = b1;
c1.left = f1;
c1.right = g1;
b1.left = d1;
b1.right = e1;
var a2 = new Node("a");
var b2 = new Node("b");
var c2 = new Node("c");
var d2 = new Node("d");
var e2 = new Node("e");
var f2 = new Node("f");
var g2 = new Node("g");
a2.left = c2;
a2.right = b2;
c2.left = f2;
// c2.right = g2;
b2.left = d2;
b2.right = e2;
function compareTree(root1, root2) {
  //都是空算相等吗？算
  if (root1 == root2) return true; //是同一颗树
  if ((root1 == null && root2 != null) || (root2 == null && root1 != nul))
    return false;
  if (root1.value != root2.value) return false; //相同位置的值不相等
  var leftBool = compareTree(root1.left, root2.left); //左子树是否相等
  var rightBool = compareTree(root1.right, root2.right); //右子树是否相等
  return leftBool && rightBool; //左右都相等才相等
  //以上三句简化：
  //return compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right)
}
console.log(compareTree(a1, a2));
//遇到二叉树比较问题，必须确定，左右两颗子树交换位置，即左右互换算不算同一颗
//以上：不算
//笔试没有特殊说明默认互换不是同一颗树；面试问一下

二叉树左右子树互换后的比较

二叉树左右子树互换后是一颗二叉树

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a1 = new Node("a");
var b1 = new Node("b");
var c1 = new Node("c");
var d1 = new Node("d");
var e1 = new Node("e");
var f1 = new Node("f");
var g1 = new Node("g");
a1.left = c1;
a1.right = b1;
c1.left = f1;
c1.right = g1;
b1.left = d1;
b1.right = e1;
var a2 = new Node("a");
var b2 = new Node("b");
var c2 = new Node("c");
var d2 = new Node("d");
var e2 = new Node("e");
var f2 = new Node("f");
var g2 = new Node("g");
// a2.left = c2;
// a2.right = b2;
a2.right = c2;
a2.left = b2;
c2.left = f2;
c2.right = g2;
b2.left = d2;
b2.right = e2;
function compareTree(root1, root2) {
  if (root1 == root2) return true;
  if ((root1 == null && root2 != null) || (root2 == null && root1 != nul))
    return false;
  if (root1.value != root2.value) return false;
  return (
    (compareTree(root1.left, root2.left) &&
      compareTree(root1.right, root2.right)) ||
    (compareTree(root1.left, root2.right) &&
      compareTree(root1.right, root2.left))
  );
}
console.log(compareTree(a1, a2));

二叉树的 diff 算法

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
var a1 = new Node("a");
var b1 = new Node("b");
var c1 = new Node("c");
var d1 = new Node("d");
var e1 = new Node("e");
var f1 = new Node("f");
var g1 = new Node("g");
a1.left = c1;
a1.right = b1;
c1.left = f1;
c1.right = g1;
b1.left = d1;
b1.right = e1;
var a2 = new Node("a");
var b2 = new Node("b");
var c2 = new Node("c");
var d2 = new Node("x");
var e2 = new Node("e");
var f2 = new Node("f");
var g2 = new Node("g");
a2.left = c2;
a2.right = b2;
c2.left = f2;
// c2.right = g2;
b2.left = d2;
b2.right = e2;
f2.right = g2;
//新增了什么，修改了什么，删除了什么

// {type:"新增",origin:null,now :c2},
// {type:"修改",origin:c1,now:c2},
// {type:"删除".origin:c2,now:null}
function diffTree(root1, root2, diffList) {
  if (root1 == root2) return diffList;
  if (root1 == null && root2 != null) {
    //新增了节点
    diffList.push({ type: "新增", origin: null, now: root2 });
  } else if (root1 != null && root2 == null) {
    //删除了节点
    diffList.push({ type: "删除", origin: root1, now: null });
  } else if (root1.value != root2.value) {
    //相同位置节点值不同了，修改了节点
    diffList.push({ type: "修改", origin: root1, now: root2 });
    diffTree(root1.left, root2.left, diffList); //修改不一定改儿孙
    diffTree(root1.right, root2.right, diffList);
  } else {
    diffTree(root1.left, root2.left, diffList);
    diffTree(root1.right, root2.right, diffList);
  }
}
var diffList = [];
diffTree(a1, a2, diffList);
console.log(diffList);

图的最小生成树问题

希望将所有村庄联通，花费最小

树：有向无环图

普利姆算法——加点法

克鲁斯卡尔算法——加边法

普利姆算法

  1. 选一个点作为起点
  2. 找到以当前选中点为起点路径最短的边
  3. 如果这个边的另一端没有被联通起来，那么就联结
  4. 如果这个边的另一端也早就被连进来了，则看倒数第二短的边
  5. 重复 2-4 直到所有的点都联通为止

克鲁斯卡尔算法

  1. 选择最短的边进行连接
  2. 要保证边连接的两端至少有一个点是新的要点
  3. 或者这个边是将两个部落进行连接的
  4. 重复 1-3 直到将所有的点都连接到一起

代码实现

表示一个图，可以使用点集合和边集合

点集合：[a,b,c,d,e,f]

A B C D E
A 0 4 7 max max
B 4 0 8 6 max
C 7 8 0 5 max
D max 6 5 0 7
E max max 7 0 
var max = 1000000;
var pointSet = [];
var distance = [
  [0, 4, 7, max, max],
  [4, 0, 8, 6, max],
  [7, 8, 0, 5, max],
  [max, 6, 5, 0, 7],
  [max, max, max, 7, 0],
];

function Node(value) {
  this.value = value;
  this.neighbor = [];
}

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");

pointSet.push(a);
pointSet.push(b);
pointSet.push(c);
pointSet.push(d);
pointSet.push(e);

//得到当前str对应的那一列的行
function getIndex(str) {
  for (var i = 0; i < pointSet.length; i++) {
    if (str == pointSet[i].value) return i;
  }
  return -1; //愚蠢的错误，要写在for外面
}

//需要传入点的集合，边的集合，当前已经连接进入的集合
// 此方法，根据当前已经有的节点，来进行判断，获取到距离最短的点
function getMinDisNode(pointSet, distance, nowPointSet) {
  var fromNode = null; //线段的起点
  var minDisNode = null; //线段的终点
  var minDis = max;
  //根据当前已有的这些点为起点，依次判断连接其他的点的距离是多少
  for (var i = 0; i < nowPointSet.length; i++) {
    var nowPointIndex = getIndex(nowPointSet[i].value); //获取当前节点的序号
    for (var j = 0; j < distance[nowPointIndex].length; j++) {
      var thisNode = pointSet[j]; //thisNode表示distance中的点，但是这个点不是对象。
      if (
        nowPointSet.indexOf(thisNode) < 0 && //首先这个点不能是已经接入的点
        distance[nowPointIndex][j] < minDis
      ) {
        //其次点之间的距离得是目前的最短距离
        fromNode = nowPointSet[i];
        minDisNode = thisNode;
        minDis = distance[nowPointIndex][j]; //更新最小距离
      }
    }
  }
  fromNode.neighbor.push(minDisNode); //起点和终点相连：即互相是邻居
  minDisNode.neighbor.push(fromNode);
  return minDisNode;
}

function prim(pointSet, distance, start) {
  var nowPointSet = [];
  nowPointSet.push(start);
  //获取最小代价的边
  while (true) {
    var minDisNode = getMinDisNode(pointSet, distance, nowPointSet);
    nowPointSet.push(minDisNode); //又连进来一个点
    if (nowPointSet.length == pointSet.length) {
      //所有的点都连进来了
      break;
    }
  }
}

prim(pointSet, distance, pointSet[2]); //'C'

console.log(pointSet);
var max = 1000000;
var pointSet = [];
var distance = [
  [0, 4, 7, max, max],
  [4, 0, 8, 6, max],
  [7, 8, 0, 5, max],
  [max, 6, 5, 0, 7],
  [max, max, max, 7, 0],
];

function Node(value) {
  this.value = value;
  this.neighbor = [];
}

var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");

pointSet.push(a);
pointSet.push(b);
pointSet.push(c);
pointSet.push(d);
pointSet.push(e);

function canLink(resultList, tempBegin, tempEnd) {
  var beginIn = null;
  var endIn = null;
  for (var i = 0; i < resultList.length; i++) {
    if (resultList[i].indexOf(tempBegin) > -1) {
      beginIn = resultList[i];
    }
    if (resultList[i].indexOf(tempEnd) > -1) {
      endIn = resultList[i];
    }
  }
  //两个点都是新的点（都不在任何部落里）——可以连接，产生新的部落
  // begin在A部落，end没有部落 —— A部落扩张一个村庄
  // end在A部落，begin没有部落 ——A部落扩张一个村庄
  // begin在A部落，end在B部落 ——将AB两个部落合并
  // begin和end在同一个部落，——不可以连接
  if (beginIn != null && endIn != null && beginIn == endIn) {
    return false;
  }
  return true;
}

function link(resultList, tempBegin, tempEnd) {
  var beginIn = null;
  var endIn = null;
  for (var i = 0; i < resultList.length; i++) {
    if (resultList[i].indexOf(tempBegin) > -1) {
      beginIn = resultList[i];
    }
    if (resultList[i].indexOf(tempEnd) > -1) {
      endIn = resultList[i];
    }
  }
  if (beginIn == null && endIn == null) {
    // 两个点都是新的点（都不在任何部落里）——可以连接，产生新的部落
    var newArr = [];
    newArr.push(tempBegin);
    newArr.push(tempEnd);
    resultList.push(newArr);
  } else if (beginIn != null && endIn == null) {
    // begin在A部落，end没有部落 —— A部落扩张一个村庄
    beginIn.push(tempEnd);
  } else if (beginIn == null && endIn != null) {
    // end在A部落，begin没有部落 ——A部落扩张一个村庄
    endIn.push(tempBegin);
  } else if (beginIn != null && endIn != null && beginIn != endIn) {
    // begin在A部落，end在B部落 ——将AB两个部落合并
    var allIn = beginIn.concat(endIn);
    var needRemove = resultList.indexOf(endIn);
    resultList.splice(needRemove, 1);
    needRemove = resultList.indexOf(beginIn);
    resultList.splice(needRemove, 1);
    resultList.push(allIn);
  }
  tempBegin.neighbor.push(tempEnd);
  tempEnd.neighbor.push(tempBegin);
}

function kruskal(pointSet, distance) {
  var resultList = []; //这里是二维数组，此数组代表的是有多少个"部落"

  while (true) {
    var minDis = max;
    var begin = null;
    var end = null;
    for (var i = 0; i < distance.length; i++) {
      for (var j = 0; j < distance[i].length; j++) {
        //遍历二维数组
        var tempBegin = pointSet[i];
        var tempEnd = pointSet[j];
        if (
          i != j && //去掉自己到自己的距离，因为都为0
          distance[i][j] < minDis &&
          canLink(resultList, tempBegin, tempEnd)
        ) {
          minDis = distance[i][j];
          begin = tempBegin;
          end = tempEnd;
        }
      }
    }
    link(resultList, begin, end);
    if (resultList.length == 1 && resultList[0].length == pointSet.length) {
      //只存在一个部落并且部落里的村庄数=所有
      break;
    }
  }
}

kruskal(pointSet, distance);
console.log(pointSet);

二叉搜索树

问题：有一万个数，写一个方法，进行查找，查找给定的数，返回是否存在。尽可能性能好

var arr = [];
for (var i = 0; i < 10000; i++) {
  arr[i] = Math.floor(Math.random() * 10000);
}
var num = 0;
function search(arr, target) {
  for (var i = 0; i < arr.length; i++) {
    num += 1;
    if (arr[i] == target) return true;
  }
  return false;
}
console.log(search(arr, 1000));
console.log(num);

性能差：1.数据结构;2.算法
问题出在数据结构上
二叉搜索树(二叉排序树)

  1. 二叉树
  2. 有排序的效果，左子树节点都比当前节点小，右子树节点都比当前节点大

二叉搜索树

var arr = [];

for (var i = 0; i < 10000; i++) {
  arr[i] = Math.floor(Math.random() * 10000);
}

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

var num = 0;
function search(arr, target) {
  for (var i = 0; i < arr.length; i++) {
    num += 1;
    if (arr[i] == target) return true;
  }
  return false;
}

function addNode(root, num) {
  if (root == null) return;
  if (root.value == num) return; //重复的数
  if (root.value < num) {
    //目标值比当前节点大
    if (root.right == null) root.right = new Node(num);
    //如果右侧为空，则创建节点
    else addNode(root.right, num); //如果右侧不为空，则向右侧进行递归
  } else {
    //目标值比当前节点小
    if (root.left == null) root.left = new Node(num);
    else addNode(root.left, num);
  }
}

function buildSearchTree(arr) {
  if (arr == null || arr.length == 0) return null;
  var root = new Node(arr[0]);
  for (var i = 1; i < arr.length; i++) {
    addNode(root, arr[i]);
  }
  return root;
}

var num2 = 0;
function searchByTree(root, target) {
  //二叉搜索树查找过程 前序遍历
  if (root == null) return false;
  num2 += 1;
  if (root.value == target) return true;
  if (root.value > target) return searchByTree(root.left, target);
  else return searchByTree(root.right, target);
}

console.log(search(arr, 1000));
console.log(num);

var root = buildSearchTree(arr);

console.log(searchByTree(root, 1000));
console.log(num2);

平衡二叉树

根节点的左子树与右子树高度差不超过 1；
这颗二叉树的每个子树都符合第一条

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");
var h = new Node("h");
var j = new Node("j");

a.left = b;
a.right = c;
b.left = d;
// b.right = e;
c.left = f;
c.right = g;
d.right = h;
// e.right = j;

function getDeep(root) {
  //获取深度
  if (root == null) return 0;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  return Math.max(leftDeep, rightDeep) + 1; //加上当前一层
}

function isBalance(root) {
  if (root == null) return true;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) > 1) {
    //不平衡
    return false;
  } else {
    return isBalance(root.left) && isBalance(root.right); //两边同时平衡
  }
}

console.log(isBalance(b));

二叉树的单旋

不平衡变成平衡

某一节点不平衡，如果左边浅，右边深，进行左单旋
旋转节点：不平衡的节点为旋转节点（2）
新根：旋转之后称为根节点的节点（5)
变化分支：父级节点发生变化的那个分支
不变分支：父级节点不变的那个分支

左单旋时：
旋转节点：当前不平衡的节点
新根：右子树的根节点
变化分支：旋转节点的右子树的左子树
不变分支：旋转节点的右子树的右子树

右单旋时：
旋转节点：当前不平衡的节点
新根：左子树的根节点
变化分支：旋转节点的左子树的右子树
不变分支：旋转节点的右子树的左子树

左单旋：

  1. 找到新根 5
  2. 找到变化分支
  3. 当前旋转节点的右子树为变化分支
  4. 新根的左孩子为旋转节点
  5. 返回新的根节点
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

var node2 = new Node("2");
var node5 = new Node("5");
var node3 = new Node("3");
var node6 = new Node("6");

node2.right = node5;
node5.left = node3;
node5.right = node6;

function getDeep(root) {
  if (root == null) return 0;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  return Math.max(leftDeep, rightDeep) + 1;
}

function isBalance(root) {
  if (root == null) return true;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) > 1) {
    //不平衡
    return false;
  } else {
    return isBalance(root.left) && isBalance(root.right);
  }
}

function leftRotate(root) {
  // 找到新根
  var newRoot = root.right;
  // 找到变化分支
  var changeTree = root.right.left;
  // 当前旋转节点的右孩子为变化分支
  root.right = changeTree;
  // 新根的左孩子为旋转节点
  newRoot.left = root;
  // 返回新的根节点
  return newRoot;
}

function rightRotate(root) {
  // 找到新根
  var newRoot = root.left;
  // 找到变化分支
  var changeTree = root.left.right;
  // 当前旋转节点的左孩子为变化分支
  root.left = changeTree;
  // 新根的右孩子为旋转节点
  newRoot.right = root;
  // 返回新的根节点
  return newRoot;
}

function change(root) {
  //返回平衡之后的根节点
  if (isBalance(root)) return root;
  // 推荐用后序的方式来判断，先变子节点，后变根节点
  if (root.left != null) root.left = change(root.left); // change后根节点root就变了
  if (root.right != null) root.right = change(root.right);
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) < 2) {
    return true;
  } else if (leftDeep > rightDeep) {
    //不平衡，左边深，需要右旋
    return rightRotate(root);
  } else {
    //不平衡，右边深，需要左旋
    return leftRotate(root);
  }
}

console.log(isBalance(node2));

var newRoot = change(node2);

console.log(isBalance(newRoot));
console.log(newRoot);

二叉树的双旋

单旋不能满足所有
变化分支不可是唯一的变化分支
如果是 要先进行反向旋转
二叉树的双旋（左右双旋，右左双旋）
右左双旋：当要对某个节点进行左单旋，如果变化分支是唯一的最深分支，那么要对新根进行右单旋，然后左单旋
反之左右双旋

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

var node8 = new Node("8");
var node7 = new Node("7");
var node6 = new Node("6");
var node5 = new Node("5");
var node2 = new Node("2");

node8.left = node7;
node7.left = node6;
node6.left = node5;
node5.left = node2;

function getDeep(root) {
  if (root == null) return 0;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  return Math.max(leftDeep, rightDeep) + 1;
}

function isBalance(root) {
  if (root == null) return true;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) > 1) {
    //不平衡
    return false;
  } else {
    return isBalance(root.left) && isBalance(root.right);
  }
}

function leftRotate(root) {
  // 找到新根
  var newRoot = root.right;
  // 找到变化分支
  var changeTree = root.right.left;
  // 当前旋转节点的右孩子为变化分支
  root.right = changeTree;
  // 新根的左孩子为旋转节点
  newRoot.left = root;
  // 返回新的根节点
  return newRoot;
}

function rightRotate(root) {
  // 找到新根
  var newRoot = root.left;
  // 找到变化分支
  var changeTree = root.left.right;
  // 当前旋转节点的左孩子为变化分支
  root.left = changeTree;
  // 新根的右孩子为旋转节点
  newRoot.right = root;
  // 返回新的根节点
  return newRoot;
}

function change(root) {
  //返回平衡之后的根节点
  if (isBalance(root)) return root;
  if (root.left != null) root.left = change(root.left);
  if (root.right != null) root.right = change(root.right);
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) < 2) {
    return root;
  } else if (leftDeep > rightDeep) {
    //不平衡，左边深，需要右旋
    var changeTreeDeep = getDeep(root.left.right);
    var noChangeTreeDeep = getDeep(root.left.left);
    if (changeTreeDeep > noChangeTreeDeep) {
      //变化树比较深
      root.left = leftRotate(root.left); //左子树进行左单旋
    }
    return rightRotate(root);
  } else {
    //不平衡，右边深，需要左旋
    var changeTreeDeep = getDeep(root.right.left);
    var noChangeTreeDeep = getDeep(root.right.right);
    if (changeTreeDeep > noChangeTreeDeep) {
      root.right = rightRotate(root.right);
    }
    return leftRotate(root);
  }
  return root;
}

function addNode(root, num) {
  if (root == null) return;
  if (root.value == num) return;
  if (root.value < num) {
    //目标值比当前节点大
    if (root.right == null) root.right = new Node(num);
    //如果右侧为空，则创建节点
    else addNode(root.right, num); //如果右侧不为空，则向右侧进行递归
  } else {
    //目标值比当前节点小
    if (root.left == null) root.left = new Node(num);
    else addNode(root.left, num);
  }
}

function buildSearchTree(arr) {
  if (arr == null || arr.length == 0) return null;
  var root = new Node(arr[0]);
  for (var i = 1; i < arr.length; i++) {
    addNode(root, arr[i]);
  }
  return root;
}

var num2 = 0;
function searchByTree(root, target) {
  if (root == null) return false;
  num2 += 1;
  if (root.value == target) return true;
  if (root.value > target) return searchByTree(root.left, target);
  else return searchByTree(root.right, target);
}
var arr = [];
for (var i = 0; i < 10000; i++) {
  arr.push(Math.floor(Math.random() * 10000));
}

var root = buildSearchTree(arr);
// console.log(searchByTree(root, 1000));
// console.log(num2);

var newRoot = change(root);
// num2 = 0;
// console.log(searchByTree(newRoot, 1000));
// console.log(num2);
console.log(isBalance(newRoot));

// console.log(isBalance(node8));
//
// var newRoot = change(node8);
//
// console.log(isBalance(newRoot));//目前还是不能平衡，因为还有特殊情况 需要左左双旋，右右双旋
// console.log(newRoot);

左 左 双 旋 与 右 右 双 旋

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

var node8 = new Node("8");
var node7 = new Node("7");
var node6 = new Node("6");
var node5 = new Node("5");
var node2 = new Node("2");

node8.left = node7;
node7.left = node6;
node6.left = node5;
node5.left = node2;

function getDeep(root) {
  if (root == null) return 0;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  return Math.max(leftDeep, rightDeep) + 1;
}

function isBalance(root) {
  if (root == null) return true;
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) > 1) {
    //不平衡
    return false;
  } else {
    return isBalance(root.left) && isBalance(root.right);
  }
}

function leftRotate(root) {
  // 找到新根
  var newRoot = root.right;
  // 找到变化分支
  var changeTree = root.right.left;
  // 当前旋转节点的右孩子为变化分支
  root.right = changeTree;
  // 新根的左孩子为旋转节点
  newRoot.left = root;
  // 返回新的根节点
  return newRoot;
}

function rightRotate(root) {
  // 找到新根
  var newRoot = root.left;
  // 找到变化分支
  var changeTree = root.left.right;
  // 当前旋转节点的左孩子为变化分支
  root.left = changeTree;
  // 新根的右孩子为旋转节点
  newRoot.right = root;
  // 返回新的根节点
  return newRoot;
}

function change(root) {
  //返回平衡之后的根节点
  if (isBalance(root)) return root;
  if (root.left != null) root.left = change(root.left);
  if (root.right != null) root.right = change(root.right);
  var leftDeep = getDeep(root.left);
  var rightDeep = getDeep(root.right);
  if (Math.abs(leftDeep - rightDeep) < 2) {
    return root;
  } else if (leftDeep > rightDeep) {
    //不平衡，左边深，需要右旋
    var changeTreeDeep = getDeep(root.left.right);
    var noChangeTreeDeep = getDeep(root.left.left);
    if (changeTreeDeep > noChangeTreeDeep) {
      root.left = leftRotate(root.left);
    }
    var newRoot = rightRotate(root);
    newRoot.right = change(newRoot.right); //每次右旋了之后有可能再次右旋。再来一遍，右侧分支进行再次平衡，右侧分支的高度变了，所以要对自己再做一次平衡，
    newRoot = change(newRoot); //对自己再做一次平衡
    return newRoot;
  } else {
    //不平衡，右边深，需要左旋
    var changeTreeDeep = getDeep(root.right.left);
    var noChangeTreeDeep = getDeep(root.right.right);
    if (changeTreeDeep > noChangeTreeDeep) {
      root.right = rightRotate(root.right);
    }
    var newRoot = leftRotate(root);
    newRoot.left = change(newRoot.left);
    newRoot = change(newRoot);
    return newRoot;
  }
  return root;
}

function addNode(root, num) {
  if (root == null) return;
  if (root.value == num) return;
  if (root.value < num) {
    //目标值比当前节点大
    if (root.right == null) root.right = new Node(num);
    //如果右侧为空，则创建节点
    else addNode(root.right, num); //如果右侧不为空，则向右侧进行递归
  } else {
    //目标值比当前节点小
    if (root.left == null) root.left = new Node(num);
    else addNode(root.left, num);
  }
}

function buildSearchTree(arr) {
  if (arr == null || arr.length == 0) return null;
  var root = new Node(arr[0]);
  for (var i = 1; i < arr.length; i++) {
    addNode(root, arr[i]);
  }
  return root;
}

var num2 = 0;
function searchByTree(root, target) {
  if (root == null) return false;
  num2 += 1;
  if (root.value == target) return true;
  if (root.value > target) return searchByTree(root.left, target);
  else return searchByTree(root.right, target);
}
var arr = [];
for (var i = 0; i < 10000; i++) {
  arr.push(Math.floor(Math.random() * 10000));
}

var root = buildSearchTree(arr);
console.log(searchByTree(root, 1000));
console.log(num2);

var newRoot = change(root);
num2 = 0;
console.log(searchByTree(newRoot, 1000));
console.log(num2);
console.log(isBalance(newRoot));

// console.log(isBalance(node8));
//
// var newRoot = change(node8);
//
// console.log(isBalance(newRoot));
// console.log(newRoot);

进行了一系列操作后，性能还未达到极致，需要再次探索。
​

234 树的由来

树的深度优先搜索

function Node(value) {
  this.value = value;
  this.childs = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");

a.childs.push(c);
a.childs.push(f);
a.childs.push(b);
b.childs.push(d);
b.childs.push(e);

function deepSearch(root, target) {
  if (root == null) return false;
  if (root.value == target) return true;
  var result = false;
  for (var i = 0; i < root.childs.length; i++) {
    result |= deepSearch(root.childs[i], target);
  }
  return result ? true : false;
}

console.log(deepSearch(a, "n"));

树的广度优先搜索

function Node(value) {
  this.value = value;
  this.childs = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");

a.childs.push(c);
a.childs.push(f);
a.childs.push(b);
b.childs.push(d);
b.childs.push(e);

function bfs(roots, target) {
  if (roots == null || roots.length == 0) return false;
  var childs = [];
  for (var i = 0; i < roots.length; i++) {
    if (roots[i].value == target) {
      return true;
    } else {
      childs = childs.concat(roots[i].childs);
    }
  }
  return bfs(childs, target);
}

console.log(bfs([a], "n"));

图的深度优先

不要形成环，防止死循环—-找过的点就不找了

function Node(value) {
  this.value = value;
  this.neighbor = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");

a.neighbor.push(b);
a.neighbor.push(c);
b.neighbor.push(a);
b.neighbor.push(c);
b.neighbor.push(d);
c.neighbor.push(a);
c.neighbor.push(b);
c.neighbor.push(d);
d.neighbor.push(b);
d.neighbor.push(c);
d.neighbor.push(e);
e.neighbor.push(d);

function deepSearch(node, target, path) {
  if (node == null) return false;
  if (path.indexOf(node) > -1) return false; //这个点找过了
  if (node.value == target) return true;
  path.push(node);
  var result = false;
  for (var i = 0; i < node.neighbor.length; i++) {
    result |= deepSearch(node.neighbor[i], target, path); //一真为真
  }
  return result ? true : false;
}

console.log(deepSearch(b, "d", [])); //b节点开始，找d是不是在里面，返回找过的路径

图的广度优先

function Node(value) {
  this.value = value;
  this.neighbor = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");

a.neighbor.push(b);
a.neighbor.push(c);
b.neighbor.push(a);
b.neighbor.push(c);
b.neighbor.push(d);
c.neighbor.push(a);
c.neighbor.push(b);
c.neighbor.push(d);
d.neighbor.push(b);
d.neighbor.push(c);
d.neighbor.push(e);
e.neighbor.push(d);

function bfs(nodes, target, path) {
  if (nodes == null || nodes.length == 0) return false;
  var nextNodes = [];
  for (var i = 0; i < nodes.length; i++) {
    if (path.indexOf(nodes[i]) > -1) continue; //存在的话看下一个
    path.push(nodes[i]); //代表填过了  不存在就push进去
    if (nodes[i].value == target) return true;
    else nextNodes = nextNodes.concat(nodes[i].neighbor); //把它的邻居全添加到下一步要走的路里
  }
  return bfs(nextNodes, target, path);
}

console.log(bfs([c], "n", []));

动态规划-斐波那契数列

// 动态规划，笔试遇到动态规划是后面的大题

// 0, 1, 1, 2, 3, 5, 8, 13, 21 ……
// 给出第n位，问第n位值为几？

function fibo(n) {
  if (n <= 0) return -1;
  if (n == 1) return 0;
  if (n == 2) return 1;
  var a = 0;
  var b = 1;
  var c = 0;
  for (var i = 3; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return c;
}

// f(n) = f(n-1) + f(n-2);
function fibo2(n) {
  if (n <= 0) return -1;
  if (n == 1) return 0;
  if (n == 2) return 1;
  return fibo2(n - 1) + fibo2(n - 2);
}

console.log(fibo2(7));

动态规划-青蛙跳台阶

// 一个青蛙，一次只能跳一级台阶，或者跳两级台阶。
// 问：这个青蛙跳上n级台阶有多少种跳法。

// 如果这只青蛙，跳上了第n级台阶，那么最后一次跳跃之前，他一定在n-1级台阶或n-2级台阶上。
// 那么跳上n级台阶有多少种情况就变成了两个子问题
// 跳上n-1级台阶的跳法 加上 跳上n-2级台阶的跳法。

// 按照此逻辑递推，跳上n-1级台阶可以拆解为两个子问题
// 既：跳上n-2级台阶的跳法 加上 跳上n-3级台阶的跳法

// f(n) = f(n-1) + f(n-2)

function jump(n) {
  if (n <= 0) return -1; //0级
  if (n == 1) return 1; //一级 一种
  if (n == 2) return 2; //两级 两种
  return jump(n - 1) + jump(n - 2);
}

牛客网多练

变态青蛙跳台阶

//
// 这只青蛙，一次可以跳1级台阶、2级台阶、或n级台阶。
// 问：这只青蛙，跳上n级台阶有多少种方法?

// f(n) = f(n-1) + f(n-2) + f(n-3) + …… + f(2) + f(1) + f(0)

function jump(n) {
  if (n <= 0) return -1;
  if (n == 1) return 1;
  if (n == 2) return 2;
  var result = 0;
  for (var i = 1; i < n; i++) {
    result += jump(n - i);
  }
  return result + 1; // +1代表从0级台阶直接跳上去的情况
}
/*
 * 1,1,1,1,
 * 1,1,2
 * 1,2,1,
 * 2,1,1,
 * 1,3,
 * 3,1,
 * 2,2,
 * 4
 * */
console.log(jump(4));

深入算法
《算法导论》

文章作者: Sunny
文章链接: http://example.com/2020/07/23/%E5%89%8D%E7%AB%AF%E5%BF%85%E4%BC%9A%E7%AE%97%E6%B3%95/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Sunny !
algorithm
赏
  目录