数据结构与算法-基础知识

// 数据结构与算法是什么？
1. 数据结构：计算机存储、组织数据的方式，就像锅碗瓢盆
2. 算法：一系列解决问题的清晰指令，就像食谱
----------------------------------------------------------------------------------------------
// 数据结构与算法的关系
1. 程序 = 数据结构 + 算法
2. 数据结构为算法提供服务，算法围绕数据结构操作
----------------------------------------------------------------------------------------------
// 时间复杂度是什么？
1. 一个函数，用大 O 表示，比如 O(1)、O(n)、O(logN)
2. 时间复杂度用来定性描述该算法的运行时间 // 大概的趋势
3. O(n^2) > O(n) > O(logN) > O(1)
4. 只执行一次的代码的时间复杂度就是 O(1)
    let i = 0
    i += 1
5. 单次的循环的时间复杂度是 O(n)
    for (let i = 0; i < n; i++) {
      console.log(i)
    }
6. 计算时间复杂度的时候如果两个时间复杂度先后排列就把他们相加，而且要取增长趋势更快的时间复杂度
    let i = 0
    i += 1
    for (let i = 0; i < n; i++) {
      console.log(i)
    }
   以上代码的时间复杂度是 O(1) + O(n) = O(n)
7. 嵌套的循环的时间复杂度是相乘
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        console.log(i, j)
      }
    }
   以上代码的时间复杂度是 O(n) * O(n) = O(n^2)
8. let i = 1
   while (i < n) {
     console.log(i)
     i *= 2
   }
   以上代码的时间复杂度是 O(logN)
   // 如果 a^x=N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作log(a）N, 其中，a叫做对数的底数，N叫做真数。
   // 且a>o，a≠1，N>0。而这里则用logN也就是log（2）N，即求 2 的多次方为 N
----------------------------------------------------------------------------------------------
// 空间复杂度是什么？
1. 一个函数，用大 O 表示，比如 O(1)、O(n)、O(n^2)
2. 算法在运行过程中临时占有存储空间大小的量度 // 内存大小
3. 空间复杂度为 O(1) 的例子
    let i = 0
    i += 1
   只声明了一个变量，占用了一个内存单元
4. 空间复杂度为 O(n) 的例子
    const list = []
    for (let i = 0; i < n; i++) {
      list.push(i)
    }
   声明了 n 个变量，占用了 n 个内存单元
5. 空间复杂度为 O(n^2) 的例子
    const matrix = []
    for (let i = 0; i < n; i++) {
      matrix.push([])
      for (let j = 0; j < n; j++) {
        matrix[i].push(j)
      }
    }
----------------------------------------------------------------------------------------------
// 栈是什么？
1. 一个后进先出的数据结构
2. js 中没有栈，但可以用 Array 实现栈的所有功能 // push 和 pop
3. 应用场景：
    十进制转二进制
    判断字符串的括号是否有效
    函数调用堆栈
4. 常用操作：push、pop、stack[stack.length - 1]
----------------------------------------------------------------------------------------------
// 队列是什么？
1. 一个先进先出的数据结构
2. js 中没有队列，但可以用 Array 实现队列的所有功能 // push 和 shift
3. 应用场景：
    食堂排队打饭
    js 异步中的任务队列
    计算最近请求次数
----------------------------------------------------------------------------------------------
// 链表是什么？
1. 多个元素组成的列表
2. 元素存储不连续，用 next 指针连在一起
3. 数组和链表的区别
    数组：增删非首尾元素时往往需要移动元素
    链表：增删非首尾元素不需要移动元素，只需要更新 next 指针
4. js 中没有链表，可以用 Object 模拟
5. 示例：
    // 创建
    const a = { val: 'a' }
    const b = { val: 'b' }
    const c = { val: 'c' }
    a.next = b
    b.next = c
    // 遍历
    let p = a
    while(p) {
      console.log(p.val)
      p = p.next
    }
    // 插入
    const d = { val: 'd' }
    b.next = d
    d.next = c
    // 删除
    b.next = c
6. 如何删除链表中的某一个节点？
    把要删除的节点的下一位节点赋值给当前要删除的节点，再删除下一位的节点，这样就变相的删除了指定的节点
----------------------------------------------------------------------------------------------
// 集合是什么？
1. 一种无序且唯一的数据结构
2. ES6 中有集合 Set
3. 集合的常用操作：
    去重、判断某元素是否在集合中、求交集
    // 去重
    const arr = [1, 1, 2, 2]
    const newArr = [...new Set(arr)]
    // 判断某元素是否在集合中
    const set = new Set(arr)
    const has = set.has(3)
    // 求交集
    const set2 = new Set([2, 3])
    const set3 = new Set([...set].filter(item => set2.has(item)))
----------------------------------------------------------------------------------------------
// 字典是什么？
1. 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储
2. ES6 中有字典 Map
3. 字典的常用操作：
    键值对的增删改查
----------------------------------------------------------------------------------------------
// 树是什么？
1. 一种分层数据的抽象模型
2. 前端工作中常见的树包括：
    DOM树、级联选择、树形控件
3. js 中没有树，但是可以用 Object 和 Array 构建树
4. 树的常用操作：
    深度、广度优先遍历、先中后序遍历
5. 深度优先遍历：尽可能深的搜索树的分支 // 递归，适用于遍历深度嵌套的 json 串
    口诀：
      访问根节点
      对根节点的 children 挨个进行深度优先遍历
    tree:
        a——1
          b——2
            d——3
            e——4
          c——5
            f——6
            g——7
    例子：
      const dfs = root => {
        console.log(root.val)
        root.children.forEach(dfs)
      }
      dfs(tree)
