• 【算法】算法题总结

    算法题总结

    数组

    • 二分 O(n) => O(log n)
    left = 0; right = len-1
while(left <= right) {
    mid = left + Math.floor(left+right)
    if(target < mid) {
        right = mid-1
    }else if(target > mid) {
        left = mid+1
    }else return mid
}
return -1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 双指针 O(n^2) => O(n)

    (通过一个快指针和慢指针在一个for循环下完成两个for循环的工作)

    slow = 0; fast = 0;
while(fast < len) {
    if(...){
       slow ...
    }
    fast++
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 滑动窗口 O(n^2) => O(n)
    left = 0; right = 0; res // 子数组
while(right < len) {
    ...
    // 窗口滑动，左闭右开
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 组成螺旋矩阵 59 四个规则不可复用

    哈希表

    快速判断一个元素是否出现集合里（三数之和，四数之和 固定一个值用双指针）

    字符串

    方法：常用双指针

    反转字符串，翻转单词，重复子串，KMP ，前缀表（next数组）

    NOTICE：字符串不能通过查询的方式改变

    let str = '123'
str[0] = 9
str	// '123' 没有变！需要重新赋值

    • 1
    • 2
    • 3

    字符串找字符串

    优化用 KMP（https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC）

    当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。（用 next数组 记录已经匹配的文本内容）

    链表

    • 种类

      单链表，双链表，循环链表

    • 五大基本操作（用虚拟头节点）

      查找第i个，链表前插入，链表后插入，第i个前插入，删除第i个

    • 题型

      设计链表，翻转链表，链表相交（快慢指针），环形链表

    • 定义

    function ListNode(val, next) {
    this.val = val===undefined ? 0 : val
    this.next = next===undefined ? null : next
}

    • 1
    • 2
    • 3
    • 4

    反转链表

    var reverseList = function(head) {
    if(!head || !head.next) return head
    let pre = null, cur = head, temp = null // 要加一个 temp 保存 cur.next
    while(cur) {
        temp = cur.next
        cur.next = pre  // 移指针
        // 向下走
        pre = cur
        cur = temp
    }
    return pre  // 注意！pre成了头节点
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    两两交换链表节点

    // 三步骤(!写的时候顺序反过来)：temp -> cur, cur -> pre, pre -> cur.next (四个节点参与), -> 用 next= 替换
var swapPairs = function(head) {
    let data = new ListNode(0, head), temp = data
    while(temp.next && temp.next.next) {
        let pre = temp.next, cur = pre.next
        pre.next = cur.next
        cur.next = pre
        temp.next = cur
        temp = pre
    }
    return data.next    // 返回 head 会少一位
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    栈和队列

    有效的括号

    []{}()

    • 栈

      题型：括号匹配，字符串去重，逆波兰表达式

    • 队列

      类型：单调队列，优先级队列

    二叉树

    层序遍历

    // 层序遍历模板 迭代
var levelOrder = function(root, pipe=[], res=[]) {	// 队列维护
    if(!root) return res
    pipe.push(root)	// 放实际节点

    while(pipe.length) {
        // NOTICE: 一定要 len 保存下来
        const len = pipe.length, levelNode = []   // 每层的节点
        for(let i=0; i<len; i++) {
            const node = pipe.shift()	// 放在循环内
            levelNode.push(node.val)
            node.left && pipe.push(node.left)
            node.right && pipe.push(node.right)
        }
        res.push(levelNode)
    }
    return res
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    翻转二叉树

    // 翻转二叉树 递归
var invertTree = function(root) {
    if(!root) return null
    const right = invertTree(root.right)
    const left = invertTree(root.left)	// 左右都递归完，再赋值
    root.left = right
    root.right = left
    return root
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    构造最大二叉树

    // 654构造最大二叉树 [3,2,1,6,0,5] -> TreeNode
var constructMaximumBinaryTree = function(nums) {
    const dfs = (arr) => {
        if(!arr || !arr.length) return null
        const max = Math.max(...arr), index = arr.indexOf(max)
        const node = new TreeNode(max)
        node.left = dfs(arr.slice(0, index))
        node.right = dfs(arr.slice(index+1))
        return node
    }
    return dfs(nums)
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    二叉搜索树

    // 98验证二叉搜索树：中序遍历变成数组，判断是否递增
// 二叉搜索树，中序遍历的数组，单调递增
// 二叉搜索树插入，正常递归遍历，遇到空节点 插入即可

    • 1
    • 2
    • 3
    // 搜索 LCA 最近公共祖先：onLeft && onRight || (onLeft||onRight) && (node.val==p.val/q.val)
// 如果是二叉搜索树，简单些，直接判断 min < val < max || val==min/max && (val < max || val > min)
var lowestCommonAncestor = function(root, p, q, res=null) {
    // 输入：node -> 输出：boolean 是否存在p,q
    const dfs = (head) => { 
        if(!head) return false
        // if(head.val === p.val || head.val === q.val) return head 
        const hasLeft = dfs(head.left), hasRight = dfs(head.right)
        if(hasLeft && hasRight || (hasLeft || hasRight) && (head.val === p.val || head.val === q.val)) res = head
        return hasLeft || hasRight || head.val === q.val || head.val === p.val
    }
    dfs(root)
    return res
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    // 二叉搜索树的插入
var insertIntoBST = function(root, val) {
    // input: node -> output: node/newNode(null)
    const dfs = (head) => {
        if(!head) {
            return new TreeNode(val)
        }
        if(head.val > val) head.left = dfs(head.left)   // 需要赋返回值
        if(head.val < val) head.right = dfs(head.right)
        return head
    }
    return dfs(root)
};

// 二叉搜索树的删除（或普通二叉树的删除）分五种情况 450，被删元素 left right都在时，需要将 left移到 right的最深左节点上，同时把 right 给当前节点

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 遍历方式：（前中后）深度优先，广度优先
    • 求属性题型：对称？ 最大/小深度，节点数？ 平衡？ 路径数？ 左子叶之和，左下角的值
    • 二叉搜索树题型：搜索，是否？ 众数，最小绝对差
    • 修改二叉树题型：翻转，构造，合并两个二叉树
    • 公共祖先问题

    使用前中后？规律：

    1. 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。

    2. 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。单纯求深度和找所有路径就用前序，方便让父节点指向子节点。

    3. 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

    回溯

    • 模板
    function backTracking () {
    if(终止条件) {
        存结果
        return
    }
    
    for(选择本层中元素) {
        处理节点...
        backTracking(路径，选择列表)	// 递归
        撤销结果
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 题型：

    组合问题：N个数里面按一定规则找出k个数的集合

    排列问题：N个数按一定规则全排列，有几种排列方式

    切割问题：一个字符串按一定规则有几种切割方式

    子集问题：一个N个数的集合里有多少符合条件的子集

    棋盘问题：N皇后，解数独等等

    // 组合 1-9 的k个数 组成和为 n
var combinationSum3 = function(k, n, res=[]) {
    const dfs = (stack, index) => {
        if(stack.length === k) {	// 终止，存结果
            if(stack.reduce((p,c) => p+c, 0) === n) {
                res.push(stack.slice())
            }
            return  // 这里不pop
        }
        for(let i=index; i<10; i++) {
            stack.push(i)	// 处理节点
            dfs(stack, i+1)
            stack.pop()		// 撤回
        }
    }
    dfs([], 1)
    return res
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    贪心

    找出局部最优并可以推出全局最优，并且找不到反例，就可以试试贪心。找不出局部最优，就不是贪心，可能是模拟

    动态规划

    • 五部
    1. 确定dp数组（dp table）以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导dp数组
    • 题型

    1. 背包

      （物品数量有限为01背包，遍历容量时倒序，无限为完全背包；有顺序为排列，先遍历容量再遍历物品，无序为组合；初始化条件和递归公式，求装满背包几种方法 dp[j] += dp[j - nums[i]]）

      01背包

      完全背包

      多重背包

    2. 打家劫舍

    3. 股票

      买卖最佳时期（限制买卖次数，冷冻期，手续费）

    4. 子序列

      不连续子序列（最长上升/公共）

      连续子序列（最大子序和，最长连续递增）

      回文（回文子串，最长回文子序列）

      编辑距离

    其他

    拓扑排序 依赖图找顺序

    有向图 找 拓扑序。其限制是对于序列中任意元素，前面都没有被它所指向的点。

    例如：

    • 商店有NN个物品，但其中购买一些物品需要先购买其他的物品才能解锁购买，求一个合法购买方案。

    将有前提条件的商品向所限制商品连边，例如：购买1号商品得先购买2，3号商品，所以将1号商品向2，3号商品连边，若出现了环，则互相约束，无解，然后跑一遍拓扑排序就行了。

    • 文件依赖，假设现有 0，1，2，3 四个文件，0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为 2,1,0,3 或 2,1,3,0。现给出文件依赖关系，如 1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，3号文件依赖1号文件。有同时可以编译多个文件的情况，按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3
    //** 这题比课程表简单，只有每个最多只有一个依赖
// 准备：list 存i ->依赖 v，map/queue 管理 按顺序放入 可以访问的(无需依赖/ 已有依赖)
// 1. 先找 -1（无依赖），放入 map
// 2. while（判出条件 size != len）, 遍历 has（v） & !has(i)
function compileSeq( input, res=[] ) {
    // write code here
    const list = input.split(',').map(Number), map = new Map()
    const len = list.length
    list.forEach((v,i) => {
        if(v === -1) map.set(i, true)
    })
    while(map.size !== len) {
        for(let i=0; i<len; i++) {
            if(map.has(list[i]) && !map.has(i)) {
                map.set(i, true)
                break    // 注意要 break, 因为要按顺序返回
            }
        }
    }
    map.forEach((v,i) => {
        res.push(i)
    })
    return res.join(',')
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 课程顺序 力扣207：判断有向图是否有环
    // [入度a, 出度b]: a <- b 学a要先学b，a依赖b
var canFinish = function(numCourses, prerequisites) {
    // 构建 邻接表（依赖表） 出度b：所有入度 (b可以到达的所有点)
    // 同时创建 入度列，用于判断是否所有入度为0
    const inqueue = Array(numCourses).fill(0), map = {}
    prerequisites.forEach(v => {
        inqueue[v[0]]++
        if(map[v[1]]) {
            map[v[1]].push(v[0])
        } else map[v[1]] = [v[0]]
    })
    
    // main 操作至所有入度为0
    // 跳出入度为0的，用于循环 -入度
    const zeroQueue = []
    inqueue.forEach((v,i) => {if(v === 0) zeroQueue.push(i)})
    while(zeroQueue.length) {
        const list = map[zeroQueue.shift()]
        if(list && list.length) {
            list.forEach(v => {
                if(--inqueue[v] === 0) zeroQueue.push(v)
            })
        }
    }
    return inqueue.every(v => v===0)
};

    • 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

    最优路

    最短路径长度（带障碍）

    思路：dfs 用 visited 数组保存是否走过

    游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，’#@‘是不可达的，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径

// 输入
15
0 7 7 7
*5#++B+B+++++$3
55#+++++++###$$
###$++++++#+*#+
++$@$+++$$$3+#+
+++$$+++$+4###+
A++++###$@+$++A
+++++#++$#$$+++
A++++#+5+#+++++
+++$$#$++#++++A
+++$+@$###+++++
+###4+$+++$$+++
+#+3$$$+++$##++
+#*+#++++++#$$+
$####+++++++$##
3$+++B++B++++#5

// 输出
9

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    // 准备数据
const n = +readline()
const [s2, s1, e2, e1] = readline().split(' ').map(Number)
const list = []
let count = n
while(count--) {
    const curList = readline().split('').map(v => {
        if(v == '#' || v == '@') return 0
        return 1
    })
    list.push(curList)
}

// 准备 全局变量
const row = n, column = list[0].length
const visited = Array(row).fill().map(v => Array(column).fill(-1))

// 关键函数  input: list 矩阵(0 不可达， 1可达)
const getBestPathLen = () => {
    const dfs = (cur, count) => {
        const [c1, c2] = cur
        if(c1<0 || c1>=row || c2<0 || c2>=column || !list[c1][c2] || visited[c1][c2] !== -1 && visited[c1][c2] <= count) return
        visited[c1][c2] = count
        if(c1 === e1 && c2 === e2) return
        dfs([c1+1, c2], count+1)
        dfs([c1, c2+1], count+1)
        dfs([c1-1, c2], count+1)
        dfs([c1, c2-1], count+1)        
    }
    dfs([s1,s2], 0)
}
getBestPathLen()
console.log(visited[e1][e2])

    • 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

    其他力扣分类题

  • 相关阅读:
    没想到吧，Spring中还有一招集合注入的写法
    通过监控Nginx日志来实时屏蔽高频恶意访问的IP
    3 万亿美元，苹果问鼎全球市值最高公司宝座
    CTO强烈禁止使用Calendar，那用啥？
    Vue框架中的面试相关问题
    传统企业数字化转型，处理好业务问题是关键
    【基于形态学的权重自适应去噪】
    mac m1 配置goland debbug
    get和post
    2022 大话--时间复杂度
  • 原文地址：https://blog.csdn.net/weixin_49834963/article/details/126452656