LeetCode刷题记录

一、数组

1. 删除有序数组中的重复项Ⅱ
2. 轮转数组
3. 买卖股票的最佳时机Ⅱ
4. 跳跃游戏
5. 跳跃游戏Ⅱ
6. H指数除自身以外数组的乘积
7. 加油站
8. O(1) 时间插入、删除和获取随机元素
9. 分发糖果 参考题解
10. 接雨水 参考题解 单调栈参考 参考题解2—巧妙 参考题解3

字符串

1. 整数转罗马数字
2. Z字形变换
3. 文本左右对齐 参考题解

双指针

1. 验证回文串
2. 判断子序列
3. 两数之和Ⅱ-输入有序数组
4. 盛最多水的容器
5. 三数之和

滑动窗口

1. 长度最小的子数组
2. 无重复字符的最长子串
3. 串联所有单词的子串 参考题解
4. 最小覆盖子串 参考题解

哈希表

1. 赎金信
2. 有效的字母异位词
3. 字母异位词分组
4. 快乐数
5. 存在重复元素Ⅱ
6. 最长连续序列
7. 三数之和 参考题解

区间

1. 汇总区间
2. 合并区间 参考题解
3. 插入区间
4. 用最少数量的箭引爆气球 参考题解

笔记

1. ans.toArray(new int[0][]) 会创建一个新的 int[][] 数组，并将 ans 中的元素复制到这个数组中。new int[0][] 是一个空的二维数组，用于告诉 toArray 方法返回的数组类型，并根据 ans 的大小来创建实际的数组。

   List<int[]> ans = new ArrayList<>();
   return ans.toArray(new int[0][]);

2. 按 intervals[][] 的每一行的首元素排序

   Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

3. 区间问题的关键在于左右端点的判断和更新时机

Kadane算法

1. 最大子数组和
2. 环形子数组的最大和 参考题解

回溯

子集型

1. 电话号码的字母组合 参考题解
2. 分割回文串 参考题解
3. 子集

组合型 剪枝

1. 组合 参考题解 参考题解
2. 组合总和
3. 括号生成 参考题解

排列型

1. 全排列
2. N皇后 参考题解
3. N皇后Ⅱ
4. 单词搜索 参考题解

二分查找

1. 搜索插入位置
2. 搜索二维矩阵
3. 寻找峰值 参考题解
4. 搜索旋转排序数组
5. 在排序数组中查找元素的第一个和最后一个位置
6. 寻找旋转排序数组中的最小值 参考题解
7. 寻找两个正序数组的中位数

二、栈&链表&堆

栈

1. 有效的括号
2. 简化路径
3. 最小栈 ——用栈+辅助栈实现
4. 逆波兰表达式求值
5. 基本计算器

笔记

1. path.split("/")：将 path 字符串按 / 拆分成一个字符串数组。

• "/home//user/"的切割结果是： [] home [] user []

