前言

大环境下失业2个月, 重温下JS数据结构与算法, 后续会把前端常考算法梳理下

提升算法思维：如：贪心、二分、动态规划等
常见数据结构

算法复杂度

程序执行时需要的计算量和内存空间

O(1) 一次就够
O(n)和传输的数据量一样(数量级) > 输入量是100,计算量是100次
O(n^2)数据量的平分(数量级) > 输入量是100,计算量是1万次
O(logn)数据量的对数(数量级) > 输入量是100 ,计算量是10次
O(n*logn)数据量 * 数据量的对数(数量级)

前端开发: 重时间,轻空间

时间复杂度

程序执行时需要的计算量（CPU）

// O(1) 只执行一次
let i = 0
i +1 = 1

// O(n) for循环执行n次
for(let i = 0; i < n; i+=1) {
    console.log(i)
}

// O(n) * O(n) = 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) 算2^n次方，对数，输入100，计算量是10
let i = 1
whild(i < n) {
    console.log(i)
    i *= 2
}

空间复杂度

程序执行时需要的内存空间

// O(1) 只声明单个变量
let i = 0
i +1 = 1

// O(n) 占用了n个内存单元
const list = []
for(let i = 0; i < n; i+=1) {
    list.push(i)
}

什么是栈

栈是一种遵从先进后出原则的有序集合。新添加的或是待删除的元素都保存在栈的末尾。我们称作栈顶，而另一端我们称作栈底。

Array实现栈的方法

入栈 arr.push()
出栈 arr.pop()
访问栈顶 arr[arr.length – 1]

const stack = [1,2]
stack.push(1)
stack.pop()

栈的应用场景

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

栈的相关算法

1.有效括号

题目描述

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例:

输入： s = "()[]{}"
输出： true

题解

遇到左括号 { ( [ 就压栈
遇到右括号就判断栈顶，匹配则出栈，一个不匹配就为false
最后判断length是否为0

function isMath(l,r) {
    if(l === '{' && r ==='}') return true
    if(l === '[' && r ===']') return true
    if(l === '(' && r ===')') return true
    return false
}
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const length = s.length
    const leftBracket = "([{"
    const rightBracket = "}])"
    const stack = []
    for(let i = 0; i < length;i++) {
        const val = s[i]
        if(leftBracket.includes(val)) {
            stack.push(val)
        } else if(rightBracket.includes(val)) {
            const stackVal = stack[stack.length - 1]
            if(isMath(stackVal,val)) {
                 stack.pop()
            } else {
                return false
            }
        } 
    }
    return stack.length === 0
};

leetcode链接 20.有效括号

2.二叉树的前序遍历

概念:

二叉树其实就是一个数的结构

题目描述

给你二叉树的根节点 root ，返回它节点前序遍历的值。

示例:

const bst = {
    value: 5,
    left: {
        value: 3,
        left: {
            value: 2,
            left: null,
            right: null
        },
        right: {
            value: 4,
            left: null,
            right: null,
        }
    },
    right: {
        value: 7,
        left: {
            value: 6,
            left: null,
            right: null
        },
        right: {
            value: 8,
            left: null,
            right: null
        }
    }
}

输出: [5,3,2,4,7,6,8]

题解

前序遍历 (栈实现, 当然也可以用递归实现)

根节点先出栈,访问根节点的value值
右节点入栈,因为用前序遍历,栈是先进后出,所以要先访问的是左节点
左节点入栈,判断栈的长度,来访问value值

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const res = []
    const stack = []
    root && stack.push(root)
    
    while(stack.length > 0) {
        let node = stack.pop()
        if(node.val) res.push(node.val)
        if(node.right) stack.push(node.right)
        if(node.left)  stack.push(node.left)
    }
    return res
};

leetcode144.二叉树前序遍历

文章版权归作者所有，未经允许请勿转载。

THE END