1.3合并区间

排序

首先，将列表中的区间按照左端点升序排序。

查看代码

 //将列表中的区间按照左端点升序排序Arrays.sort(intervals,new Comparator(){public int compare(int[] interval1,int[]interval2){return interval1[0]-interval2[0];}
});

然后将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；

否则，它们重合，需要将比较当前区间的右端点和数组 merged 中最后一个区间的右端点，将此merged中最后一个区间的右端点值置为二者的较大值。

2、二维数组

2.1旋转矩阵

使用辅助矩阵：

时间复杂度：O(N^2)，其中N是matrix 的边长。

空间复杂度：O(N^2)，需要使用一个和matrix 大小相同的辅助数组。

对于矩阵中第 i 行的第 j个元素，在旋转后，它出现在倒数第 i列的第 j个位置。

copy[j][row-i-1]=matrix[i][j]

2.2零矩阵

使用标记数组：

用两个标记数组分别记录每一行和每一列是否有零出现。具体地，首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为true。最后再次遍历该数组，用标记数组更新原数组即可。

2.3对角线遍历

boolean flag = true;//true:对角线从下往上；false：对角线从上往下

总共有row+column-1条对角线。

每一趟对角线中元素的坐标（x, y）相加的和是递增的。第一趟：x + y == 0。第二趟：x + y == 1。第三趟： x + y == 2。

每一趟都是 x 或 y 其中一个从大到小（每次-1），另一个从小到大（每次+1）

3、字符串

3.1最长公共前缀

内置函数：str.length()；s.substring(start,end+1)；str.charAt(i)

横向比较：自定义方法public String comparePrefix(String s1,String s2)，输入两个字符串，输出一个公共前缀。得到的结果与后面的字符串逐个进行比较，更新公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

时间复杂度：O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数

3.2最长回文子串

内置函数：str.length()；Math.max(,)；s.substring(start,end+1)；str.charAt(i)

中心扩散法：自定义函数public int getLengthOfPalindrome(String str,int left,int right) 获取回文字符串的长度，字符串str的回文中心在left和right之间。

枚举回文串的「回文中心」，并从回文中心开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从 P(i+1,j-1) 扩展到 P(i,j)；如果两边的字母不同，我们就停止扩展，因为在这之后的子串都不能是回文串了。此时得到对应回文中心的回文子串长度，选出所有回文中心情况下的最长长度就是结果。

时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心(奇数和偶数的情况)分别有 n 和 n-1个，每个回文中心最多会向外扩展 O(n)次。

空间复杂度：O(1)

3.3翻转字符串里的单词

双指针法：

内置函数：s.trim()删除首尾的空格, s.length(),s.substring(i+1,j+1),s.charAt(i)

先删除字符串首尾空格，从末尾开始遍历，判断单词长度，遍历完一个单词，和空格一起添加(append)进结果，然后判断单词前面的空格，直到遇到字符后继续判断单词长度。需要留下一个变量j指向单词的尾字符。

字符串用length(),数组用length

3.4找出字符串中第一个匹配项的下标

实现strStr()

暴力匹配：独立完成。

4、双指针技巧

场景一：从两端向中间迭代数组。

这时你可以使用双指针技巧：一个指针从头部开始，而另一个指针从尾部开始。

这种技巧经常在排序数组中使用。

4.1反转字符串

双指针：独立完成

