再谈前端算法

• 楔子 – 青蛙跳台阶
• 什么是算法
• 算法实例 ： 实现一个LRU缓存
  • 实现 LRUCache
  • 扩展： ES6 Map
    • Map的创建和初始化：
    • 添加键值对：
    • 获取键值对：
    • 检查Map中是否存在某个键：
    • 删除键值对：
    • 遍历Map：
    • 获取Map的大小：
• 算法实例 ： 求环状链表
  • 扩展： 链表
• 算法实例 ：二又树的前序、中序、后序遍历
  • 前序遍历 - 根左右
  • 中序遍历 - 左根右
  • 后序遍历 - 左右根
  • 举例
  • 实现代码
• （二叉树）层序遍历
• （二叉树）的层级
• 类数组转数组有多少种方法
  • 扩展运算符
  • prototype
  • Array.from
  • Array.apply
• 扩展： ES6新增了数组哪些方法？

楔子 – 青蛙跳台阶

一只青蛙一次可以跳上一级台阶，也可以跳上二级台阶，求该青蛙跳上一个n级的台阶总共需要多少种跳法。

分析: 当n=1的时候，①只需要跳一次即可；只有一种跳法，即f(1)=1；

当n=2的时候，①可以先跳一级再跳一级，②也可以直接跳俩级；共有俩种跳法，即f(2)=2；

当n=3的时候，①一阶一阶跳即可；
②他可以从一级台阶上跳俩阶上来
③也可从二级台阶上跳一阶上来;即共有f(3)=f(2)+f(1)；

所以当有n阶台阶时，且当n>2的时候，根据上面式子可推导出→ f(n)=f(n-1)+f(n-2)

所以很直白的看出就是个 斐波那契数列 ，有一点不同的是，斐波那契数列从1,1,2,3,5,8,13…开始的，而我们这是以1,2,3,5,8,13…开始的，少了前面的1

什么是算法

解决一系列问题的具体步骤

算法是一组用于解决特定问题或执行特定任务的有限步骤序列。这些步骤按照确定的顺序执行，以达到所需的结果。在计算机科学中，算法通常用于描述数据处理、自动化处理和数学运算的过程。算法可以用来解决各种问题，包括排序、搜索、路径规划等。

算法实例 ： 实现一个LRU缓存

LRU是Least Recently Used（最近最少使用）的缩写。

在计算机科学中，LRU是一种页面置换算法，通常用于操作系统的虚拟内存管理中。

该算法根据页面（或者其他资源）的最近使用情况来进行置换，当需要置换时，选择最近最少被使用的页面进行替换。

这样可以保证最常用的页面保留在内存中，从而提高性能。

实例：vue keep-alive 缓存

LRU – 最近使用

实现 LRUCache

缓存，有一个大小 const lru = new LRUCache(capacity)

提示

const lru = new LRUCache(2)
lru.put(1,1)
lru.put(2,2) // {1:1,2:2}
lru.get(1)

lru.put(3,3) // {1:1,3:3}
lru.get(2) // -1 (找不到)

lru.put(4,4)  // {4:4,3:3}

实现代码

// 函数的 get 和 put 必须以 O(1)的时间复杂度运行 
// get，得是个hash（Map，Set），而不能是数组
// ES6 迭代器

const LRUCache = function(capacity){
 this.cacheQueue = new Map()
 this.capacity = capacity 
}

LRUCache.prototype.get = function(key){
  if(this.cacheQueue.has(key)){ // 如果找到了，这个key对应的value要提升新鲜度
    const result = this.cacheQueue.get(key)

    // 删掉，然后再放进去，这样，这个就能在cacheQueue的队尾(队尾为最新鲜地方)
    this.cacheQueue.delete(key) 
    this.cacheQueue.set(key,result) 
    return result

  }
  return -1 // 如果没有找到key，则直接返回 -1 
}


