学习笔记

3. 实战题目解析：盛水最多的容器、爬楼梯

盛水最多的容器

• i, j遍历不相交

for (int i = 0; i < list.length - 1; i++)
    for (int j = i + 1; j < list.length; j++)
        ...

• 左右边界 i, j, 向中间收敛

for (int i =0, j = list.length - 1; i < j) {
    i++;
    j--;
}

爬楼梯

归纳法 --> 从基本情况找最近重复子问题 计算机程序逻辑无非三类：分支，循环与递归 遇到难题找重复性

4. 实战题目解析：3数之和、环形链表

3数之和 （高频）

双指针法/夹逼法，做到滚瓜烂熟

经典写法

while ( i < j && nums[ i ] == nums[ ++i ] );
while ( i < j && nums[ j ] == nums[ --j ] );

环形链表

Linked List类题目解法固定，熟能生巧

环形链表常用套路 - 快慢指针

第1周 第4课 | 栈、队列、优先队列、双端队列

1. 栈和队列的实现与特性

2. 实战题目解析：有效的括号、最小栈

具有最近相关/重复性的问题，由内向外，或由外向内层层扩散，那么栈就非常合适。 滑动窗口问题，就用队列。

---

本周作业

简单：

• 用 add first 或 add last 这套新的 API 改写 Deque 的代码
• 分析 Queue 和 Priority Queue 的源码
• 删除排序数组中的重复项
• 旋转数组
• 合并两个有序链表
• 合并两个有序数组
• 两数之和
• 移动零
• 加一

中等：

• 设计循环双端队列

困难：

• 接雨水

下周预习

预习题目

• 有效的字母异位词
• 二叉树中序遍历
• 最小的K个数