两边向中间移动，互换字符。循环条件while(i

4.2数组拆分Ⅰ

内置函数：Arrays.sort(nums)，nums.length

字符串用length(),数组用length

先排序，后选择偶数项相加

4.3两数之和Ⅱ-输入有序数组

1.暴力解法：独立完成

2.双指针

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 numbers[i]+numbers[j]=target 是唯一解，其中 。初始时两个指针分别指向下标 0和下标numbers.length−1，左指针指向的下标小于或等于 i，右指针指向的下标大于或等于 j。除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 的位置或者右指针先到达下标 j的位置。

如果左指针先到达下标 i的位置，此时右指针还在下标 j的右侧， sum>target，因此一定是右指针左移，左指针不可能移到 i的右侧;如果右指针先到达下标 j的位置，此时左指针还在下标 i的左侧， t，因此一定是左指针右移，右指针不可能移到 j的左侧。

由此可见，在整个移动过程中，左指针不可能移到 i的右侧，右指针不可能移到 j的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。

场景二：

我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。

这是你需要使用双指针技巧的另一种非常常见的情况：同时有一个慢指针和一个快指针。

解决这类问题的关键是：确定两个指针的移动策略。

与前一个场景类似，你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。

4.4移除元素

1.双指针

可以使用双指针：右指针 right 指向当前将要处理的元素，左指针left 指向下一个将要赋值的位置。

如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；如果右指针指向的元素等于val，它不能在输出数组里，此时左指针不动，右指针右移一位。

• 时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。
• 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

4.5 最大连续1的个数

记录当前连续1的个数，如果当前元素是 1，则将当前的连续 1 的个数加 1，直到当前元素不为1为止。记录下此时的连续的1个数，与之前的记录的个数比较，取较大值作为记录结果。循环下去直至结束对数组的遍历。

• 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次。
• 空间复杂度：O(1)。

4.6 长度最小的子数组

双指针滑动窗口

定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，变量sum 表示子数组中的元素和（即从nums[start] 到 nums[end] 的元素和）。

初始状态下，start 和end 都指向下标0，sum 的值为0。每一轮迭代，将end指针往后移一位，然后将新的 nums[end] 加到 sum。如果sum≥s，则更新子数组的最小长度（此时子数组的长度是end−start+1），然后将nums[start] 从sum 中减去并将start 右移，end保持不变，直到sum

时间复杂度： O(n)，其中 n是数组的长度。指针start 和end 最多各移动 n次。

空间复杂度： O(1)。

4.7 杨辉三角Ⅰ

逐行计算

定义：List> ret = new ArrayList>();

List row = new ArrayList();

内置函数：row.add(j,1); row.get(j-1);

• 时间复杂度：O(numRows^2)。
• 空间复杂度：O(1)。不考虑返回值的空间占用。

4.8 杨辉三角Ⅱ

方法一：同上，只是取出对应的行(get(index))

内置函数：row.add(j,1); row.get(j-1);

优化：

当前行第 i项的计算只与上一行第 i-1 项及第 i项有关。因此我们可以倒着计算当前行，这样计算到第 i项时，第 i-1项仍然是上一行的值。

内置函数：row.set(j, value);

• 时间复杂度：O(rowIndex2)。
• 空间复杂度：O(1)。不考虑返回值的空间占用。

4.9 反转字符中的单词 Ⅲ

内置函数：s.length(); s.charAt(j); res.append; res.toString().trim(); StringBuilder res = new StringBuilder();

开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果

时间复杂度：O(N)，其中N 为字符串的长度。原字符串中的每个字符都会在O(1) 的时间内放入新字符串中。

空间复杂度：O(N)。我们开辟了与原字符串等大的空间。

4.10 寻找旋转排序数组的最小值

暴力解法：独立完成

二分法：

时间复杂度：时间复杂度为 O(log n)，其中 n是数组nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为O(log n)。

空间复杂度：O(1)。

4.11 删除排序数组中的重复项

双指针：

• 时间复杂度：O(n)，其中n 是数组的长度。快指针和慢指针最多各移动n 次。
• 空间复杂度：O(1)。只需要使用常数的额外空间。

4.12 移动零

二次遍历(双指针)：第一次遍历用来记录非零元素(int i=0;i

• 时间复杂度: O(n)
• 空间复杂度: O(1)

一次遍历：参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。

这里我们可以用0当做这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]

三、哈希表

1、设计哈希表

哈希表的关键思想是使用哈希函数(hashcode())将键映射到存储桶。

当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

1.哈希函数作为资源。

2.add 和 search 作为 method。

1.1设计哈希集合

哈希： 

查看代码

 HashMap map = new HashMap<>();int maxLen = 0;//用于记录最大不重复子串的长度int left = 0;//滑动窗口左指针for (int i = 0; i < s.length() ; i++){/**1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；2、如果当前字符 ch 包含在 map中，此时有2类情况：1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时应该不变，left始终为2，子段变成 ba才对。为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！*/if(map.containsKey(s.charAt(i))){left = Math.max(left , map.get(s.charAt(i))+1);}//不管是否更新left，都要更新 s.charAt(i) 的位置！map.put(s.charAt(i) , i);maxLen = Math.max(maxLen , i-left+1);}return maxLen;

2、实际应用-哈希集合HashSet

哈希集是集合的实现之一，它是一种存储不重复值的数据结构。

查看代码

                  // 1. initialize the hash setSet hashSet = new HashSet<>();    // 2. add a new keyhashSet.add(3);// 3. remove the keyhashSet.remove(3);       // 4. check if the key is in the hash setif (!hashSet.contains(2)) {System.out.println("Key 2 is not in the hash set.");}// 5. get the size of the hash setSystem.out.println("The size of has set is: " + hashSet.size());    // 6. iterate the hash setfor (Integer i : hashSet) {System.out.print(i + " ");}System.out.println("are in the hash set.");// 7. clear the hash sethashSet.clear();// 8. check if the hash set is emptyif (hashSet.isEmpty()) {System.out.println("hash set is empty now!");}

2.1存在重复元素

定义哈希集合：Set hashSet = new HashSet<>();

2.2只出现一次的数字

方法一：使用异或

方法二：使用哈希集合

独立完成

2.3两个数组的交集

先随机存储一个数组的元素到哈希集合，然后遍历第二个数组，如果第二个数组的元素也存在于第一个哈希集合，则添加进第二个哈希集合，最后得到交集的元素。然后将第二个哈希集合转换为数组输出结果。

时间复杂度： O(m+n)，其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 O(m+n) 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 O(min(m,n)) 的时间，因此总时间复杂度是 O(m+n)。

空间复杂度： O(m+n)，其中 m 和 n分别是两个数组的长度。空间复杂度主要取决于两个集合

2.4快乐数

1.把每一次得到的结果都保存到hashset中

2.如果得到的结果是1，就直接返回为true

3.如果不是1，就查看hastset中是否有这个值，如果有，那么就产生了循环，那么他就不是快乐数

3、实际应用-哈希映射HashMap

哈希映射是用于存储 (key, value) 键值对的一种实现。

// "static void main" must be defined in a public class.public class Main {public static void main(String[] args) {// 1. initialize a hash mapMap hashmap = new HashMap<>();// 2. insert a new (key, value) pairhashmap.putIfAbsent(0, 0);hashmap.putIfAbsent(2, 3);// 3. insert a new (key, value) pair or update the value of existed keyhashmap.put(1, 1);hashmap.put(1, 2);// 4. get the value of specific keySystem.out.println("The value of key 1 is: " + hashmap.get(1));// 5. delete a keyhashmap.remove(2);// 6. check if a key is in the hash mapif (!hashmap.containsKey(2)) {System.out.println("Key 2 is not in the hash map.");}// 7. get the size of the hash mapSystem.out.println("The size of hash map is: " + hashmap.size());// 8. iterate the hash mapfor (Map.Entry entry : hashmap.entrySet()) {System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");}System.out.println("are in the hash map.");// 9. clear the hash maphashmap.clear();// 10. check if the hash map is emptyif (hashmap.isEmpty()) {System.out.println("hash map is empty now!");}}}

场景一：提供更多信息

3.1两数之和

HashMap内置函数：hashmap.containsKey(a)，hashmap.get(a)，hashmap.put(nums[i],i)

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

3.2同构字符串

HashMap内置函数：hashmap.containsKey(a)，hashmap.get(a)，hashmap.put(nums[i],i)

String：s.charAt(i)，s.length()

需要双向判断，需要两个哈希映射防止不同字符映射到同一个字符上

时间复杂度：O(n)，其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s 和 t 即可。

空间复杂度：O(∣Σ∣)，其中Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要 O(∣Σ∣) 的空间。

3.3两个列表的最小索引总和

内置函数：

Map map = new HashMap<>();

List res = new ArrayList<>();

int sum = Integer.MAX_VALUE;

hashmap.containsKey(a)，hashmap.get(a)，hashmap.put(nums[i],i)

res.clear()，res.add(list2[i])，res.toArray(new String[res.size()])

先将任意一个列表存入hashmap，然后containsKey判断另一个列表是否有重复

arraylist.toArray(T[] arr)

注：arraylist 是 ArrayList 类的一个对象。

参数说明：

• · T [] arr（可选参数）- 用于存储数组元素的数组

注意：这里 T 指的是数组的类型。

场景二：按键聚合

3.4字符串中的第一个唯一字符

内置函数：hashmap.put();hashmap.get();s.charAt();s.length();

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

getOrDefault() 方法的语法为：

hashmap.getOrDefault(Object key, V defaultValue)

注：hashmap 是 HashMap 类的一个对象。

参数说明：

• · key - 键
• · defaultValue - 当指定的key并不存在映射关系中，则返回的该默认值

hashmap.put(ch,hashmap.getOrDefault(ch,0)+1); //hashmap记录频率

时间复杂度： O(n)，其中 n 是字符串 s 的长度。我们需要进行两次遍历。

空间复杂度： O(∣Σ∣)，其中Σ 是字符集，在本题中 s 只包含小写字母，因此∣Σ∣≤26。我们需要 O (∣Σ∣) 的空间存储哈希映射。

3.5两个数组的交集

内置函数:hashmap.remove();Arrays.copyOfRange(res,0,index);

hashmap.put(num,hashmap.getOrDefault(num,0) + 1); //hashmap存储字符出现的次数

Arrays.copyOfRange(res,0,index)

功能：
将数组拷贝至另外一个数组
参数：
res：第一个参数为要拷贝的数组对象
0：第二个参数为拷贝的开始位置（包含）
index：第三个参数为拷贝的结束位置（不包含

分析：将较短长度的数组存入哈希映射，遍历另一个数组得到每一个值(for(int num : nums2))。int count = hashmap.getOrDefault(num,0);

count>0,num存在于nums1和nums2，将hashmap中的num拿一个出来放到结果数组，结果数组多一个，hashmap就少一个。操作完后更新count的值，为零就不需要考虑该num了，否则重复操作。

时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。

空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。

3.6存在重复元素（独立完成）

时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次，对于每个元素，哈希表的操作时间都是O(1)。

空间复杂度：O(n)，其中 n 是数组nums 的长度。需要使用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超过 n。

3.7日志速率限制器

文章

4、实际应用-设计键

4.1字母异位词分组

toCharArray() 方法将字符串转换为字符数组。

语法：

public char[] toCharArray()

参数：无

返回值：字符数组。

values() 方法返回映射中所有 value 组成的 Set 视图。

values() 方法的语法为：

hashmap.values()

注：hashmap 是 HashMap 类的一个对象。

参数说明：无

返回值：返回 HashMap 中所有 value 值所组成的 collection view(集合视图)。

时间复杂度：O(nklogk)，其中 n 是strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序(Arrays.sort()是经过调优排序算法,时间复杂度可以达到O(n*log(n)),而没有经过优化的冒泡排序的平均时间复杂度为O(n^2))以及O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

4.2移位字符串分组

4.3有效的数独

时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。

空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。

5、小结

5.1宝石和石头

独立完成！

内置函数：Set hashset = new HashSet<>(); jewels.length();jewels.charAt(i);hashset.add(ch);hashset.contains(ch)

时间复杂度：O(m+n)，其中 m 是字符串jewels 的长度，n 是字符串stones 的长度。遍历字符串jewels 将其中的字符存储到哈希集合中，时间复杂度是 O(m)，然后遍历字符串 stones，对于stones 中的每个字符在O(1) 的时间内判断当前字符是否是宝石，时间复杂度是 O(n)，因此总时间复杂度是O(m+n)。

空间复杂度：O(m)，其中m 是字符串jewels 的长度。使用哈希集合存储字符串 jewels 中的字符。

5.2无重复字符的最长子串

滑动串口法(双指针法)。

没有遇到重复的字符，右移右指针，遇到重复的字符，右移左指针。两个指针之间的内容就是子串。

内置函数Set hashset = new HashSet<>();hashset.remove(xx);hashset.contains(xx);hashset.contains(xx);s.length()；s.charAt(i-1); length = Math.max(length,hashset.size());

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)[0,128) 内的字符，即∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣个，因此空间复杂度为 O(∣Σ∣)。

