LeetCode算法题解

个人算法实践，详细注释，提供多种解体方案和思路。

二分查找

专题文章：双指针技巧总结

二分法一般针对已经排好序的数组。

// 二分法套路
function dichotomy() {
    // 左边界
    var left ...
    // 右边界
    var right ...
    // 记录答案
    var ans
    while(left <= right) {
        // 中间值
        var middle = Math.floor((left + right) / 2)
        // 猜测是否满足条件
        if (guess(middle, ...)) {
            // 如果满足条件，记录答案
            ans = middle
            // 缩小搜索范围，在更小的值中搜索
            right = middle - 1
        } else  {
            // 在更大的值中搜索
            left = middle + 1
        }
    }
    return ans
}

更多二分法技巧

• 二分查找^折半搜索
• 搜索插入位置
• x 的平方根
• 第一个错误的版本
• 寻找比目标字母大的最小字母
• 33.搜索旋转排序数组
• 153.寻找旋转排序数组中的最小值

二叉树

专题文章：二叉树的深度优先遍历与广度优先遍历

• 定义二叉搜索树^递归
• 相同的树^递归
• 对称二叉树^{递归、技巧}
• 二叉搜索树中的搜索^递归
• 判断二叉树是否是高度平衡的二叉树^递归
• base-traverse 遍历
  • 二叉树的前序遍历^递归、栈
  • 二叉树的中序遍历^递归
  • 二叉树的后序遍历^递归、栈
  • 将有序数组转换为二叉搜索树^{递归（分治）、中序遍历的逆操作}
• depth-first-search 深度优先
  • 给定一个二叉树，返回所有从根节点到叶子节点的路径^DFS-递归
  • 路径总和^DFS-递归
  • 路径总和2^DFS-递归
• breadth-first-search 广度优先
  • 二叉树的层次遍历 II^队列BFS
• 二叉树的最大深度^{递归BFS、队列BFS}
• 二叉树的最小深度^{递归BFS、队列BFS}

String

• 回文数^{技巧、双指针法}
• 125.验证回文串^{技巧、双指针法}
• 反转字符串中的元音字母^双指针法
• 字符串解码^栈
• 实现strStr() 即实现js中indexOf
• 字符串相加
• 3.无重复字符的最长子串
• 383. 赎金信^hashmap

技巧题

许多算法题，除了数据结构外，还有许多是解题思路。换个思维方式或许有更多解法。

• 两数之和^{技巧、hashmap}
• 两数之和 II - 输入有序数组
• 反转字符串^双指针法
• 排列硬币

分治（递归）

递归是分治算法**最常用方法。

递归的三大要素:

• 第一要素：明确你这个函数想要干什么
• 第二要素：寻找递归结束条件
• 第三要素：找出函数的等价关系式(不断缩小参数的范围)

有关递归的一些优化思路:

1. 考虑是否重复计算
2. 考虑是否可以自底向上

• 简单案例理解
  • fibonacci
  • 小青蛙跳台阶
• 翻转链表
• 两数的最大公约数^递归

动态规划

• 经典01背包问题^{递归、动态规划}
• 1143. 最长公共子序列^{递归、动态规划}
• 字符串最小编辑距离^动态规划

参考

• 数据结构和算法

• 背包问题

• 双指针技巧总结