travisliang001 / leetcode Goto Github PK

• 相关学习：关于双指针算法问题的思考

• 相关学习：滑动窗口算法技巧

• 相关学习：二分查找是偏爱细节的魔鬼

查找峰值是非常典型的根据数据二段性进行二分的题目

前缀和表示数组的前 n 项和，它是一种数据预处理的方法，是对空间换时间的应用，我们一般会创建 数组长度 + 1 大小的数组来记录前缀和，并将 0 索引处的前缀和标记为 0，表示前 0 项和，如下图所示，索引 1 处的前缀和表示原数组中的前 1 项和（nums[0]），所以我们想获取原数组中某索引元素的前缀和的话，需要将索引值加 1 再从前缀和数组中取值。

一般 连续子数组 求和且不涉及区间修改的问题都可以使用前缀和来求解，通过 前缀和减法计算 我们能计算出任意区间和，这一点很重要，利用这一点可以解决很多区间求和的问题。

• 一维数组前缀和计算模板如下：

    int[] preSum = new int[nums.length + 1];
    for (int i = 1; i < preSum.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }

我们能通过前缀和减法计算任意区间和，即 preSum[k, i] = preSum[0, i] - preSum[0, k - 1]，其中 k <= i

我觉得 304 题是二维数组前缀和的代表性题目，熟悉它的解题思路之后，大概几分钟就能解出来。我们以计算 matrix[i][j] 处的前缀和为例，其中二维数组中每个元素表示以 [0, 0] 为左上角，以当前元素 [i, j] 为右下角构成的矩阵的前缀和，在计算 matrix[i][j] 之前，我们先来看一下官方题解给出示例图，我觉得记住这张图能的推导出计算公式：

计算 matrix[i][j] 我们能够依靠已知的前缀和 matrix[i - 1][j - 1]、matrix[i - 1][j] 和 matrix[i][j - 1]，其实我们可以轻易的根据图示得出 matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1]，为什么要减去 matrix[i - 1][j - 1] 呢，因为在 matrix[i - 1][j] 和 matrix[i][j - 1] 中都包含着 matrix[i - 1][j - 1]，我们做加和计算时把 matrix[i - 1][j - 1] 加了两遍，所以需要再减去一个，记住这个图示之后遇到类似的题推导一下就可以了，不必记住模板。

计算二维数组前缀和的要点一定是确定好 矩形的对角（左上角和右下角 或 左下角和右上角）

相关学习：深入理解树状数组

树状数组是一种简单的数据结构，它支持单点修改和区间查询操作，一般的 RMQ 问题优先选择树状数组求解，而不是线段树，后者相对来说代码量大，也比较复杂

• 树状数组解题模板：BinaryIndexedTree.java

相关学习：深入理解线段树

线段树可以解决区间和、区间最大值或区间最小值的问题（RMQ 问题），不过线段树的代码量相对来说较大而且比较复杂，所以线段树是在前缀和、差分和树状数组解决方法之后不得已才会考虑的方案。 一般使用线段树的题目都具备 区间修改和区间查询 的特点，如果大家在这里是按照顺序刷的话，应该对 RMQ 问题有一个比较充分的了解了，在这里做一下相关题型解法的归纳：

• 数组不变，区间查询：前缀和、树状数组和线段树
• 数组单点修改，区间查询：树状数组和线段树
• 数组区间修改，单点查询：差分和线段树
• 数组区间修改，区间查询：线段树

注意每种题型涉及的解法都是越靠前越优先考虑。

• 线段树模板：SegmentTree.java

• 线段树模板：SegmentTree2.java

• 线段树模版：SegmentTree3.java

1. 14. 最长公共前缀 简单
2. 151. 反转字符串中的单词 中等

• s.charAt(i) - '0' = 数字
• Integer.parseInt() 字符串转整数自动忽略前导0

1. 165. 比较版本号 中等:
2. 8. 字符串转换整数 (atoi) 中等
3. 43. 字符串相乘 中等

链表是一种 递归 的数据结构，与数组不同的是它不需要占用连续的内存空间，但是需要额外的空间保存后继节点的指针，以此将所有的链表节点串联起来。它的删除和插入操作比较高效，时间复杂度为 $O(1)$，但是想访问链表中某个值时，需要对链表进行遍历，时间复杂度为 $O(n)$。链表是数组的一种重要的替代方式。

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;

        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }

        return pre;
    }

