【LeetCode 总结】Leetcode 题型分类总结、索引与常用接口函数

文章目录

• 零. Java 常用接口函数
• 一. 动态规划
• 二. 链表
• 三. 哈希表
• 四. 滑动窗口
• 五. 字符串
• 六. DFS、BFS
• 七. 二分法
• 八. 二叉树
• 九. 偏数学、过目不忘 and 原地算法等

前言：

是时候开一个对于我的 LeetCode 专栏的总结索引了= =

虽然说大概只刷了150道左右，不过应该也可以简单总结一下了呢～

题型主要是 LeetCode hot100 + 剑指Offer，也有其他的一些高频题

持续更新中，还有120题左右，尽量这几天弄完… QAQ

零. Java 常用接口函数

集合类

// 1. ArrayList
list.add(element); // 加到尾部
list.size();

List<int[]> list = new ArrayList<>(); 
int[][] arr = list.toArray(new int[list.size()][2]); // 链表 -> 数组
list = Arrays.asList(arr); // 数组 -> 链表

// 2. LinkedList
list.add(element); // 加到尾部
list.addFirst(element); // 加到头部

list.removeFirst();
list.removeLast();

list.getFirst();
list.getLast();

// 3. Deque：双向队列
Deque<Integer> deque = new ArrayDeque<>(); // ArrayDeque 可以作为队列、栈来用，效率都更高
deque.offerFirst(element); // 加队头 or 加队尾
deque.offerLast(element); // 也可以换成 addFirst、addLast

deque.pollFirst(); // 出队头 or 出队尾（会返回元素）
deque.pollLast(); // 也可以换成 removeFirst、removeLast

deque.getFirst();
deque.getLast();

// 4. HashMap
hashmap.put(k, v);
hashmap.get(k); // 获取 k 对应的 v
hashmap.size();
hashmap.isEmpty();
hashmap.containsKey(key1); // 判断 key1 是否存在
hashmap.containsValue(value1); // 判断 value1 是否存在

// 5. HashSet
hashset.add(element);
hashset.contains(element);
hashset.remove(element);
hashset.size()

// 6. Stack
stack.push();
stack.pop();
stack.peek();
stack.isEmpty();

// 7. PriorityQueue 优先队列（堆）
// 知识点：小顶堆存较大值，大顶堆存较小值（便于维护）
// Lambda 表达式
           

数学类

Math.max(num1, num2); // 取最大值
Math.min(num1, num2); // 取最小值
Arrays.sort(arr); // 排序数组
Arrays.sort(arr, (a, b) -> (a[0) - b[0])) // 自定义排序方式的 sort
           

字符串

// String
char[] arr = s.toCharArray(); // 转化成字符数组，提高
String s2 = s1.substring(0, 3); // 截取，闭开区间[0,3)
char c = s1.charAt(1); // 选取元素，效率比较慢
s.length(); // 用函数获取长度，数组则直接 arr.length

int num = Integer.parseInt(s); // String 转换成 int
String s1 = Integer.toString(num); // int 转换成 String
String s2 = "" + num; // 也可以这样做

// StringBuilder：这里的 leetcode 都是单线程，因此不涉及 StringBuffer
sb.append("abc"); // 添加到尾
sb.delete(1, 3); // 删除，闭开区间[1, 3)的元素
           

一. 动态规划

考察的大头了，大部分题目都用的这玩意

知识点

• 三要素：边界处理、最优子结构、状态转移方程
• 滚动数组：用于节约空间复杂度，可能需要通过逆序处理来实现无后效性
• 树形dp：树结构的dp
• 数位dp：对象是数字的各个位的dp
• 01背包问题：取 or 不取的背包问题
• 主要就是：如何找出三要素
• O(1) 空间复杂度：逻辑上的数组，有时可以直接通过几个变量实现

题目

5.最长回文子串（字符串）

42. 接雨水（常考的 hard，思路还是挺好用的，在后面刷题也有类似的做法）

32. 最长有效括号（算是比较有难度的 hard 了，需要细分很多情况，考虑边界）

53. 最大子序和（常考 easy 题，思路还是很值得学习的：负收益舍弃）

128. 最长连续序列（哈希表）（被字节面过）

62. 不同路径（dp入门题）

64. 最小路径和（同上）

70. 爬楼梯（同上）

96. 不同的二叉搜索树（有点东西的，空树也算一种树，方程推导思路也值得学习，容易忘）

