AboutFE 48、数据结构和算法

https://github.com/labuladong/fucking-algorithm
https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa https://www.geekxh.com/0.01.%E6%8C%87%E5%AF%BC%E5%AD%A6%E4%B9%A0/021.html#_03%E3%80%81%E7%AE%97%E6%B3%95%E9%97%AE%E9%A2%98%E6%B1%87%E6%80%BB

May 30 '20 16:05 CodingMeUp

深度遍历DFS 和广度遍历BFS

 <div class="parent">
      <div class="child-1">
          <div class="child-1-1">
              <div class="child-1-1-1">
                a
              </div>
              <div class="child-1-1-2">
                b
              </div>              
          </div>
          <div class="child-1-2">
              <div class="child-1-2-1">
                c
              </div>    
          </div>     
          <div class="child-1-3">
                d
          </div>                 
      </div>
      <div class="child-2">
        <div class="child-2-1">
          e
        </div>
        <div class="child-2-2">
          f
        </div>        
      </div>
      <div class="child-3">
        <div class="child-3-1">
          g
        </div>
      </div>
  </div>

深度优先遍历 - 递归

    var dfs_recursive = function(root, res = []){
      res.push(root)
      for (let item of root.children) {
        dfs_recursive(item, res)
      }
      return res
    }
    console.log('1------------->>', dfs_recursive(root))

深度优先遍历 - stack 先进后出【push(item) -> pop】或者 [unshift(item) -> shift()]

    var dfs_stack = function(root) {
      const res = []
      const stack = []
      stack.push(root)
      while (stack.length != 0) {
        let item = stack.pop()
        res.push(item)
        for (let i = item.children.length - 1; i >= 0; i--) {
          stack.push(item.children[i])
        }
      }
      return res
    }
    console.log('2------------->>', dfs_stack(root))

广度优先遍历 - queue 先进先出[push(item) -> shift()] 或者[unshift(item) -> pop()]

    var bfs_queue = function(root) {
      const res = []
      const queue = []
      queue.push(root)
      while (queue.length != 0) {
        let currentLevelLength = queue.length
        for (let i = 0 ; i < currentLevelLength; i++) {
          let item = queue.shift()
          res.push(item)
          for (let j = 0; j < item.children.length; j++) {
            queue.push(item.children[j])
          }
        }
      }
      return res
    }
    console.log('3------------->>', bfs_queue(root))

Jun 16 '20 09:06 CodingMeUp

遍历tree

觉得用这几个字母表示递归遍历的三种方法不错： D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。

哪个遍历就哪个在中间

先序遍历：DLR
中序遍历：LDR
后序遍历：LRD