5.3四数相加

内置函数：Map hashmap = new HashMap<>();hashmap.put(i+j,hashmap.getOrDefault(i+j,0)+1); hashmap.containsKey(-i-j)；hashmap.get(-i - j)

时间复杂度：O(n^2)。用了两次二重循环，时间复杂度均为 O(n^2) 。在循环中对哈希映射进行的修改以及查询操作的期望时间复杂度均为 O(1)，因此总时间复杂度为 O(n^2)。

空间复杂度：O(n^2)，即为哈希映射需要使用的空间。在最坏的情况下，A[i]+B[j]A[i]+B[j] 的值均不相同，因此值的个数为 n^2，也就需要 O(n^2)的空间。

5.4前k个高频元素

内置函数：

堆操作

排序

简单的做法是给「出现次数数组」排序。但由于可能有 O(N)个不同的出现次数（其中 N为原数组长度），故总的算法复杂度会达到 O(NlogN)，不满足题目的要求。

时间复杂度：O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间。二者之和为 (Nlogk)。

空间复杂度：O(N)。哈希表的大小为)O(N)，而堆的大小为 O(k)，共计为O(N)。

5.5常数时间插入、删除和获取随机元素

变长数组+哈希表：变长数组可以在 O(1)的时间内完成获取随机元素操作，但是不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1) 的时间内完成插入和删除操作，但是不能在O(1) 的时间内完成获取随机元素操作。