LRUCache.prototype.put = function(key,value){
   if(this.cacheQueue.has(key)){ 
    // 如果找到了， 删掉
     this.cacheQueue.delete(key)  
   }

   if(this.cacheQueue.size >= this.capacity){
      // 删除map的第一个元素，即最长时间未使用的
      this.cacheQueue.set(key,value)  
      this.cacheQueue.delete(this.cacheQueue.keys().next().value)  
   } else {
      this.cacheQueue.set(key,value)  
   }
}

扩展： ES6 Map

ES6的Map是一种内置的数据结构，它存储键值对并允许你通过键快速查找值。

Map对象类似于对象，但不同之处在于Map的键可以是任意数据类型，而对象的键只能是字符串或Symbol。

Map还保留了插入顺序，这意味着当你遍历一个Map对象时，它会按照插入顺序返回键值对。

Map的创建和初始化：

要创建一个新的Map，你需要使用new Map()语法。

例如：

const myMap = new Map();

添加键值对：

你可以使用Map对象的set()方法添加键值对。

例如：

myMap.set('key1', 'value1');
myMap.set('key2', 'value2');

获取键值对：

你可以使用Map对象的get()方法获取键对应的值。

例如：

const value1 = myMap.get('key1'); // 返回 'value1'
const value2 = myMap.get('key2'); // 返回 'value2'

检查Map中是否存在某个键：

你可以使用Map对象的has()方法检查Map中是否存在某个键。

例如：

const hasKey1 = myMap.has('key1'); // 返回 true
const hasKey3 = myMap.has('key3'); // 返回 false

删除键值对：

你可以使用Map对象的delete()方法删除键值对。

例如：

myMap.delete('key1');

遍历Map：

你可以使用Map对象的keys()、values()或entries()方法遍历Map中的键或值。

例如：

for (const key of myMap.keys()) {
  console.log(key); // 输出键名
}
for (const value of myMap.values()) {
  console.log(value); // 输出值
}
for (const [key, value] of myMap.entries()) {
  console.log(key, value); // 输出键名和值
}

myMap.forEach((value, key) => {
  console.log(key + ' = ' + value);
});

获取Map的大小：

myMap.size; // 返回Map的大小

更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。

算法实例 ： 求环状链表

leecode的地址：https://leetcode.cn/problems/linked-list-cycle/

链表：常见 – react源码

思路：快慢指针，两个（起点相同位置）指针，n步骤以后指针相遇

实现代码

head.next 指向下一个值

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = slow = head
    while(fast && fast.next){
        fast = fast.next.next
        slow = slow.next
        if(fast === slow){
            return true
        }  
    }
    return false
};

扩展： 链表

链表是一种数据结构，其中的元素以节点的形式按顺序排列。

每个节点都包含数据和指向下一个节点的引用。

相比数组，链表在插入和删除元素时更灵活，因为它们不需要连续的存储空间。

举例来说，一个简单的链表可以被定义如下：

Node 1: 23 -> Node 2
Node 2: 47 -> Node 3
Node 3: 95 -> null

在这个例子中，链表中的每个节点包含一个值和指向下一个节点的引用。

第一个节点包含值23，同时指向第二个节点，依此类推。最后一个节点指向null，表示链表的结束。

通过使用链表，我们可以轻松地插入或删除节点，而无需移动其他节点。

这使得链表在某些场景下比数组更为适用。

链表是一种物理存储结构上 非连续、非顺序 的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表有很多种不同的类型，包括单向链表、双向链表以及循环链表。

链表可以在多种编程语言中实现，例如C、C++和Java等。

算法实例 ：二又树的前序、中序、后序遍历

前序遍历 - 根左右

先走根节点，然后左，然后右

中序遍历 - 左根右

先走左节点，然后根节点，然后右节点

后序遍历 - 左右根

先走左节点，然后右节点，然后再根节点

举例

前/先序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
后序遍历: AEFDHZMG

前序遍历: A-B-D-F-G-H-I-E-C
中序遍历: F-D-H-G-I-B-E-A-C
后序遍历: F-H-I-G-D-E-B-C-A