2. Deque<>和Stack<>` 都可以用于实现栈。

• Deque<>:LinkedList 实现的 Deque 不是线程安全的。如果需要线程安全，可以使用 ConcurrentLinkedDeque。

  Stack<>:是线程安全的，因为它的方法是同步的，但这种线程安全特性可能会引入额外的开销。

  总结

  如果应用场景需要线程安全的栈，Stack<> 可能会更合适。

  在大多数情况下，特别是当不需要线程安全性时，使用 Deque<>（尤其是 ArrayDeque 实现）会更高效，并且是推荐的做法

3. StringBuilder 的 equals 方法

• StringBuilder 类的 equals 方法并没有被重写，因此它继承了 Object 类的默认 equals 实现。这个默认实现比较的是对象的引用，而不是对象的内容。

• 因此，ans.equals("") 会检查 ans 对象是否与 ""（一个空字符串对象）相同，而这永远是 false，因为 StringBuilder 和 String 是不同的类，即使 StringBuilder 为空，它也不等于一个空字符串。

• 要检查一个 StringBuilder 对象是否为空（即其内容是否为空），应该使用 StringBuilder 提供的方法，比如 length() 或 toString()

链表

1. 环形链表
2. 环形链表Ⅱ 快慢指针参考题解
3. 两数相加
4. 合并两个有序链表
5. 随机链表的复制 参考题解
6. 反转链表Ⅱ
7. 反转链表 参考题解
8. K个一组翻转链表
9. 删除排序链表中的重复元素Ⅱ
10. 旋转链表
11. 分隔链表 参考题解
12. LRU缓存 参考题解

笔记

链表遍历注意

//修改 head 可能会导致链表丢失；使用额外的 current 指针，可以在不改变原链表结构的情况下遍历链表。

堆

1. 数组中的第K个最大元素

   Queue<Integer> heap = new PriorityQueue<>();	// PriorityQueue 默认是小根堆
   PriorityQueue 是一个基于优先级的队列，默认情况下，它按照自然顺序排列元素，即小根堆，堆顶是最小元素。为了实现大根堆，我们可以使用 Collections.reverseOrder() 作为构造参数。
   Collections.reverseOrder() 返回一个比较器，这个比较器反转了元素的自然顺序
       
   maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 大根堆
   
   不提供比较器：使用默认自然顺序（小根堆）。
   提供比较器：按照指定的顺序排列元素（可以是大根堆或其他顺序）
   

2. IPO

3. 查找和最小的K对数字 参考题解

   数组转List

   int[] poll = heap.poll();
   List<Integer> list = Arrays.stream(poll).boxed().collect(Collectors.toList());
   Arrays.stream(poll):	这个方法将 int[] 转换为一个流（Stream）。流是一种可以处理数据序列的功能。
   .boxed():这个方法将 int 原始类型的流转换为 Integer 对象的流。因为 Java 的集合类（如 List）只能存储对象，而不能存储原始类型。
   .collect(Collectors.toList()):最后，使用 Collectors.toList() 将流收集到一个 List<Integer> 中。这样就完成了从 int[] 到 List<Integer> 的转换。

4. 数据流的中位数

三、二叉树

1. 二叉树的最大深度

2. 相同的树

3. 翻转二叉树

4. 对称二叉树 参考题解

5. 从前序与中序遍历序列构造二叉树 参考题解 参考题解2

6. 从中序与后序遍历序列构造二叉树

7. 填充每个节点的下一个右侧节点指针Ⅱ

8. 二叉树展开为链表

9. 路径总和

10. 求根节点到叶节点数字之和

11. 二叉树中的最大路径和

12. 二叉搜索树迭代器 参考题解

13. 完全二叉树的节点个数

14. 二叉树的最近公共祖先 参考题解

笔记

1. 写树算法的套路框架

2. 对称二叉树定义

   1.L.val = R.val ：即此两对称节点值相等。
   2.L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称。
   3.L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。

3. 细节

   List<TreeNode> cur = new ArrayList<>();
   List<TreeNode> next = new ArrayList<>();
   cur = next;
   将 cur 引用设置为指向 next 对象。cur 和 next 将指向同一个 ArrayList 实例
   cur 和 next 共享相同的数据，并且对其中一个的修改需要反映到另一个上

4. Deque<T> cur = new LinkedList<>();和Deque<T> cur = new ArrayDeque<>();

   LinkedList 是基于链表的实现。每个元素都包含指向前一个和下一个元素的指针。
   ArrayDeque 是基于动态数组的实现，内部使用了数组来存储元素
   
   LinkedList: 更适合频繁的插入和删除操作，尤其是在列表的两端或中间；随机访问较慢，内存开销较大。
   ArrayDeque: 更适合频繁的两端插入和删除操作，以及需要较低的内存开销；随机访问性能较好，但在极端情况下可能需要扩展数组的容量

5. 二叉搜索树

   前序遍历：往左子树，更新当前值为右区间；往右子树，更新当前值为左区间
   中序遍历：是个递增数组
   

二叉树层次遍历

1. 二叉树的右视图
2. 二叉树的层平均值
3. 二叉树的层序遍历 参考题解
4. 二叉树的锯齿形层序遍历

二叉搜索树

1. 二叉搜索树的最小绝对差
2. 二叉搜索树中第K小的元素
3. 验证二叉搜索树 参考题解

分治

1. 将有序数组转换为二叉搜索树 参考题解
2. 排序链表 参考题解
3. 建立四叉树
4. 合并K个升序链表

四、图

深度优先搜索

1. 岛屿问题: 在网格中DFS

   1. 岛屿数量

   2. 岛屿的周长

   3. 岛屿的最大面积

   4. 最大人工岛 参考题解

      HashSet 的 add 方法用于向集合中添加元素：
          集合中不存在该元素，add 方法会将其添加，并返回 true。
          如果元素已存在，则不做任何操作，返回 false

   5. 被围绕的区域

2. 克隆图 参考题解

拓扑排序

1. 课程表 参考题解

   map.putIfAbsent(prerequisites[i][1], new ArrayList<>());
   putIfAbsent 是 Map 接口的方法，它的功能是：
   如果指定的键当前不在 map 中，则将该键和指定的值放入 map。
   如果键已经存在，putIfAbsent 不会做任何操作，不会替换原有的值。

2. 课程表Ⅱ

   list.isEmpty() 和 list == null

   List<String> list = new ArrayList<>();
   System.out.println(list.isEmpty()); // true
   System.out.println(list == null);    // false
   
   List<String> list = null;
   System.out.println(list.isEmpty()); // 会抛出 NullPointerException
   System.out.println(list == null);    // true

广度优先搜索

1. 除法求值 参考题解
2. 最小基因变化
3. 单词接龙

字典树

1. 实现Trie(前缀树) 参考题解
2. 添加与搜索单词-数据结构设计 参考题解
3. 单词搜索Ⅱ 参考题解

五、数学

1. 回文数
2. 加一
3. 阶乘后的零 参考题解
4. x的平方根
5. Pow(x, n)
6. 直线上最多的点数

矩阵

1. 有效的数独
2. 旋转图像
3. 矩阵置零
4. 生命游戏

位运算

1. 二进制求和
2. 颠倒二进制位
3. 位1的个数
4. 只出现一次的数字 参考题解 参考题解2
5. 只出现一次的数字Ⅱ 参考题解
6. 数字范围按位OR 参考题解

笔记

1. 在数学上，将一个整数转换为二进制的过程包括以下步骤：

   1. 除以 2: 将整数除以 2，记录下余数（0 或 1）。
   2. 记录商: 将除法得到的商作为新的数，重复步骤 1。
   3. 重复直到商为 0: 继续除以 2，直到商为 0。
   4. 逆序余数: 最终，二进制表示是余数从最后一次到第一次的逆序排列。

   示例

   将 13 转换为二进制：

   13 ÷ 2 = 6，余数 1

   6 ÷ 2 = 3，余数 0

   3 ÷ 2 = 1，余数 1

   1 ÷ 2 = 0，余数 1

   余数从最后到最开始的逆序是 1101，因此 13 的二进制表示是 1101

六、动态规划

一维动态规划

1. 爬楼梯

2. 打家劫舍

   String s = "catsandog";
   String result = s.replace("san", "");  // 移除子串 "san"

3. 单词拆分

   零钱兑换问题

4. 零钱兑换

5. 分割等和子集

6. 最长递增子序列 参考题解

多维动态规划

1. 三角形最小路径和
2. 最小路径和
3. 不同路径Ⅱ
4. 最长回文子串
5. 交错字符串
6. 编辑距离
7. 最大正方形
8. 买卖股票的最佳时机Ⅱ
9. 买卖股票的最佳时机Ⅳ

七、贪心算法