栈是一种基于 后进先出（LIFO）策略 的集合类型，这就需要我们在对值进行处理时注意结果值有没有对顺序的要求，因为入栈到出栈是倒序的。

• 应用: 函数调用栈、括号的匹配、双栈实现浏览器的前进和后退功能、JVM栈、电子邮件的存放、算数表达式的求值(操作数栈和运算符栈)

单调栈本质上是 维护数组中的元素为单调序列，数组中的元素 要么 符合单调性顺利进栈，要么 不符合单调性而将栈中其他元素“挤走”再进栈，使得栈中序列始终满足单调性。

理解这一点很重要，我们以单调递增栈为例，如果出现了比栈顶元素 小 的值，即不符合当前栈中序列单增特性的值，那么它会使所有比它大的值出栈，而 该值便是接下来要连续出栈元素右侧最近的小值，比该值大的值出栈完毕后，该值进栈，使得栈中的序列仍然满足单调递增。

如果题目有 在连续序列中找元素左/右侧最近的大/小值 的特点，我们就可以使用单调栈来求解，找最近的小值的单调递增栈模板如下，注意入栈的是数组元素的索引而不是元素值：

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
        int index = stack.pop();
        
        // 关于 index 的特殊处理
        process();
    }
    // 索引入栈
    stack.push(i);
    
    // 处理逻辑
    process1();
}

这个模板其实很好记，根据想找小值还是找大值来确定模板中的 while 条件，如果找小值则使用小于号，则 nums[i] < nums[stack.peek()]，如果找大值则使用大于号，则 nums[i] > nums[stack.peek()]，再根据题意判断是否需要给大于小于号添加上等号，这一点考虑是在有重复值出现的情况下。

说了这么多，其实只需要考虑想找的是最近的小值还是大值，写对应的模板解题即可，即使你没明白为什么单调栈能找元素最近的大/小值（应该自己 Debug 学习一下）也没关系，只要使用了单调栈它就有这个性质，其他的全是虚妄......

该类型题目不直接要求找某元素左/右侧最近的大/小值，而是利用单调栈能找到某元素最近的大值/小值的特点来 确定当前元素作为区间内最大值/最小值时的区间范围（这么说起来有点儿绕），以此来计算该元素对题解的"贡献"。

我们初始化每个元素的默认区间范围如下，这是该元素作为极值时的特殊情况：

int[] left = new int[nums.length];
Arrays.fill(left, -1);
int[] right = new int[nums.length];
Arrays.fill(right, nums.length);

以当前元素作为区间内最大值为例，记录每个元素能到达的左侧/右侧的最远距离：

Stack<Integer> stack = new Stack<>();

// 正序遍历计算上界
for(int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
        right[stack.pop()] = i;    
    }  
    stack.push(i);
}
stack.clear();
// 逆序遍历计算下界
for (int i = nums.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        left[stack.pop()] = i;
    }
    stack.push(i);
}

注意，记录的区间范围为全开区间，所以如果在计算区间长度时需要减 1，而且当题目中没有规定所有值都不同时，有时需要为其中一个（正序或逆序）遍历条件增加等号，避免发生“重复统计”。

先进先出队列（简称队列）是一种基于先进先出（FIFO）策略的集合类型，它相比于栈多了能够在队首操作的方法，所以使用栈能解决的问题队列也能解决，不过使用队列解决的问题会突出 需要操作两端数据 的特点。

单调队列是在单调栈的基础上实现了对 序列的两端操作，所以使用单调队能让我们 获取区间最值（队首即为最值）和 移除队首值。此外 不要局限 在只使用一个单调队列解题，有的题目需要维护两个单调队列来分别记录区间内的最大值和最小值来求解。

理论上使用单调栈能解决的问题单调队列也能解决，不过在我们不需要获取区间最值时还是使用单调栈来求解。

能获取区间最大值（nums[deque.peekFirst()]）的单调递减队列模板如下：

    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
            int index = deque.pollLast();
            // 关于 index 的特殊处理
            process();
        }
        deque.addLast(i);
        
        // 必要处理逻辑
        process1();
    }

• 时间复杂度为 O(n²) 的排序算法

• 时间复杂度为 O(nlogn) 的排序算法

• 时间复杂度为 O(n) 的排序算法

• 相关学习：一文搞懂优先队列及相关算法

• 相关学习：树专题 —— 二叉搜索树和中序遍历

• 相关学习：树专题 —— 二叉树前序遍历

