canicode.cn

# JavaScript 版数据结构与算法

# 一、数据结构与算法简介

  1. 数据结构：计算机存储、组织数据的方式
  2. 算法：一系列解决问题的清晰指令
  3. 程序 = 数据结构 + 算法
  4. 数据结构为算法提供服务，算法围绕数据结构操作

# 二、时间/空间复杂度计算

  • 时间复杂度：
    1. 一个函数，用大 O 描述，比如 O(1)、O(n)、O(logN)......
    2. 定性描述该算法的运行时间
    // O(1)
let i = 0
i += 1
// O(n)
for (let i = 0; i < n; i += 1) {
    console.log(i)
}
// O(n^2)
for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
        console.log(i, j)
    }
}
// O(logN)
let i = 1
while (i < n) {
    console.log(i)
    i *= 2
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
  • 空间复杂度：
    1. 一个函数，用大 O 描述，比如 O(1)、O(n)、O(n^2)......
    2. 算法在运行过程中临时占用存储空间大小的量度
    // O(1)
let i = 0
i += 1
// O(n)
const list = []
for (let i = 0; i < n; i += 1) {
    list.push(i)
}
// O(n^2)
const matrix = []
for (let i = 0; i < n; i += 1) {
    matrix.push([])
    for (let j = 0; j < n; j += 1) {
        matrix[i].push(j)
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

# 三、数据结构：栈

  • 一个后进先出的数据结构，Javascript 没有栈，但是可以用 Array 数组实现栈的所有功能
    1. 入栈：push，出栈：pop
    const stack = []
stack.push(1)
stack.push(2)
console.log(stack) // 控制台打印： [1, 2]
const item1 = stack.pop()
const item2 = stack.pop()
console.log(stack, item1, item2) // 控制台打印：[] 2 1
    1
    2
    3
    4
    5
    6
    7
    1. 应用场景：十进制转二进制、判断字符串的括号是否有效、函数调用堆栈
    // 1. 十进制转二进制
// 对 35 % 2 取模后出来的余数 110001 要排到前面 100011
// 把余数依次 push 入栈，然后再依次 pop 出栈，就可以实现余数倒序输出
function transform(val) {
    let stack = ''
    let merchant = 0
    while (val > 0) {
        merchant = parseInt(val / 2)
        stack = (val % 2) + stack
        val = merchant
    }
    return parseInt(stack)
}
console.log(transform(35)) // 控制台打印：100011
// 2. 判断字符串的括号是否有效
// ((())()) 越靠后对左括号，对应的右括号越靠前
// 左括号入栈，右括号出栈，最后栈空来就是合法的
function isValid(s) {
    if (s.length % 2 === 1) return false
    const stack = []
    for (let i = 0; i < s.length; i += 1) {
        const c = s[i]
        if (c === '(') {
            stack.push(c)
        } else {
            const t = stack[stack.length - 1]
            if (t === '(' && c === ')') {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length === 0
}
console.log(isValid('((())())'))
// 3. 函数调用堆栈
// 函数调用函数（高阶函数），最后调用的函数，最先执行
// 4. 二叉树的前序遍历
// 输入：[1,null,2,3]
// 1
//   \
//    2
//   /
// 3
// 输出：[1,2,3]
function TreeNode(val) {
    this.val = val
    this.left = this.right = null
}
function preorderTraversal(root) {
    const res = []
    const stack = []
    if (root) stack.push(root)
    while (stack.length) {
        const n = stack.pop()
        res.push(n.val)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
    return res
}
// 5. 请用 ES6 的 class，封装一个 Stack 类，包括 push、pop、peek 方法
class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class Stack {
    constructor() {
        this.top = null
    }
    push(element) {
        const node = new Node(element)
        node.next = this.top
        this.top = node
    }
    pop() {
        this.top = this.top && this.top.next
    }
    peek() {
        return this.top && this.top.element
    }
}
const stack = new Stack()
stack.push(1)
stack.push(2)
stack.pop()
console.log(stack.peek()) // 控制台打印： 1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90

# 四、数据结构：队列

  • 一个先进先出的数据结构
  • JavaScript 没有队列，但可以用 Array 实现队列的所有功能
    1. 入队：push，出队：shift
    // 1. 简单示例
const queue = []
queue.push(1)
queue.push(2)
const item1 = queue.shift() // 移除数组的第一个元素，并且返回它
const item2 = queue.shift()
console.log(item1, item2) // 控制台打印：1 2
// 2. 食堂排队打饭
// 3. JS异步中的任务队列
// 4. 计算最近请求次数，leetcode：933题目
var RecentCounter = function() {
    this.q = []
}
RecentCounter.prototype.ping = function(t) {
    this.q.push(t)
    while (this.q[0] < t - 3000) {
        this.q.shift()
    }
    return this.q.length
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

# 五、数据结构：链表

  • 多个元素组成的列表
  • 元素存储不连续，用 next 指针连在一起
  • JavaScript 没有链表，但是可以用 Object 模拟链表
    1. 数组：增删非首位元素时往往需要移动元素
    2. 链表：增删非首位元素，不需要移动元素，只需要更改 next 的指向即可
    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) // 控制台打印： a b c
    p = p.next
}
// 插入
const d = { d: 'd' }
b.next = d
d.next = c
console.log(a)
// 删除
b.next = c
// 1. 删除链表中的节点
// head = [4,5,1,9], node = 5
function ListNode(val) {
    this.val = val
    this.next = null
}
function deletNode(node) {
    node.val = node.next.val
    node.next = node.next.next
}
// 2. 反转链表
// 输入：1->2->3->4->5->null
// 输出：5->4->3->2->1->null
function ListNode(val) {
    this.val = val
    this.next = null
}
function reverseList(head) {
    let p1 = head
    let p2 = null
    while (p1) {
        const tmp = p1.next
        p1.next = p2
        p2 = p1
        p1 = tmp
    }
    return p2
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46

# 六、数据结构：集合

# 七、数据结构：字典

# 八、数据结构：树

# 九、数据结构：图

# 十、数据结构：堆

# 十一、算法设计思想：搜索排序

# 十二、算法设计思想：分而治之

# 十三、算法设计思想：动态规划

# 十四、算法设计思想：贪心算法

# 十五、算法设计思想：回溯算法

Last Updated: 2023/9/18 06:50:08

算法结构 →