实现代码

const treeRoot = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
    },
    right: {
      val: 5,
    }
  },
  right: {
    val: 3,
    left: {
      val: 6,
    },
    right: {
      val: 7,
    }
  }
}

// 前序
const preOrder = function(node){
  if(node){
    // 如果有根节点
    console.log(node.val)
    preOrder(node.left)
    preOrder(node.right)
  }
}

preOrder(treeRoot)

// 中序
const inOrder = function(node){
  if(node){
    // 如果有根节点
    inOrder(node.left)
    console.log(node.val)
    inOrder(node.right)
  }
}

inOrder(treeRoot)

// 后序
const nextOrder = function(node){
  if(node){
    // 如果有根节点
    nextOrder(node.left)
    nextOrder(node.right)
    console.log(node.val)
  }
}

nextOrder(treeRoot)

（二叉树）层序遍历

leetcode地址：https://leetcode.cn/problems/binary-tree-level-order-traversal/

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if(!root) return []
  let queue = [root]
  let result = []

  // 开始遍历
  while(queue.length){
    let temQueue = []
    let temResult = []
    let len = queue.length
    for(let i = 0; i < len; i++){
      let node = queue.shift()
      temResult.push(node.val)
      node.left && temQueue.push(node.left)
      node.right && temQueue.push(node.right)
    }
    // 循环完毕
    result.push(temResult)
    temResult = []
    queue = temQueue
  }
  return result
};

（二叉树）的层级

**leetcode地址：**https://leetcode.cn/problems/maximum-depth-of-binary-tree/

直接return 上面层序的lengh

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var maxDepth = function(root) {
  if(!root) return []
  let queue = [root]
  let result = []

  // 开始遍历
  while(queue.length){
    let temQueue = []
    let temResult = []
    let len = queue.length
    for(let i = 0; i < len; i++){
      let node = queue.shift()
      temResult.push(node.val)
      node.left && temQueue.push(node.left)
      node.right && temQueue.push(node.right)
    }
    // 循环完毕
    result.push(temResult)
    temResult = []
    queue = temQueue
  }
  return result.length
};

使用DP方法

let maxDepth = function(root){
  if(!root) return 0 // 如果没有根节点，则直接返回0
  // 找左右叉的最大值
  return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
}

类数组转数组有多少种方法

const arrayLike = document.querySelectorAll('div')

扩展运算符

[...arrayLike]

prototype

Array.prototype.slice.call(arrayLike) 
Array.prototype.concat.apply([],arrayLike)

Array.from

Array.from(arrayLike) 

Array.apply

Array.apply(null,arrayLike) 

扩展： ES6新增了数组哪些方法？

ES6新增了许多数组方法，主要包括以下几个：

1. find()：返回数组中符合测试函数条件的第一个元素值。

   const numbers = [10, 20, 30, 40];
   const result = numbers.find(num => num > 25);
   // 结果为30
   

2. findIndex()：返回数组中符合测试函数条件的第一个元素索引。

   const numbers = [10, 20, 30, 40];
   const index = numbers.findIndex(num => num > 25);
   // 结果为2（即元素30对应的索引）
   

3. forEach()：对数组的每个元素执行提供的函数。

   const numbers = [1, 2, 3];
   numbers.forEach(num => console.log(num * 2));
   // 输出2, 4, 6
   

4. map()：对数组的每个元素执行提供的函数，并返回结果组成的新数组。

   const numbers = [1, 2, 3];
   const doubled = numbers.map(num => num * 2);
   // 结果为[2, 4, 6]
   

5. filter()：使用给定函数测试所有元素，并返回由所有通过测试的元素组成的新数组。

   const numbers = [10, 15, 20, 25, 30];
   const greaterThan20 = numbers.filter(num => num > 20);
   // 结果为[25, 30]
   

这些方法在处理数组时非常有用，并且能够简化一些常见的操作。