内置函数：  List nums;Map indices;Random random；

时间复杂度：初始化和各项操作的时间复杂度都是 O(1)。

空间复杂度： O(n)，其中 n 是集合中的元素个数。存储元素的数组和哈希表需要 O(n) 的空间。

四、树

1、初级算法

树的问题可以由广度优先搜索或深度优先搜索解决。

先序遍历：

1.1二叉树的最大深度

深度优先搜索

在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

时间复杂度： O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度

广度优先搜索

队列首存入根节点，然后遍历每一层的所有元素，每遍历一个取出一个元素(TreeNode node = queue.poll())，遍历完毕去下一层，重复进行。

内置函数：Queue queue = new LinkedList<>();queue.size()；queue.offer(root);

offer，add 区别：

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个unchecked 异常，而只是得到由 offer() 返回的 false。

poll，remove 区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

时间复杂度： O(n)，其中n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。

空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

1.2验证二叉搜索树

迭代

二叉搜索树：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值(isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE))。

时间复杂度：O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)。

空间复杂度：O(n)，其中n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为n ，递归最深达到n 层，故最坏情况下空间复杂度为 O(n)

中序遍历

中序遍历是二叉树的一种遍历方式，它先遍历左子树，再遍历根节点，最后遍历右子树。而二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。

利用上述性质写代码。

内置函数(双端队列Deque)：Deque stack = new LinkedList<>();long low = Long.MIN_VALUE; stack.push(root); root = stack.pop();

push():压入栈；pop():弹出栈

时间复杂度：O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O (n)。

空间复杂度：O(n)，其中n 为二叉树的节点个数。栈最多存储n 个节点，因此需要额外的 O(n)的空间。

1.3对称二叉树

如果一个树的左子树与右子树镜像对称，那么这个树是对称的

递归。

假设树上一共 n 个节点。

时间复杂度：这里遍历了这棵树，渐进时间复杂度为O(n)。

空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

1.4二叉树的层序遍历

广度优先搜索

内置函数：List> res = new ArrayList<>();Queue queue = new LinkedList();queue.offer(root); queue.poll();queue.size();queue.isEmpty()

假设树上一共 n 个节点。

时间复杂度：这里遍历了这棵树，渐进时间复杂度为O(n)。

空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

1.5将有序数组转换为二叉搜索树

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。采用递归。

时间复杂度：O(n)，其中n 是数组的长度。每个数字只访问一次。

空间复杂度： O(logn)，其中n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

五、排序和搜索

1、初级算法

1.1合并两个有序数组

1)内置函数

2)双指针

3)逆序双指针

从后往前按照从大到小往nums1数组添加元素。

时间复杂度：O(m+n)。

指针移动单调递减，最多移动m+n 次，因此时间复杂度为 O(m+n)。

空间复杂度：O(1)。直接对数组nums1原地修改，不需要额外空间。

1.2第一个错误版本

二分法：注意mid不要写错(int mid = left + (right - left) / 2;//核心).

• 时间复杂度：O(logn)，其中 n 是给定版本的数量。
• 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

六、动态规划

1、初级算法

动态规划的几个步骤

1，确定状态

2，找到转移公式

3，确定初始条件以及边界条件

4，计算结果。

1.1爬楼梯

递归：斐波那契数列

动态规划：当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1；当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2；当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)；同理当n等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。

• 时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
• 空间复杂度(优化后)：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

1.2买卖股票的最佳时机

暴力算法：独立完成！超出时间限制。

动态规划：第i天的最大收益只需要知道前i天的最低点就可以算出来了。而第i天以前（包括第i天）的最低点和i-1天的最低点有关，至此我们的动态方程就出来了。

