web全栈体系

外观

目录

数据结构与算法 ​

  • 数据结构：计算机存储、组织数据的方式，就像锅碗瓢盆
  • 算法：一系列解决问题的清晰指令，就像食谱
  • 程序 = 数据结构 + 算法
  • 数据结构为算法提供服务，算法围绕数据结构操作

时间复杂度 ​

  • 一个函数，使用大O表示，比如O(1)、O(2)、 O(n)...
  • 作用：用来描述该算法的运行时间

**O(1)：**平铺直叙的执行，没有任何循环

javascript
let i = 0
    i += 1

O(n)： 如果是 O(1) + O(n) 则还是 O(n)

javascript
for (let i = 0; i < n; i++) {
      console.log(i) // 随着n增大，for循环里面代码执行次数也会增大
    }

O(n^2)： O(n) * O(n), 双层循环

javascript
for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        console.log(i, j)
      }
    }

O(logn)： 求 log 以 2 为底的多少次方等于 n（使用二分法是一个典型例子）

javascript
// 此例子求2的多少次方会大于i，然后就会结束循环
    let i = 1
    while (i < n) {
      console.log(i)
      i *= 2
    }

**O(n*logn)：**嵌套循环，一层是普通循环，一层有二分算法。例如：快速排序算法

空间复杂度 ​

  • 一个函数，用大O表示，比如 0(1)、O(n)、O(n^2）..
  • 作用：描述算法在运行过程中临时占用存储空间大小

O(1)： 单个变量

javascript
let i = 0
    i += 1

O(n)： 声明一个数组， 添加 n 个值， 相当于占用了 n 个空间单元

javascript
const arr = []
    for (let i = 0; i < n; i++) {
      arr.push(i)
    }

O(n^2)： 类似一个矩阵（二维数组）的概念

javascript
const arr = []
    for (let i = 0; i < n; i++) {
      arr.push([])
      for (let j = 0; j < n; j++) {
        arr[i].push(j)
      }
    }

栈的实现 ​

  • 栈是一种后进先出的有序数据结构，可以想象公交站，后进来的在门口，反而可以最先出来
  • 往后添加新元素的一端称为栈顶，另一端称为栈底
  • JavaScript中没有栈，但可以用 Array 实现栈的所有功能
  • 栈常用操作：push、pop、stack[stack.length-1]
javascript
const stack = [];

stack.push(1); // 入栈
stack.push(2); // 入栈

const item1 = stack.pop();  //出栈的元素
const item2 = stack.pop();  //出栈的元素

手写模拟栈

javascript
class Stack {
  constructor() {
    // 存储栈的数据
    this.data = {};
    // 记录栈的数据个数（相当于数组的 length）
    this.count = 0;
  }
  // 入栈方法
  push(item) {
    // 计数方式
    this.data[this.count] = item;
    // 入栈后，count 自增
    this.count++;
  }
  // 出栈方法
  pop() {
    // 出栈的前提是栈中存在元素，应先行检测
    if (this.isEmpty()) {
      console.log("栈为空！");
      return;
    }
    // return this.data.pop()
    // 方式2：计数方式
    const temp = this.data[this.count - 1];
    delete this.data[--this.count];
    return temp;
  }
  // isEmpty() 检测栈是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 获取栈顶值
  top() {
    if (this.isEmpty()) {
      console.log("栈为空！");
      return;
    }
    return this.data[this.count - 1];
  }
  // size() 获取元素个数
  size() {
    return this.count;
  }
  // clear() 清空栈
  clear() {
    this.data = {};
    this.count = 0;
  }
}

const s = new Stack();
s.push("a");
s.push("b");
s.push("c");

栈的应用场景 ​

  • 需要后进先出的场景
  • 比如:十进制转二进制、判断字符串的括号是否有效、函数调用堆栈...

1、LeetCode: 20.有效括号 ​

解题思路：

  • 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前
  • 满足后进先出，考虑用栈

image.png

解题步骤：

  • 新建一个栈
  • 扫描字符串，遇左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法
  • 最后栈空了就合法，否则不合法
javascript
// 时间复杂度O(n) n为s的length
// 空间复杂度O(n)
const isValid = (s) => {
  // 不是偶数，直接返回
  if(s.length % 2 !== 0) return false
  const stack = [];
  for(let i = 0; i < s.length; i++) {
      const item = s[i];
      const leftBrackets = ["(", "{", "["]
      // 如果是左括号就入栈
      if(leftBrackets.includes(item)) {
          stack.push(item)
      }else {
          // 拿到最后栈顶元素即最后一个左括号
          const top = stack[stack.length - 1];
          // 如果是右括号和左括号能匹配就出栈
          if((item === ")" && top === "(") || (item === "}" && top === "{") || (item === "]" && top === "[")) {
              stack.pop()
          }else {
              return false
          }
      }
  }
  return stack.length === 0
}

2、十进制转二进制 ​

  • 后出来的余数反而要排到前面
  • 把余数依次入栈，然后再出栈
  • 就可以实现余数倒序输出
javascript
// 时间复杂度 O(n) n为二进制的长度
// 空间复杂度 O(n) n为二进制的长度
const dec2bin = (dec) => {
  // 创建一个字符串
  let res = "";
  // 创建一个栈
  let stack = []
  // 遍历数字 如果大于0 就可以继续转换2进制
  while (dec > 0) {
    // 将数字的余数入栈
    stack.push(dec % 2)
    // 除以2
    dec = Math.floor(dec / 2)
  }
  // 取出栈中的数字
  while (stack.length) {
    res += stack.pop()
  }
  // 返回这个字符串
  return res
};

3、JS中的函数调用堆栈 ​

image.png

  • callStack首先会有个整体的匿名函数执行 Javascript 代码
  • 先入栈 func1  接着会进入 func2  func3
  • 然后出栈 fun3  fun2  fun1
  • JS解释器函数调用堆栈符合后进先出

4、旋转数组 ​

  • 输入 [1, 2, 3, 4, 5, 6, 7]和 `key = 3``
  • 输出 [5, 6, 7, 1, 2, 3, 4]

实现思路一：

  • 将 k 后面的元素，挨个 pop 然后 unshift 到数组前面
    • 看代码时间复杂度是 O(n)，但数组是有序结构 unshift 本身就是 O(n) 复杂度，所以实际复杂度是 O(n^2)

实现思路二：

  • 将 k 后面的所有元素拿出来作为 part1
  • 将 k 前面的所有元素拿出来作为 part2
  • 返回 part1.concat(part2)
    • slice 和 concat 不会修改原数组，而数组是有序结构，复杂度是 O(1)
javascript
function rotate(arr, k) {
  const length = arr.length;
  if (!length) return true;
  const step = Math.abs(k % length);
  const rotateBeforeArr = arr.slice(-step);
  const otherArr = arr.slice(0, length - step);
  return rotateBeforeArr.concat(otherArr);
}

console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3)); // [5, 6, 7, 1, 2, 3, 4]

May all encounters not be in vain