这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总是优先往深处访问。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        //创建二叉树
        function Node(data,left,right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
        Node.prototype.show = function(){
            return this.data;
        }
        function BST(){
            this.root = null;
        }
        BST.prototype.insert = function(data){
            var node = new Node(data,null,null);
            if(this.root == null){
                this.root = node;
            }else{
                var current = this.root;
                var parent;
                while(true){
                    parent = current;
                    if(data < current.data){
                        current = current.left;
                        if(current == null){
                            parent.left = node;
                            break;
                        }
                    }else{
                        current = current.right;
                        if(current == null){
                            parent.right = node;
                            break;
                        }
                    }
                }
            }
        }
        //二叉树中序遍历
        BST.prototype.inOrder = function(node){
            if(node){
                this.inOrder(node.left);
                console.log(node.show() + " ");
                this.inOrder(node.right);
            }
        }
        //测试数据
        var bst  = new BST();
        var nums = [10,3,18,2,4,13,21,9,8,9];
        console.log('src', nums);
        for(var i = 0;i < nums.length;i ++){
            bst.insert(nums[i]);
        }
        bst.inOrder(bst.root);
    </script>
</body>
</html>

先序遍历的算法：

// 递归
var preOrder = function (node) { 
 if (node) {
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
 }
}
// 非递归
var preOrderUnRecur = function(root) { 
  var stack=[],res=[];
  if(root!=null){
      stack.push(root);
  }
  while(arr.length!=0){
      var temp=stack.pop();
      res.push(temp.val);
      // 栈中元素都是自己和自己的左孩子都访问过了，而右孩子还没有访问到的节点， 而且先序遍历stack要后面塞left才能弹出left
      if(temp.right!=null){
          stack.push(temp.right);
      }
      if(temp.left!=null){
          stack.push(temp.left);
      }
  }
  return res;
}

中序遍历的算法：

// 递归
var inOrder = function (node) { 
 if (node) {
  inOrder(node.left);  //先遍历到最左边的节点，然后输出
   console.log(node.value);
  inOrder(node.right);
 }
}
// 非递归 栈中保存的元素是节点自身和它的右子树都没有被访问到的节点地址
var inOrderUnRecur = function(root) { 
  va stack=[],res=[];
  while(true){
      while(root!=null){
          stack.push(root);
          root=root.left;
      }
      //终止条件：最后树遍历完了自然就结束
      if(stack.length==0){
          break;
      }
      var temp=stack.pop();
      res.push(temp.val);
      root=temp.right;
  }
  return res;
}

后序遍历的算法：

// 递归
var postOrder = function (node) { 
 if (node) {
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
 }
}
// 非递归 栈中保存的元素是它的右子树和自身都没有被遍历到的节点，
与中序遍历不同的是先访问右子树，在回来的时候再输出根节点的值。
var posOrderUnRecur = function(root) { 
  var stack=[],res=[];
  if (root !== null) {
    stack.push(root);
  }
  while(stack.length !== 0) {
      var temp = stack.pop();
      if (temp !== null) {
        res.push(temp.val);
      }
      if(temp.left!=null){
          stack.push(temp.left);
      }
      if(temp.right!=null){
          stack.push(temp.right);
      }
  }
  return res.reverse();
}

层次遍历

let levelTrav = (root) => {
  if(!root) return []
    let queue = [root]
    let res = []
    while(queue.length > 0){
      let len = queue.length
      let arr = []
      while(len){
        let node = queue.shift()
        arr.push(node.val)
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
        len--
      }
      res.push(arr)
    }
    return res
}

Jul 02 '20 15:07 CodingMeUp

前端数据结构

VDOM Fiber Hooks

{
  type: 'div',
  props: {
    name: 'lucifer'
  },
  children: [{
    type: 'span',
    props: {},
    children: []
  }]
}

逻辑上 VDOM 就是用来抽象 DOM 的(面向 DOM 编程，切换到面向 VDOM 编程，而现在 VDOM 又是由数据驱动的，因此我们的编程模式切换到了“数据驱动)
底层上 VDOM 普遍实现是基于hash table 这种数据结构的, VDOM 是一种递归的数据结构，因此使用递归的方式来处理是非常直观和容易的
VDOM Diff React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的

为什么O3 树的最小距离编辑算法的时间复杂度是O(n^2m(1+logmn)), 我们假设m 等于 n，就变成 O(n^3), 这里的n指的是页面的VDOM节点数，这个不太严谨。如果更严谨一点，我们应该应该假设变化之前的节点数为m，变化之后的节点数为n , 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
O3 -> O1 React 和 Vue 做的假设是：

检测VDOM的变化只发生在同一层检测VDOM的变化依赖于用户指定的key

如果变化发生在不同层或者同样的元素用户指定了不同的key或者不同元素用户指定同样的key， React 和 Vue都不会检测到，就会发生莫名其妙的问题。但是React 认为，前端碰到上面的第一种情况概率很小，第二种情况又可以通过提示用户，让用户去解决，因此这个取舍是值得的。没有牺牲空间复杂度，却换来了在大多数情况下时间上的巨大提升。明智的选择

Hooks 它要解决的问题是状态逻辑复用, 逻辑上解决了纯函数无法持久化状态的“问题”，从而拓宽了纯函数组件的适用范围.
Fiber 类似 VDOM，也是一个数据结构，而且同样也是一个递归的数据结构。为了解决 React 之前一次全量更新的"问题", React 引入了 fiber 这种数据结构，并重写了整个调和算法，并且划分了多个阶段

Git

React16 新的调和算法也有 Git 思想, Git 在推送本地仓库到远程的时候会进行压缩，其实这里就用到了最小编辑距离算法, 就是上面那个Diff 的题

Webpack

Webpack 是众所周知的一个前端构建工具, webpack 的执行过程是基于事件驱动的，tapable 提供了一系列钩子，让 plugin 深入到这些过程之中去， acorn 去依赖收集ast

Browser History

像浏览器中的历史页面，移动端 webview 的 view stack, 都用到了栈这种数据结构

巨型Mapper的优化

由于业务需要，我们需要在前端缓存一些HTTP请求。我们设计了如下的数据结构，其中key表示资源的URL， value会上次服务端的返回值。

现在我们的项目中已经有上千个接口，当接口多起来之后，缓存占用会比较大，我们如何对此进行优化？这是一个典型的数据压缩算法，游程编码和哈夫曼编码

搜索自动联系

使用前缀树

leetcode

Jul 03 '20 03:07 CodingMeUp

基础技巧：分治、二分、贪心排序算法：快速排序、归并排序、计数排序搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等图论：最短路径、最小生成树动态规划：背包问题、最长子序列

数据结构，主要有如下几种：

数组与链表：单 / 双向链表栈与队列哈希表堆：最大堆／最小堆树与图：最近公共祖先、并查集字符串：前缀树（字典树）／后缀树

高级数据结构

优先队列 Priority Queue

本质：二叉堆结构，用一个数组结构来做完全二叉树区别：优先队列与普通队列的区别是：保证每次取出的元素是队列中优先级最高的。（优先级别可自定义）场景：从杂乱无章的数据中按照一定顺序筛选数据。特性：【1】 array[0]也就是第一个元素拥有最高优先级，下标index，那array[index]而言, 父节点index = (index - 1) / 2, 左侧子节点 2 * index + 1, 右侧子节点 2 * index + 2，【2】数组中每个元素的优先级都高于左右两侧 leetcode: 【347】, 取前K个高频元素, O（nlogn）

Jul 03 '20 17:07 CodingMeUp

AboutFE AboutFE copied to clipboard

48、数据结构和算法

深度遍历DFS 和 广度遍历BFS

遍历tree

先序遍历的算法：

中序遍历的算法：

后序遍历的算法：

层次遍历

前端数据结构

VDOM Fiber Hooks

Git

Webpack

Browser History

巨型Mapper的优化

搜索自动联系

高级数据结构

优先队列 Priority Queue

AboutFE
AboutFE copied to clipboard

深度遍历DFS 和广度遍历BFS