dp[i] = min(d[i-1],prices[i])
其中dp[0]=prices[0],然后动态计算之后的就可以了。得到了前i天的最低点以后，只需要维护一个max用来保存最大收益就可以了。进一步优化后，不需要一个数组来保存数据。

• 时间复杂度：O(n)，只需要遍历一次。
• 空间复杂度(优化后)： O(1)，只使用了常数个变量。

1.3最大子序和

动态规划：

1：定义dp[i]表示数组中下标i为右端点的连续子数组的最大和。

2：如果要计算下标i为右端点的连续子数组的最大和，也就是计算dp[i]，只需要判断dp[i-1]是大于0还是小于0。如果dp[i-1]大于0，就继续累加，dp[i]=dp[i-1]+num[i]。如果dp[i-1]小于0，我们直接把前面的舍弃，也就是说重新开始计算，否则会越加越小的，直接让dp[i]=num[i]。所以转移公式：dp[i]=num[i]+max(dp[i-1],0);同理也可以优化dp[]数组，只用一个临时变量保存数据即可。

• 时间复杂度：O(n)，只需要遍历一次。
• 空间复杂度(优化后)： O(1)，只使用了常数个变量。

1.4打家劫舍

动态规划：对于第k (k>2) 间房屋，有两个选项：偷窃第 k 间房屋，那么就不能偷窃第k−1 间房屋，偷窃总金额为前k−2 间房屋的最高总金额与第k 间房屋的金额之和；不偷窃第 k 间房屋，偷窃总金额为前k−1 间房屋的最高总金额。在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前k 间房屋能偷窃到的最高总金额。

dp[i]=max(dp[i−2]+nums[i],dp[i−1])，优化空间复杂度后：

时间复杂度：O(n)，其中n 是数组长度。只需要对数组遍历一次。

空间复杂度： O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是O(1)。

2、HOT100

LC42接雨水

动态规划

LC62不同路径

动态规划：

时间复杂度：O(m∗n)

空间复杂度：O(m∗n)

LC64最小路径和

动态规划：

时间复杂度 O(M×N) ：遍历整个 grid矩阵元素。

空间复杂度 O(1) ：直接修改原矩阵，不使用额外空间。

LC72编辑距离

动态规划：

时间复杂度 ：O(mn)，其中 m 为 word1 的长度n 为 word2 的长度。

空间复杂度 ：O(mn)，我们需要大小为 O(mn)的数组来记录状态值。

以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符word2[2]）

(2) dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作

(3) dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

七、数学

1、初级算法

1.1Fizz Buzz

枚举

时间复杂度：O(n)。需要遍历从1 到n 的每个整数，对于每个整数i，生成 list[i] 的时间复杂度是 O(1)。

空间复杂度：O(1)。注意返回值不计入空间复杂度。

1.2计算质数

方法一：枚举

时间复杂度：O(n\sqrt{n})。单个数检查的时间复杂度为 O(\sqrt{n})，一共要检查O(n) 个数，因此总时间复杂度为 O(n\sqrt{n}) 。

空间复杂度：O(1)。

方法二：埃氏筛：如果x 是质数，那么大于x 的x 的倍数 如：2x,3x,… 一定不是质数。后续不需要考虑2x,3x,…等数字是否为质数了。节省时间。

内置函数：int[] primes = new int[n];Arrays.fill(primes,1);

1.3 3的幂

试除法

时间复杂度：O(log2n)。当 n 是3 的幂时，需要除以3 的次数为 log_3 n = O(log2n)；当n 不是3 的幂时，需要除以3 的次数小于该值。

空间复杂度： O(1)。

1.4罗马数字转整数

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。

HashMap初始化：

• 时间复杂度：O(n)，其中n 是字符串s 的长度。
• 空间复杂度：O(1)。

八、HOT 100

LC4. 寻找两个正序数组的中位数

时间复杂度：O(log(m+n))，其中m 和n 分别是数组nums 1和nums 2的长度。初始时有 k=(m+n)/2 或k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))。

空间复杂度： O(1)

LC10. 正则表达式匹配

动态规划：字符串 s 和字符规律 p

1、确定状态：dp[i][j]:表示s的前i(s[0]-s[i-1])个字符，p的前j个字符是否能够匹配(数组下标为0，所以i，j下标也是从0开始，但是到s.length和p.length结束，即长度为s.length+1和p.length+1)

2、转移公式：

2.1边界情况(空串)

• p为空串，s不为空串，肯定不匹配。
• s为空串，但p不为空串，要想匹配，只可能是右端是星号，它干掉一个字符后，把 p 变为空串。
• s、p都为空串，肯定匹配。

2.2正常情况

2.2.1文本串(s)和模式串(p)末位字符(s[i-1],j[i-1])能匹配上:dp[i][j] = dp[i -1][j -1]

2.2.2不能匹配

2.2.2.1:j[i-1]不是“*”，返回false

2.2.2.2:j[i-1]==’*’且模式串的前一个字符j[i-2]能够跟文本串的末位匹配上

此时p[j−1] 星号可以让p[j−2] 在p串中消失、出现1 次、出现>=2 次。

只要其中一种使得剩余子串能匹配，那就能匹配，见下图 a1、a2、a3。

2.2.2.3: j[i-1]==’*’且模式串的前一个字符j[i-2]不能跟文本串的末位匹配上

*号代表匹配0次，此时dp[i][j] = dp[i][j-2];

