• 一、数据结构与算法简介
  • 1、理论
  • 2、刷题
  • 3、数据结构与算法
• 二、时间空间复杂度计算
  • 1、时间复杂度计算
  • 2、空间复杂度计算
• 三、栈
  • 1、栈简介
  • 2、栈的应用场景
  • 3、力扣解题（20. 有效的括号）
  • 4、力扣解题（144. 二叉树的前序遍历）
• 四、队列
  • 1、队列简介
  • 2、队列的应用场景
  • 3、力扣解题（933. 最近的请求次数）

一、数据结构与算法简介

1、理论

* 数据结构：栈、队列、集合、链表、字典、树、图、堆
* 进阶算法：冒泡算法、选择算法、插入算法、归并算法、快速算法、顺序算法、二分搜索
* 算法设计思想：分而治之、动态规则、贪心、回溯
* 重点关注：数据结构与算法的特点、应用场景、js实现、时间/空间复杂度

2、刷题

* 刷题网站：leetcode
* 重点关注：通用套路、时间/空间复杂度分析和优化

3、数据结构与算法

* 是什么：
    - 数据结构：计算机存储、组织数据的方式
    - 算法：一系列解决问题的清晰指令
* 程序：数据结构 + 算法
* 关系：数据结构为算法提供服务，算法围绕数据结构操作

二、时间空间复杂度计算

1、时间复杂度计算

• 是什么

* 一个函数，用大O表示，比如O(1)、O(n)、O(logN)...
* 定性描述该算法的运行时间

• O(1)

let i = 0
i += 1

• O(n)

// O(1) + O(n) = O(n)
for (let i = 0; i < n; i++) {
    console.log(i)
}

• O(n^2)

// O(n) * O(n) = O(n^2)
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        console.log(i, j)
    }
}

• O(logN)

// 如果a的x次方等于N，其中a>0且a不等于1，那么数x叫做以a为底N的对数
// 2的x次方等于N，x等于logN（计算机中2会省略不写，数学中2不可以省略）
let i = 1
while (i < n) {
    console.log(i)
    i *= 2
}

2、空间复杂度计算

• 是什么

* 一个函数，用大O表示，比如O(1)、O(n)、O(n^2)...
* 算法在运行过程中临时占用存储空间大小的量度

• O(1)

let i = 0
i += 1

• O(n)

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

• 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、栈简介

// 1、栈是一种后进先出的数据结构
// 2、栈常用操作：push、pop、stack[stack.length-1]
const stack = []
stack.push(1)
stack.push(2)
const item1 = stack.pop()
const item2 = stack.pop()

2、栈的应用场景

* 十进制转二进制
* 判断字符串的括号是否有效
* 函数调用堆栈

3、力扣解题（20. 有效的括号）

var isValid = function (s) {
    const lp = "([{"
    if (s.length % 2 === 1 || lp.indexOf(s[0]) === -1) {
        return false
    }
    const stack = []
    const rp = ")]}"
    for (let i = 0; i < s.length; i++) {
        if (lp.indexOf(s[i]) !== -1) {
            stack.push(s[i])
        } else {
            const top = stack.pop()
            if (lp.indexOf(top) !== rp.indexOf(s[i])) {
                return false
            }
        }
    }
    return !stack.length
};

4、力扣解题（144. 二叉树的前序遍历）

// 二叉树前序：根-左-右
// 二叉树中序：左-根-右
// 二叉树后序：左-右-根
var preorderTraversal = function (root) {
    let arr = []
    let preorder = function (node, arr) {
        if (node === null) return arr
        arr.push(node.val)
        preorder(node.left, arr)
        preorder(node.right, arr)
    }
    preorder(root, arr)
    return arr
};

四、队列

1、队列简介

// 1、队列是一种先进先出的数据结构
const queue = []
queue.push(1)
queue.push(2)
const item1 = queue.shift()
const item2 = queue.shift()

2、队列的应用场景

* 食堂排队打饭
* js异步中的任务队列
* 计算最近请求次数

3、力扣解题（933. 最近的请求次数）