写在前面

知识点：

  • 数组
  • 栈
  • 队列
  • 链表
  • 树
  • 空间/时间复杂度

数组

  1. 创建数组 
const newArr = new Array(7).fill(1);

  1. 遍历

    for循环（优先推荐）

    let i;
for(i=0;i<newArr.length;i++) {
    console.log(arr[i], i);
}

forEach

   array.forEach((item, index) => {
           console.log(item, index);
       })

map

   const newArr = arr.map((item, index) => {
       // 输出数组的元素值，输出当前索引
       console.log(item, index)
       // 在当前元素值的基础上加1
       return item+1;
   })

  1. fill 注意事项

    const arr =(new Array(7)).fill([]);
arr[0][0] = 1;//会修改每一部分数值，原因参考栈内存，用fill赋值的是地址，且给每一个对象都赋值了同一地址

    因此初始化二维数组推荐方法：

    const len = arr.length;
let i;
for(i=0;i<len;i++) {
    // 将数组的每一个坑位初始化为数组
    arr[i] = [];
}

    数组访问

    // 缓存外部数组的长度
const outerLen = arr.length;
let i;
for(i=0;i<outerLen;i++) {
    // 缓存内部数组的长度
    const innerLen = arr[i].length;
    let j;
    for(j=0;j<innerLen;j++) {
        // 输出数组的值，输出数组的索引
        console.log(arr[i][j],i,j);
    }
}

栈

复习数组CRUD

增：unshift push splice

删：shift pop splice

栈（Stack）：一种后进先出(LIFO，Last In First Out)的数据结构。

(栈顶就是数组末尾元素、出栈就是拿出数组末尾元素)

现实案例：冰箱放、取冰淇淋

  • 特点
    • 只允许从尾部添加元素 (push )
    • 只允许从尾部取出元素 (pop )

队列

队列（Queue）：一种先进先出（FIFO，First In First Out）的数据结构。

（队列元素出队时，我们关心的则是队头元素（数组的第一个元素））

现实案例：排队购物，进/出

  • 特点
    • 只允许从尾部添加元素 (push )
    • 只允许从头部取出元素 (shift)

链表

基础

链表：与数组相似，有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）。不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的，而数组一般对应着一段连续的内存。

关联：每一个结点的结构都包括了两部分的内容：数据域和指针域（以嵌套的对象的形式来实现的）

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

链表节点创建

function ListNode(val) {
    this.val=val;
    this.next=null;
}

const node = ListNode(1);
node.next = ListNode(2);

链表节点添加

//改变一个 next 指针就行

链表节点插入

// 如果目标结点本来不存在，那么记得手动创建
const node3 = new ListNode(3)     
// 把node3的 next 指针指向 node2（即 node1.next）
node3.next = node1.next
// 把node1的 next 指针指向 node3
node1.next = node3

链表的删除

删除的标准是：在链表的遍历过程中，无法再遍历到某个结点的存在。按照这个标准，要想遍历不到 node3，我们直接让它的前驱结点 node1 的 next 指针跳过它、指向 node3 的后继即可

TIPS:重点不是定位目标结点，而是定位目标结点的前驱结点

node1.next = node3.next 

// 利用 node1 可以定位到 node3
const target = node1.next  
node1.next = target.next

链表遍历

// 记录目标结点的位置
const index = 10;
// 设一个游标指向链表第一个结点，从第一个结点开始遍历
let node = head; 
// 反复遍历到第10个结点为止
let i;
for (i=0;i<index&&node;i++) {
    node = node.next
}

链表和数组的辨析

在数组中，删/增会有数组塌陷和膨胀，而链表没有

TIPS：

在JS中，纯数字数组，那么对应的确实是连续内存，但如果我们定义了不同类型的元素，此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。

因此，JS 数组未必是真正的数组，而真正数组是指存储在连续的内存空间里

优势 劣势
链表 高效增/删 低效查找
数组 低效增/删 高效查找

树

树的关键特性和重点概念

  • 树的层次计算规则：根在第一层，以此类推向上+1；
  • 结点和树的“高度”计算规则：叶子结点高度记为1，每向上一层高度就加1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”；
  • “度”：一个结点开叉出去多少个子树，被记为结点的“度”；
  • “叶子结点”：度为0的结点。

二叉树

满足以下要求的树被称为二叉树：

  • 它可以没有根结点，作为一棵空树存在
  • 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

TIPS：

二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。

// 二叉树结点的构造函数
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
const node  = new TreeNode(1)

二叉树实现方式

递归（先中后）

迭代（层次）

递归

一个函数反复调用它自己的时候

根节点的遍历排位来规定先中后

根、左二叉树、右二叉树（先）

...

案例（手写）

const ary = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }

    },
    right: {
        val: 'C',
        left: {
            val: 'G'
        },
        right: {
            val: 'F'
        }
    }
}
console.log(ary);
//先序：ABDECGF
//中：DBEAGCF
//后：DEBGFCA

image-20201116094415298

递归函数的编写要点

  • 递归式

    每一次重复的内容是什么。如：先序遍历，每一次重复 根结点 -> 左子树 -> 右子树

  • 递归边界

    什么时候停。目标树为空，return

// 先序遍历 根->左->右
function preOrder(root) {
    if (!root) {
        return;
    }
    console.log('当前遍历为',root.val);
    preOrder(root.left);
    preOrder(root.right);
}
preOrder(ary); 

// 中序遍历 最左->根->最右
function preOrder(root) {
    if (!root) {
        return;
    }
    preOrder(root.left);
    console.log('当前遍历为',root.val);
    preOrder(root.right);
}
preOrder(ary); 


// 后序遍历 先访问左子树，再访问右子树，最后访问根结点
//其实就是如果有左右子树，访问完再访问根节点
function preOrder(root) {
    if (!root) {
        return;
    }
    preOrder(root.left);
    preOrder(root.right);
    console.log('当前遍历为',root.val);
}
preOrder(ary);

以能快速“默写”为标准！！！！！

复杂度

时间复杂度

算法的时间复杂度，它反映的不是算法的逻辑代码到底被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个变化趋势。

image-20201115125124214

我们可以看出，规模为 n 的一维数组遍历时，最内层的循环会执行 n 次，其对应的时间复杂度是 O(n)；规模为 n*n 的二维数组遍历时，最内层的循环会执行 n*n 次，其对应的时间复杂度是 O(n^2)。

以此类推，规模为 n*m 的二维数组最内层循环会执行 n*m 次，其对应的时间复杂度就是 O(n*m)；规模为 n*n*n 的三维数组最内层循环会执行 n^3 次，因此其对应的时间复杂度就表示为 O(n^3)。

function fn(arr) {
    const len = arr.length  

    for(let i=1;i<len;i=i*2) {
        console.log(arr[i])
    }
}

假设 i 在以 i=i*2的规则递增了 x 次之后，i<n 开始不成立（反过来说也就是 i>=n 成立）。那么此时我们要计算的其实就是这样一个数学方程：

2^x >= n

x解出来，就是要大于等于以 2 为底数的 n 的对数：

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。和时间复杂度相似，它是内存增长的趋势。

  • 在常数运算中，整个 traverse 函数对内存的占用量是恒定的，它对应的空间复杂度就是 O(1)

  • 这个 arr最终的大小是由输入的 n 的大小决定的，它会随着 n 的增大而增大、呈一个线性关系。因此这个算法的空间复杂度就是 O(n)

  • 假如需要初始化的是一个规模为 n*n 的数组，那么它的空间复杂度就是 O(n^2) 啦