• 相关学习：树专题 —— 二叉树后序遍历

实现散列表分为两步：

1. 用散列函数将被查找的键转化为数组的一个索引，理想情况下，不同的键都能转化为不同的索引值
2. 处理碰撞冲突，有两种常见的处理方法，分别为拉链法和线性探测法。前者的方法是将发生碰撞的元素保存在链表中；后者的**是与其将内存用作链表，不如将它们保存在散列表的空元素中

散列表数据结构使用了适度的空间和时间，并在这两个极端之间找到了平衡

动态规划一般都用来求最值，它的问题核心是穷举，如果使用回溯解决问题时，要考虑使用备忘录对其进行优化。解题时需要考虑以下几点

1. 这个问题的 base case 是什么？
2. 它的子问题是什么？再想想它的状态呢？
3. 它的状态转移方程是怎样的？
4. 如何定义dp来表现状态或采用回溯法时如何用方法来表示它的状态？

// 解题模板
dp[0][0][...] = base case;
for 状态1 in 状态1中的所有值
    for 状态2 in 状态2中的所有值
        for ...
            dp[状态1][状态2][...] = 状态转移方程 = 最值;

1. 剑指 Offer 10- II. 青蛙跳台阶问题 简单
2. 322. 零钱兑换 中等
3. 64. 最小路径和 中等
4. 剑指 Offer 42. 连续子数组的最大和 简单
5. 198. 打家劫舍 中等
6. 213. 打家劫舍 II 中等
7. 剑指 Offer 14- I. 剪绳子 中等
8. 剑指 Offer 46. 把数字翻译成字符串 中等
9. 剑指 Offer 47. 礼物的最大价值 中等
10. 剑指 Offer 49. 丑数 中等
11. 72. 编辑距离 困难

涉及子序列，一般情况下时间复杂度为 $O(n^2)$，那么就跑不了双层的for循环

// 解题模板，针对数组的最长递增子序列问题，一维数组
int n = array.length;
int[] dp = new int[n];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        dp[i] = 最值;    
    }
}

// 解题模板，针对两个数组或字符串的子序列问题
int n1 = array1.length;
int n2 = array2.length;
int[][] dp = new int[n1][n2];

for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
        if (n1[i] == n2[j]) {
            dp[i][j] = 
        } else {
            dp[i][j] = 
        }    
    }    
}

1. 1143. 最长公共子序列 中等
2. 516. 最长回文子序列 中等: 回文串系列都是反向遍历
3. 1312. 让字符串成为回文串的最少插入次数 困难

1. 剑指 Offer 60. n个骰子的点数 中等

回溯相当于穷举搜索，但是回溯算法的复杂度非常高，只能用来解决小规模的数据问题。回溯问题可以想成 "决策树" ，在树的每个节点从 "选择列表" 里做出不同的决策， 而当走过的 "路径" 满足结束条件时即为答案之一。回溯算法用于解决全排列、八皇后、正则表达式匹配和某些做选择的动态规划问题，它的解题模板如下

result = [];
def backtrack(路径, 选择列表):
    if 满足结束条件
        result.add(路径)
        return
    
    for 选择 in 选择列表: 
        // 做选择
        路径.add(选择)
        backtrack(路径, 选择列表)
        // 撤销选择
        路径.remove(选择)

1. 46. 全排列 中等
2. 剑指 Offer 38. 字符串的排列 中等
3. 39. 组合总和 中等
4. 40. 组合总和 II 中等
5. 78. 子集 中等
6. 22. 括号生成 中等
7. 面试题 08.12. 八皇后 困难
8. 10. 正则表达式匹配 困难
10. 139. 单词拆分 中等: 字符串API startsWith(s) 判断字符串是否以某字符串开头

递归矩阵问题注意单元格重复访问的问题，一般用 visited[][] 来标记是否访问过

1. 200. 岛屿数量 中等
2. 剑指 Offer 12. 矩阵中的路径 中等
3. 面试题13. 机器人的运动范围 中等

1. 121. 买卖股票的最佳时机 简单
2. 122. 买卖股票的最佳时机 II 中等
3. 123. 买卖股票的最佳时机 III 困难
4. 135. 分发糖果 困难: 向左向右分别分一次的想法如果能想到就太简单了
5. 55. 跳跃游戏 中等

1. 剑指 Offer 15. 二进制中1的个数 简单
2. 剑指 Offer 16. 数值的整数次方 中等