6. 广度优先遍历：先访问离根节点最近的节点
    口诀：
      新建一个队列，把根节点入队
      把队头出队并访问
      把队头的 children 挨个入队
      重复第二、第三步骤，直到队列为空
    tree:
        a——1
          b——2
            d——4
            e——5
          c——3
            f——6
            g——7
    例子：
      const bfs = root => {
        const q = [root]
        while(q.length > 0) {
          const n = q.shift()
          console.log(n.val)
          n.children.forEach(child => {
            q.push(child)
          })
        }
      }
      bfs(tree)
----------------------------------------------------------------------------------------------
// 二叉树是什么？
// 二叉树的先中后序遍历
1. 树中每个节点最多只能有两个子节点
2. 在 js 中通常用 Object 来模拟二叉树
3. 先序遍历：// 先左后右
    口诀：
      访问根节点
      对根节点的左子树进行先序遍历
      对根节点的右子树进行先序遍历
    tree:
            1
        2       6
      3   4      7
        5
    例子1：// 递归版
      const preoeder = root => {
        if (!root) { return }
        console.log(root.val)
        preoeder(root.left)
        preoeder(root.right)
      }
      preoeder(tree)
    例子2：// 非递归版
      const preoeder = root => {
        if (!root) { return }
        const stack = [root]
        while(stack.length) {
          const n = stack.pop()
          console.log(n.val)
          if (n.right) { stack.push(n.right) }
          if (n.left) { stack.push(n.left) }
        }
      }
      preoeder(tree)
4. 中序遍历
    口诀：
      对根节点的左子树进行中序遍历
      访问根节点
      对根节点的右子树进行中序遍历
    tree:
            5
        2       6
      1   4      7
        3
    例子1：// 递归版
      const inorder = root => {
        if (!root) { return }
        inorder(root.left)
        console.log(root.val)
        inorder(root.right)
      }
      inorder(tree)
    例子2：// 非递归版
      const inorder = root => {
        if (!root) { return }
        const satck = []
        let p = root
        while(stack.length || p) {
          while(p) {
            stack.push(p)
            p = p.left
          }
          const n = stack.pop()
          console.log(n.val)
          p = n.right
        }
      }
      inorder(tree)
4. 后序遍历：
    口诀：
      对根节点的左子树进行后序遍历
      对根节点的右子树进行后序遍历
      访问根节点
    tree:
            7
        4       6
      1   3      5
        2
    例子1：// 递归版
      const postorder = root => {
        if (!root) { return }
        postorder(root.left)
        postorder(root.right)
        console.log(root.val)
      }
      postorder(tree)
    例子2：// 非递归版
      const postorder = root => {
        if (!root) { return }
        const outputStack = []
        const stack = [root]
        while(stack.length) {
          const n = stack.pop()
          outputStack.push(n)
          if (n.left) { stack.push(n.left) }
          if (n.right) { stack.push(n.right) }
        }
        while(outputStack.length) {
          const n = outputStack.pop()
          console.log(n.val)
        }
      }
      postorder(tree)
----------------------------------------------------------------------------------------------
// 图是什么？
1. 图是网络结构的抽象模型，是一组由边连接的节点
2. 图可以表示任何二元关系，比如道路、航班
3. js 中没有图，可以用 Object 和 Array 构建图
4. 图的表示法：邻接矩阵、邻接表、关联矩阵
   邻接表：// 表示 A 连接 B，B 连接 C 和 D ...
    {
      A: ['B'],
      B: ['C', 'D'],
      C: ['E'],
      D: ['A'],
      E: ['D']
    }
5. 图的深度优先遍历：尽可能深的搜索图的分支
    1. 访问根节点
    2. 对根节点的没访问过的相邻节点挨个进行深度优先遍历
    const graph = {
      0: [1, 2],
      1: [2],
      2: [0, 3],
      3: [3]
    }
    const visited = new Set()
    const dfs = n => {
      console.log(n)
      visited.add(n)
      graph[n].forEach(c => {
        if (!visited.has(c)) {
          dfs(c)
        }
      })
    }
    dfs(2)
6. 图的广度优先遍历：先访问离根节点最近的节点
    1. 新建一个队列，把根节点入队
    2. 把队头出队并访问
    3. 把队头的没访问过的相邻节点入队
    4. 重复第二、三步，直到队列为空
    const graph = {
      0: [1, 2],
      1: [2],
      2: [0, 3],
      3: [3]
    }
    const visited = new Set()
    visited.add(2)
    const q = [2]
    while(q.length) {
      const n = q.shift()
      console.log(n)
      graph[n].forEach(c => {
        if (!visited.has(c)) {
          q.push(c)
          visited.add(c)
        }
      })
    }
----------------------------------------------------------------------------------------------
// 堆是什么？
1. 堆是一种特殊的完全二叉树
2. 完全二叉树：每层节点都完全填满，在最后一节点如果不是满的，则只缺少右边的若干节点
3. 特殊的地方：所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点
4. js 中通常用数组表示堆
5. 左侧子节点的位置是 2 * index + 1
6. 右侧子节点的位置是 2 * index + 2
7. 父节点位置是 (index - 1) / 2
8. 堆的应用：
    1. 堆能高效、快速的找出最大值和最小值，时间复杂度是 O(1)
    2. 找出第 K 个最大（小）元素
        构建一个最小堆，并将元素依次插入堆中
        当堆的容量超过 K，就删除堆顶
        插入结束后，堆顶就是第 K 个最大元素