时间复杂度：O(mn)，其中m 和n 分别是字符串s 和p 的长度。我们需要计算出所有的状态，并且每个状态在进行转移时的时间复杂度为O(1)。

空间复杂度：O(mn)，即为存储所有状态使用的空

LC11盛最多水的容器

内置函数：Math.max();

设两指针i , j，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i, j)。由于可容纳水的高度由两板中的 短板 决定，因此可得面积公式 ：S(i, j) = min(h[i], h[j]) × (j - i)

算法流程：

1.初始化： 双指针i , j 分列水槽左右两端；

2.循环收窄： 直至双指针相遇时跳出；更新面积最大值 res ；选定两板高度中的短板，向中间收窄一格；

3.返回值： 返回面积最大值 res 即可；

时间复杂度O(N)​ ：双指针遍历一次底边宽度N​​ 。

空间复杂度O(1)​ ：使用常数额外空间。

LC15三数之和

内置函数：List> res = new ArrayList<>();

Arrays.sort(nums);//从小到大排列res.add(Arrays.asList(nums[i],nums[l],nums[r]));

1. 特判，对于数组长度 n，如果数组为null 或者数组长度小于3，返回[]。
2. 对数组进行排序。
3. 遍历排序后数组：

3.1   若nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。

3.2   对于重复元素：跳过，避免出现重复解

3.3令左指针L=i+1，右指针 R=n−1，当 L

1)当nums[i]+nums[L]+nums[R]==0，加入结果，判断左界和右界是否和下一位置重复，去除重复解。并同时将L,R 移到下一位置，寻找新的解

2)若和大于0，说明nums[R]太大，R 左移

3)若和小于0，说明nums[L]太小，L 右移

时间复杂度：O(n^2)，数组排序O(NlogN)，遍历数组 O(n)，双指针遍历 O(n)，总体O(NlogN)+O(n)∗O(n)，O(n^2)

空间复杂度：O(1)

LC17电话号码的字母组合

时间复杂度：O(3^m * 4^n)，其中m是输入中对应3 个字母的数字个数，n 是输入中对应 44 个字母的数字个数（包括数字7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^m * 4^n种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

LC20有效的括号

栈：

内置函数：Deque stack = new LinkedList<>(); s.charAt(i)；map.containsKey(ch)；map.get(ch)；map.put(')','(');stack.pop();stack.push(ch); stack.isEmpty()； stack.peek()；

时间复杂度：O(n)，其中 n 是字符串s 的长度。

空间复杂度：O(n+∣Σ∣)，其中Σ 表示字符集，本题中字符串只包含6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

LC22括号生成

深度优先遍历：

LC23合并k个排序链表

顺序合并：

分治算法：

LC31下一个排列

算法：1.从后往前，寻找第一个相邻升序对(i,j)

2.找到[j,length-1]中最小的一个大于nums[i]的值

3.交换i，k处的值

4.nums[j,length-1]是降序 改为升序

时间复杂度：O (N)，其中N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。

空间复杂度：O(1)，只需要常数的空间存放若干变量。

LC32最长的有效括号

动态规划：

栈：

LC33搜索旋转排序数组

暴力算法：独立完成

时间复杂度为 O(n)

二分法：

时间复杂度为 O(logn)

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

暴力算法：独立完成

时间复杂度为 O(n)

二分法：

时间复杂度为 O(logn)

LC48旋转图像

辅助矩阵：

对于矩阵中第 i 行的第 j个元素，在旋转后，它出现在倒数第 i列的第 j个位置。

时间复杂度：O(N^2)，其中 N 是matrix 的边长。

空间复杂度：O(N^2)。我们需要使用一个和matrix 大小相同的辅助数组

水平翻转+对角线翻转：

水平翻转：matrix[row][col]--水平轴翻转​--> [n−row−1][col]；主对角线翻转：matrix[row][col]--主对角线翻转-->[col][row]，结果和辅助矩阵相同！

时间复杂度：O(N^2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。

空间复杂度：O(1)。为原地翻转得到的原地旋转

LC55跳跃游戏

贪心算法：

时间复杂度：O(n)，其中n 为数组的大小。只需要访问 nums 数组一遍，共 n个位置。

空间复杂度：O(1)，不需要额外的空间开销。

LC75颜色分类

双指针：

时间复杂度：O(n)

空间复杂度：O(1)

LC77最小覆盖子串

滑动窗口法：

时间复杂度是O(n)

空间复杂度为O(k)，k为S和T中的字符集合。

LC84柱状图中的最大的矩形

单调栈+哨兵：

• 时间复杂度：O(N)，输入数组里的每一个元素入栈一次，出栈一次。
• 空间复杂度：O(N)，栈的空间最多为 N。

LC85最大矩形

求出每一层的 heights[] 然后传给上一题（LC84）的函数就可以了

单调栈：

时间复杂度：O（m*n）。

空间复杂度：O（n）。

LC94二叉树的中序遍历

递归：

时间复杂度：O（n）。

空间复杂度：O（n）。

LC96不同的二叉搜索树

动态规划：

时间复杂度 : O(n^2)，其中 n 表示二叉搜索树的节点个数。

空间复杂度 : O(n)。

LC105从前序与中序遍历序列构造二叉树

递归：

时间复杂度：O(n)，其中 n是树中的节点个数。

空间复杂度：O(n)，返回的答案需要的O(n) 空间之外，还需要O(n) 的空间存储哈希映射，以及O(h)（其中h是树的高度（h

LC114二叉树展开为链表

题解：1)对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点;2) 然后将当前节点的左子节点赋给当前节点的右子节点;3)将当前节点的左子节点设为空;4)查找下一个节点

