什么是复杂度

时间复杂度-程序执行时需要的计算量（CPU）

空间复杂度-程序执行时需要的内存空间

将一个数组旋转K步

function rotate1(arr, k) {
    const length = arr.length
    if (!k || length === 0) return arr
    const step = Math.abs(k % length) // abs 取绝对值
    for (let i = 0; i < step; i++) {
        const n = arr.pop()
        if (n != null) {
            arr.unshift(n) //数组是一个有序结构，unshift操作非常慢 O(n)       
        }
    }
    return arr
}
function rotate2(arr, k) {
    const length = arr.length
    if (!k || length === 0) return arr
    const step = Math.abs(k % length) // abs 取绝对值
    const part1 = arr.slice(-step) // O(1)
    const part2 = arr.slice(0, length - step)
    const part3 = part1.concat(part2)
    return part3
}
// 功能测试
// const arr = [1, 2, 3, 4, 5, 6, 7]
// const arr1 = rotate2(arr, 3)
// console.info(arr1);
// 性能测试
const arr1 = []
for (let i = 1; i < 10 * 10000; i++) {
    arr1.push(i)
}
console.time('rotate1')
rotate1(arr1, 9 * 1000)
console.timeEnd('rotate1') //152.12ms O(n^2)
const arr2 = []
for (let i = 1; i < 10 * 10000; i++) {
    arr2.push(i)
}
console.time('rotate2')
rotate2(arr2, 9 * 1000)
console.timeEnd('rotate2') //0.41ms O(1)

判断字符串是否括号匹配

/*
 *
 *判断是否括号匹配
 */
// 判断左右括号是否匹配
function isMatch(left, right) {
    if (left === "{" && right === "}") return true
    if (left === "[" && right === "]") return true
    if (left === "(" && right === ")") return true
    return false
}
function matchBracket(str) {
    const length = str.length
    if (length === 0) return true
    const stack = []
    const leftSymbols = '{[('
    const rightSymbols = ')]}'
    for (let i = 0; i < length; i++) {
        const s = str[i]
        if (leftSymbols.includes(s)) {
            //左括号，压栈
            stack.push(s)
        } else if (rightSymbols.includes(s)) {
            //右括号，判断栈顶（是否出栈）
            const top = stack[stack.length - 1]
            if (isMatch(top, s)) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length === 0
}
// 功能测试
const str = '{a[d((s)c]d}a'
console.info(123, matchBracket(str))

时间复杂度：O(n)
空间复杂度：O(n)

栈