二. 链表

知识点

• 这块主要是链表结点之间关系的处理
• 头结点、尾结点的边界处理也要注意，小心空指针！

题目

2.两数相加

21. 合并 2 个有序链表

23. 合并 K 个升序列表（归并、分治）（很清晰的一道 hard，有前导题 合并 2 个有序链表）

19.删除链表的倒数第N个结点（快慢指针）

146. LRU缓存机制（手写双向链表 + 调库HashMap，注意结点关系处理）

160. 相交链表（原地算法，有点偏数学）

206. 反转链表 （递归 or 迭代，常考题了）

25. K个一组翻转链表（递归）（相当于 206.反转链表 + 递归）

三. 哈希表

知识点

• HashMap 可以存 null 作为键值
• 查询复杂度 O(1)

题目

1.两数之和

四. 滑动窗口

知识点

• 感觉这类题型，大多应用主体都是字符串呀！
• 主要涉及到几点操作：滑动窗口怎么拓增、缩小、移动

题目

3.无重复字符的最长字串（HashMap）

76. 最小覆盖子串（和上面的3很像）

五. 字符串

当然，涉及字符串的很多题目也会在四.滑动窗口、一. 动态规划中出现，这里不重复列出题目啦～

知识点

• 写这里的题目，要对 String、StringBuilder 的库函数有一定了解噢～

题目

49. 字母异位词分组

20. 有效的括号（栈）

六. DFS、BFS

知识点

• DFS：一路到底！
• BFS：用到队列，一层一层地跑完
• 剪枝：通过限定条件，减少需要递归的枝条，提高效率
• boolean[] visited：访问数组，用于递归中记录是否访问过。一般会涉及回滚

题目

46. 全排列（DFS、队列）

39. 组合总和（DFS、队列）

22. 括号生成（DFS、剪枝）

17. 电话号码的字母组合（DFS）

78. 子集（DFS)

79. 单词搜索 && 剑指 Offer 12 矩阵中的路径（DFS）

七. 二分法

诶，二分法在 leetcode 题库里还是有一席之地的，要学好也得多实践噢～

知识点

• 二分法和时间复杂度O(logN)挂钩！
• 注意边界，小心死循环！
• 分区 [left, mid]，[mid + 1, right]，注意 mid 的取值（向上 or 向下）
• while(left < right) 循环中，分两种情况、还是三种情况（大于、等于、小于）

题目

34. 在排序数组中查找元素的第一个和最后一个位置

33. 搜索螺旋排序数组

八. 二叉树

知识点

• 搜索二叉树：左子树均大于根，右子树均小于根
• 完全二叉树：倒数第二层结点全满
• 满二叉树：倒数第一层结点全满

题目

102. 二叉树的层序遍历（DFS + 队列即可）

94 & 144 & 145. 二叉树的前序、中序、后序遍历（迭代用栈，后序新增pre结点）

98. 验证二叉搜索树（DFS、中序遍历）（pre + 中序，保证当前最左边 && 次左边对比

101. 对称二叉树（递归）

102. 层序遍历（队列、递归）

九. 偏数学、过目不忘 and 原地算法等

这一块是记录那些比较偏数学，或者容易初见杀，但是实际代码量不多 or 写过一遍就忘不掉思路的题目。

知识点

• 原地算法：O(1)空间复杂度，要求原地的题目不少，看看能不能总结点规律出来

题目

55. 跳跃游戏（贪心法）

48. 旋转图像（原地算法、矩阵转置）

15. 三数之和（双指针）

11. 盛最多水的容器（双指针）

7. 整数反转（对溢出判断的做法，很值得学习！）

6. Z字形变化（主要考察思路的一道题，思路比较独特，类似压缩）

56. 合并区间（双指针，排序）(用了一波 Arrays.sort(arr, Lambda)，还有链表 - 数组转化）

84. 柱状图中最大的矩形（单调栈）

• 找数合集：

剑指 Offer 03. 数组中重复的数字（原地）数组转换成逻辑上的哈希表，很有意思

136. 只出现一次的数字（位运算）亦或性质：同数得0，与0不变

448. 找到所有不存在的数（原地） 数组常用的取负、取余处理

287. 寻找重复数（原地）转换成逻辑上的链表，再进行找入环点操作（环形链表II的兄弟题目

26. 删除有序数组中的重复项（原地）挺简单的。。逐个推就行