时间复杂度：O(n)，其中 n是二叉树的节点数。展开为单链表的过程中，需要对每个节点访问一次，在寻找前驱节点的过程中，每个节点最多被额外访问一次。

空间复杂度：O(1)。

LC127二叉树中的最大路径和

递归：

时间复杂度 O(N)，每个节点都要遍历；空间复杂度是 O(H)，递归树的深度。

LC128最长连续序列

独立完成！

LC139单词拆分

dfs:

序列dp：

时间复杂度：将 wordDict 转存在 Set 复杂度为 O(m)；DP 过程复忽裁剪子串和查询 Set 结构的常数，复杂度为 O(n^2)

空间复杂度：O(n + m)

LC146LRU缓存

哈希表+双向链表：

LC148排序链表

暴力算法：单独完成！但是会超时。

归并排序（无递归）：

LC152乘积最大子数组

动态规划：需要同时考虑最大值和最小值。

官方题解：

LC155最小栈

辅助栈：两种方法：辅助栈同步和不同步的情况。

LC160多数元素

官方题解：3种方法：哈希表（独立完成），排序，摩尔投票算法（最好）。

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

hashmap.getOrDefault(Object key, V defaultValue)

LC200岛屿数量

dfs：

LC463岛屿的周长

dfs：岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。注意，这里的非岛屿方格，既包括水域方格，也包括网格的边界。

LC207课程表

拓扑排序：

内置函数：

时间复杂度：O(E +V)。这里 EE表示邻边的条数，V表示结点的个数。初始化入度为 0 的集合需要遍历整张图，具体做法是检查每个结点和每条边，因此复杂度为O(E+V)，然后对该集合进行操作，又需要遍历整张图中的每个结点和每条边，复杂度也为 O(E+V)；

空间复杂度：O(E + V).邻接表长度是V，每个课程里又保存了它所有的边。

使用队列的问题：如果不使用队列，要想得到当前入度为 0的结点，就得遍历一遍入度数组。使用队列即用空间换时间。

LC208实现Trie(前缀树)

TrieNode节点：概念讲解

三叶题解：

时间复杂度：Trie树的每次调用时间复杂度取决于入参字符串的长度。复杂度为 O(Len)。

空间复杂度：结点数量为 n，字符集大小为 k。复杂度为 O(nk)。

LC215数组中第k个最大元素

使用内置函数：独立完成

快排：

LC221最大正方形

动态规划：

• 时间复杂度 O(height * width)
• 空间复杂度 O(height * width)

LC226翻转二叉树

dfs：独立完成！

LC236二叉树的最近公共祖先

dfs：分析不理解。

时间复杂度O(N)：其中N为二叉树节点数；最差情况下，需要递归遍历树的所有节点。

空间复杂度O(N)：最差情况下，递归深度达到N，系统使用O(N)大小的额外空间。

LC238除自身以外的数组的乘积

题解答案：时间复杂度：O(N)，其中 N指的是数组 nums 的大小。

空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。

LC239滑动窗口最大值

单调队列：

内置函数：

 Deque deque = new LinkedList<>();//双向队列deque.isEmpty();deque.peekLast();deque.peekFirst();//检索但不删除队尾（首）元素deque.pollLast();deque.pollFirst();//删除队尾（首）元素deque.offerLast();deque.offerFirst();//在队尾（首）位置添加元素

时间复杂度：O(n)，其中 n是数组nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。

空间复杂度：O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1个元素，因此队列使用的空间为 O(k)。

LC240搜索二维矩阵Ⅱ& LC74搜索二维矩阵

二分查找树：从右上角出发开始遍历。每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。

所以我们可以把 target 和当前值比较。

如果 target 的值大于当前值，那么就向下走。

如果 target 的值小于当前值，那么就向左走。

如果相等的话，直接返回 true 。

时间复杂度：节点最多遍历一遍了，O(m + n)。空间复杂度：O(1)

LC279完全平方数

动态规划：

三叶题解：背包问题

时间复杂度：共有 n * \sqrt{n}个状态需要转移，复杂度为 O(n * \sqrt{n})

空间复杂度：O(n)

LC253会议室Ⅱ

堆，优先队列：

      代码

public int minMeetingRooms(int[][] intervals) {int m = intervals.length;if (m == 0) return 0;//最小堆，队列元素表示会议的结束时间，队首元素为最小值PriorityQueue queue = new PriorityQueue<>(m, (a, b) -> a - b);//按照开始时间从小到大排列Arrays.sort(intervals, (a,b) -> a[0] - b[0]);queue.add(intervals[0][1]);//第一场会议的结束时间for (int i = 1; i < m; i++) {if (intervals[i][0] >= queue.peek()){// 如果当前会议的开始时间大于前面已经开始的会议中最晚结束的时间// 说明有会议室空闲出来了，可以直接重复利用// 所以先队首元素出队，再添加新元素queue.poll();}// 否则的话直接添加新元素queue.add(intervals[i][1]);}return queue.size();}

LC287寻找重复数

二分：

快慢指针：与142.环形链表II类似。

哈希集合：空间超出限制

时间复杂度：O(NlogN)，二分法的时间复杂度为 O(logN)，在二分法的内部，执行了一次 for 循环，时间复杂度为O(N)，故时间复杂度为O(NlogN)。

空间复杂度：O(1)，使用了有限个变量，因此空间复杂度为O(1)。

LC297二叉树的序列化和反序列化

dfs和bfs：

内置函数：

LC300最长递归子序列

动态规划：

LC301删除无效的括号

题解：

LC309最佳买卖股票时机含冷冻期

动态规划以及股票系列问题：

LC312戳气球

动态规划：

LC322零钱兑换

动态规划：

LC337打家劫舍Ⅲ

动态规划+树：

当前节点选择不偷：当前节点能偷到的最大钱数=左孩子能偷到的钱 + 右孩子能偷到的钱

当前节点选择偷：当前节点能偷到的最大钱数=左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数

LC338比特计数

根据奇偶：(i & 1)相当于(i%2)。

hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1；偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多

LC394字符串解码

辅助栈：这里 LinkedList 的作用是栈，应该使用 Stack，更推荐 Java 官方推荐的 Deque

Deque stack_num = new ArrayDeque<>();

LC399除法求值

并查集：

LC406根据身高创建队列

排序：

内置函数：

LC416分隔等和子集（背包问题）

动态规划——背包问题：

LC437路径总和

dfs：

前缀和：

LC438找到字符串当中所有的字母异位词（滑动窗口）

滑动窗口法：

滑动窗口法框架：

LC448找到数组中消失的元素集

题解：

• 时间复杂度：O(n)。其中 n是数组nums的长度。空间复杂度：O(1)。返回值不计入空间复杂度。

哈希表：独立完成！

时间复杂度：O(n)。空间复杂度：O(n)

LC461汉明距离

题解：三种方法

LC494目标和

动态规划：

dfs：独立完成！

LC538二叉搜索树转换为累加树

反中序遍历：

LC671二叉树中第二小的节点

三叶题解：

LC543二叉树的直径

dfs：

LC560和为k的子数组

暴力和前缀和：

LC581最短无连续的子数组

分成三段：

LC621任务调度器

桶思想：

LC647回文子串

动态规划和中心扩展：

LC739每日温度

单调递减栈：

动态规划算法

LC42接雨水

动态规划

时间复杂度为 O(n)

时间复杂度为 O(n)

LC62不同路径

动态规划：

时间复杂度：O(m∗n)

空间复杂度：O(m∗n)

LC64最小路径和

动态规划：

时间复杂度 O(M×N) ：遍历整个 grid矩阵元素。

空间复杂度 O(1) ：直接修改原矩阵，不使用额外空间。

LC72编辑距离

回溯算法

LC39组合总和

寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。

题型一：排列、组合、子集相关问题

提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。

46. 全排列（中等）

47. 全排列 II（中等）

思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；

39. 组合总和（中等）

40. 组合总和 II（中等）

77. 组合（中等）

78. 子集（中等）

90. 子集 II（中等）

剪枝技巧同 47 题、39 题、40 题；

60. 第 k 个排列（中等）

利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；

LC79.单词搜索

偏移量数组在二维平面内是经常使用的，可以把它的设置当做一个技巧。同时使用了used数组和begin

93. 复原 IP 地址（中等）

什么时候使用 used 数组，什么时候使用 begin 变量，这里为大家简单总结一下：

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；

组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

九、代码随想录

1、数组

二分查找

int left = 0;int right = nums.length - 1;while(left <= right){//左闭右闭区间，判断条件需要等号int mid = left + ((right - left) >> 1);//等价于left+(right - left)/2if(nums[mid]

ListNode mid = new ListNode(0,head);//链表ListNode cur = mid;//节点操作

if(i > 0 && nums[i] == nums[i-1]){continue;
}

while(left < right && nums[right] == nums[right-1]){right--;//去重
}
while(left < right && nums[left] == nums[left+1]){left++;//去重
}

//使用内置函数
StringBuilder ans = new StringBuilder();s.toCharArray();ans.append("%20");ans.toString();

//通过队列模拟堆，实现最小堆，堆顶元素是最小的，最先出堆。队头到队尾的顺序是从小到大排
PriorityQueue minStack = new PriorityQueue<>((num1,num2) -> (num1[1] - num2[1]));

// 定制排序的用法，此时从大到小排列
Collections.sort(arrayList, new Comparator() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
});

String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {str = deque.pop() + str;
}
return str;

StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){sb.insert(0, stack.poll());
}
return sb.toString();

String str1 = "123";
//    int num = (int)str1;//错误的
int num = Integer.parseInt(str1);String str2 = String.valueOf(num);//"123"

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len = nums.length;if(len == 1 || k == 1){return nums;}//队尾到对头，从小到大排列//正常添加元素：队尾添加//如果超出窗口，队头删除//窗口最大值：队头元素Deque queue = new ArrayDeque<>();//存储下标int[] ans = new int[len - k + 1];int max = 0;for(int i = 0; i < k; i++){while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){queue.pollLast();}queue.offerLast(i);}//存储第一次窗口的最大值ans[0] = nums[queue.peekFirst()];for(int i = k; i < len; i++){            while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){//正常添加元素，队尾到队头，从小到大queue.pollLast();}queue.offerLast(i);while(!queue.isEmpty() && i - k >= queue.peekFirst()){//超出窗口大小,删除队头queue.pollFirst();}ans[i-k+1] = nums[queue.peekFirst()];}return ans;}
}