1. 两数之和

使用hashmap，记录值和下标，值重复时返回结果

==map中添加nums[i]，则比较时比target-nums[i]==

2. 两数相加

新建一个节点链表来保存结果，两个链表长度不一样，每次循环开始都判空则用0替代

==最后循环结束后还要判断进位值是否是1而再添加一个值为1的节点==

3. 无重复字符的最长子串

使用HashSet，for循环left指针，循环体内while循环right指针add到set中，遇到重复则结束while，在计算max值并remove出left下标的值

==外层for循环循环left指针，内层while循环right指针，内层循环时要先判断right是否越界==

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

1.合并，找位置 O(m+n) O(m+n)

2.不合并，找位置 O(m+n) O(1)

2.二分法 O(log(m+n)) O(1)

二分法把问题转化为找第k小的数

在nums1和nums2中各取k/2，较小的k/2的那一个数组中k/2之前的元素一定都不是要找的第k个元素，故将那个数组中的前k/2个元素删去，此时由于少了k/2个元素，问题又变成找寻第k-k/2小的元素，一直循环重复，直到问题化为找第一小的元素时，返回较小的那一个元素即可

==二分法注意边界问题，当其中一个数组整个数组都不符合条件时，直接返回另一个数组的第k (注意k是在一直变化的) 个元素，或者是当k=1的时候返回较小的数即可==

5. 最长回文子串

动态规划

i==j dp[i][j] = true

i==j+1 dp[i][j] = s[i]==s[j]

else dp[i][j] = dp[i+1][j-1] && s[i]==s[j]

==注意，遍历时应去遍历长度L，在通过i+L-1得出右边界j，因为该题动态规划的转移方程是由内向外转移的，必须先知道内层的值才能推出外层的值，如果直接遍历i,j的话就无法先获得内层的值，从而错误==

==另外遍历也可以不用遍历长度L，可以right从0到len，left从0到right遍历，长度就等于right-left+1==

10. 正则表达式匹配

难

image-20220327203841866

image-20220327203934525

11. 盛最多水的容器

两端双指针，每次移动高度较小的指针

15. 三数之和

双指针 left right

先排序

遍历i从0开始，left从左向右，right从右向左，由于拍过序，小于则移动left，大于移动right

==注意：去重时i应该与前面i-1比，而left和right则是与left+1和right-1比。因为如果i向前比的话i就会从i到i+1，而这样的话left则会少了一次等于i+1的机会，因此i应该与i-1比。left向后比是因为若left向前比的话可能与i重合==

17. 电话号码的字母组合

回溯法

19. 删除链表的倒数第 N 个结点

快慢指针，快指针先走n步，然后慢指针开始出发，快慢指针同时前进，快指针到头时慢指针的位置即为结果（或者用栈）

20. 有效的括号

栈 简单

21. 合并两个有序链表

迭代 、简单 递归玄学

22. 括号生成

23. 合并K个升序链表

方法一：两两合并，使用合并两个升序链表的方法循环合并res和lists[i]

方法二：分治法，也是两两合并

方法三：优先队列，循环，把每个头结点加入queue，弹出的节点为最小节点，再将该节点的next节点add到queue

==注意分治法分割的时候边界为mid与mid+1==

31. 下一个排列

1.先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
2.再找出另一个最大索引 l 满足 nums[l] > nums[k]；
3.交换 nums[l] 和 nums[k]；
4.最后翻转 nums[k+1:]。

32. 最长有效括号

难

33. 搜索旋转排序数组

方法一：先遍历找到k点的位置，k分为左右两个有序数组，判断target在哪边并使用二分法查找

方法二：直接把数组分为两部分，则必有一部分是有序的，判断left，mid，right坐标的值的大小来得出哪边是有序的，再判断target是在有序还是在无序的部分里，从而更新left或right的值，本质还是二分法

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

二分法找到第一个位置，再用二分法找到第二个位置或者从第一个位置开始向后遍历

39. 组合总和

回溯法

==为了方便剪枝，先排序，在回溯过程中遇到sum>target直接break即可==

==元素可以重复选取，所以回溯的index为i==

42. 接雨水

某根柱子能接住的雨水高度为这跟柱子之前最大柱子与之后的最大柱子中的较小的一个减去当前柱子高度

动态规划

求i之前的最大，求i之后的最大，取较小值减去nums[i]，求和

==可以动态规划用两个函数求出dpLeft[]和dpRight[]，再循环遍历==

46. 全排列

回溯

==注意一个树枝上用过的元素不再使用，可以使用used数组标记或者使用path.contains()==

48. 旋转图像

方法一：使用额外一个数组存储旋转的结果，再用两层循环将原数组的值改为翻转后数组的值

方法二：先上下翻转，再沿对角线翻转(转置)

==使用额外的数组的时候应new int一个空的，不能直接等于原数组或者使用clone方法，因为这样的结果都是新建的一个引用，实际引用的对象还是一个数组==

49. 字母异位词分组

使用map将排序的str当做键，未排序的str集合list作value

53. 最大子数组和

动态规划 dp[i] = Math.max(dp[i-1]+nums[i], nums[i])

也可以写为 sum = Math.max(sum+nums[i], nums[i]); maxSum = Math.max(maxSum, sum)

55. 跳跃游戏

动态规划（慢） O(n*n)

贪心O(n)：每次只维护最远能到达的距离

56. 合并区间

先根据每个数组中的第一个值排序Arrays.sort(nums, (o1,o2)->o1[0]-o2[0])，再依次判断并两两合并

62. 不同路径

排列组合：一共要走m+n-2步，其中要向下走m-1步，所以res=C(m-1)(m+n-2)

动态规划：某个点只能是从上面或左边过来的dp[i][j]=dp[i-1][j]+dp[i][j-1]

==动态规划空间优化：dp[j]=dp[j]+dp[j-1]==

==dp[j]表示到当前行、j坐标的路径数，每次只需维护上一行的dp即可，本行的dp根据上一行的dp来更新，dp[j]=dp[j]+dp[j-1]中的左边的dp为当前坐标的dp，右边的dp[j]为上一行j坐标(上面)的dp值(此时dp还未更新，停留在上一行)，dp[i-1]为当前行j-1坐标(左边)的dp值(在上一次已经从上一行更新到了本行)==

64. 最小路径和

动态规划，同62

快速矩阵幂

==注意优化为一维dp数组时，每次循环i时都要更新dp[0] = dp[0] + grid[i][0]，或者专门用一个数组记录第一列的dp值，dp[i-1]会用到==

70. 爬楼梯

斐波那契数列

经典动态规划

矩阵快速幂

数学公式

72. 编辑距离

动态规划

详细如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(一)、当word1[i]==word2[j]时,由于遍历到了i和j,说明word1的0~i-1和word2的0~j-1的匹配结果已经生成,
由于当前两个字符相同,因此无需做任何操作,dp[i][j]=dp[i-1][j-1]
(二)、当word1[i]!=word2[j]时,可以进行的操作有3个:
      ①替换操作:可能word1的0~i-1位置与word2的0~j-1位置的字符都相同,
           只是当前位置的字符不匹配,进行替换操作后两者变得相同,
           所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
      ②删除操作:若此时word1的0~i-1位置与word2的0~j位置已经匹配了,
         此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)
         和word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
      ③插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配,
          此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得
          此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,
          所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)
      ④由于题目所要求的是要最少的操作数:所以当word1[i] != word2[j] 时,
          需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]
(三)总结:状态方程为:
if(word1[i] == word2[j]):
      dp[i][j] = dp[i-1][j-1]
else:
       min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1


PS:大佬的代码中word1.charAt(i-1)==word2.charAt(j-1)的原因是:
     初始化DP Table时dp[i][0]和dp[0][j]已经填写完成,所以接下来填表需要从1开始,
     但是字符的比较需要从0开始,因此才这样子写

75. 颜色分类

方法一：直接排序

方法二：双指针，把0挪到左边，2挪到右边

76. 最小覆盖子串

滑动窗口：可以维护两个map分别记录s和t的字母，并用一个count记录字母种类数，当count==map.size()

78. 子集

回溯法

79. 单词搜索

回溯，向上下左右四个方向搜索并回溯

==搜索时注意越界和被搜索到的节点是否使用过，使用used数组做标记==

84. 柱状图中最大的矩形

暴力解法思路：遍历每个柱子，然后从该柱子向左右蔓延，找到该柱子高度所对应的最大的面积。求最大。

思路：找每个柱子所对应高度的最大面积，该面积的长应为该柱子的高度，宽为该柱子两侧分别第一个小于该柱子高度的柱子的下标的差值。所一每个柱子高度所对应的最大面积为柱子右面第一个小于该柱子高度的下标减去左边第一个小于该柱子高度的下标再乘以该柱子的高度。

思路二：单调栈，构造一个单调递增的栈，遇到递减即为找到了栈顶元素左右的第一小的值，求出宽度即可求面积

==注意单调栈中存放的是下标而不是值，因为宽度需要用下标相减来计算==

94. 二叉树的中序遍历

递归、栈迭代

Morris遍历：本质上是找到当前节点的前驱节点，把前驱节点的right指针指向该节点，遍历时一直遍历right指针即可（空间复杂度降为O(1)）

找前驱节点：root：先到root.left，再一直向右遍历到底即为前驱节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
while(root != null){
    if(root.left != null){
        predecessor = root.left;
        while(predecessor.right != null && predecessor.right != root){
            predecessor = predecessor.right;
        }
        if(predecessor.right == null){
            predecessor.right = root;
            root = root.left;
        } else {
            res.add(root.val);
            //前驱节点右节点置空，不破坏树结构，不置空应该也对
            predecessor.right = null;
            root = root.right;
        }
    } else {
        res.add(root.val);
        root = root.right;
    }
}

96. 不同的二叉搜索树

动态规划：以第i个节点，左子树有i-1个节点，右子树有n-i个节点，故以i为根的二叉搜索树有g(i-1)*g(n-i)

i从1到n遍历求和即的结果

递归：count += numTrees[i-1] * numTrees[n-1]; return count;

递归优化：可能左子树有2个节点已经计算过numTrees(2)的值，当遇到右子树也有2个节点时便会重复计算，耗时，改进方法：每次把numTrees(n)的结果放到一个map中，下次先判断map中是否包含，包含了就直接返回，否则再计算

98. 验证二叉搜索树

递归：isValidBST(TreeNode root, long lower, long upper)

中序遍历，遇到小于上一个数则返回false

101. 对称二叉树

递归：递归左右节点，不符合则false，再递归内层、外层，与操作返回

迭代：借助队列，每次进两个节点，出两个节点，不对称则返回

102. 二叉树的层序遍历

借助队列迭代 BFS

104. 二叉树的最大深度

递归 return Math.max(root.left, root.right)+1;

迭代，层序遍历，记录层数

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

递归，先找前序遍历的第一个节点在中序遍历中的位置index，在中序遍历中index左边的为左子树，右边的为右子树，对应到前序遍历中第一个节点后的 index左边的节点数量 的节点为左子树节点，再往后为右子树节点，每次遍历时额外维护前序序列中左(右)子树的起始位置preLeft和结束位置preRight，还需维护该子树在中序序列中的起始inLeft与结束inRight位置，另外还需维护一个map以便于更快的查找出前序遍历的根节点在中序遍历中的下表位置，否则每次查找都需要遍历。

114. 二叉树展开为链表

使用递归或迭代先遍历二叉树并存在list中，再连接成链表

或者在遍历的过程中链接（只适用于迭代实现）

寻找前驱节点（当前节点左子树的最右节点指向当前节点的右孩子）

121. 买卖股票的最佳时机

贪心，每次记录当前最小，求当前最大

min = Math.min(min, prices[i]); max = Math.max(max, prices[i]-min);

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

递归：每次递归出左子树最大贡献值和右子树最大贡献值，max为左子树最大贡献加上右子树最大贡献值加上当前节点的值

1
2
3
4
5
6
7
8
9
private int getMax(TreeNode root){
    if(root == null){
        return 0;
    }
    int left = Math.max(0, getMax(root.left));
    int right = Math.max(0, getMax(root.right));
    res = Math.max(res, root.val+left+right);
    return Math.max(left, right) + root.val;
}

128. 最长连续序列

排序后双指针

全部放进一个set里，循环判断num++是否在set里（需要确定num是最小值才能得到最大count，因此先判断num-1是否在count，若不在则说明num是最小的，在循环判断num++）

136. 只出现一次的数字

全部异或，结果即为所求

使用hashmap，或使用list，无则+1，有则-1，所剩即所得

139. 单词拆分

动态规划：dp[i]为s的前i个所组成的词在字典里，dp[i] = dp[j] && contains(s.substring(j,i))

另一种作品写法，值记录为true的dp，先dp[0]=0，再遍历i，如果dp[i]=true，即说明i之前的都在字典中可以匹配，再考虑i之后的与字典前缀匹配( s.startsWith(wordDict, i) )，如果匹配上了则记录dp[i+word.length]为true。最后返回最后一个dp即可

141. 环形链表

快慢指针，快指针一次走两步，慢指针一次走一步，如果存在环，则二指针一定会相遇

142. 环形链表 II

同上，先找到相遇点，相遇点到入环点的距离与head到入环点的距离相等，只需在快慢指针相遇时res指针指向头部，然后res和slow指针一起移动，二者相遇的地方就是入环点。

146. LRU 缓存

使用hashmap和双向链表完成

==注意可以设置首尾两个虚拟节点来避免边界问题==

207. 课程表

本质上是判断图中是否有环（有向无环图）

拓扑排序

入度表（BFS）：先构建入度表和邻接表，记录每个节点的入度和该节点下一步能到达的节点，入度为0的进入队列，依次弹出，弹出的节点相当于删去了，因此节点的每一个邻接节点的入度都要减去1，如果减1后的入度为0，则继续入队，直到队列为空即为遍历完毕。

DFS：设置一个flag标志数组，0是没有被遍历过的情况，如果被当前节点遍历则设置为1，如果是被其他节点遍历过设置为0

1
2
3
4
5
6
7
8
9
10
11
12
13
//DFS
private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i){
    if(flags[i] == 1) return false;
    if(flags[i] == -1) return true;
    flags[i] = 1;
    for(int tmp : adjacency.get(i)){
        if(!dfs(adjacency, flags, tmp)){
            return false;
        }
    }
    flags[i] = -1;
    return true;
}

208. 实现 Trie (前缀树)

  • 节点结构
1
2
3
4
5
6
7
8
9
class Trie{
    private boolean isEnd; //记录是否是末尾
    Trie[] next;

    public Trie() {
        isEnd = false;
        next = new Trie[26];
    }
}

234. 回文链表

法一：遍历一遍放到数组里面，首尾双指针比较

法二：使用递归，首先全局记录一个头指针，然后递归到链表尾部，在递归回退的时候是从链表尾部向中部回退，此时同时把全局头指针向后移动并与递归的比较

法三：使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到尾部时慢指针刚好到中间，在快慢指针前进的过程中同时使用两个指针把前半段链表翻转，最后从中间向两边遍历比较即可得到答案

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private ListNode front;
    public boolean isPalindrome(ListNode head) {
        front = head;
        return check(head);
    }
    private boolean check(ListNode cur){
        if(cur != null){
            if(!check(cur.next)){
                return false;
            }
            if(front.val != cur.val){
                return false;
            }
            front = front.next;
        }
        return true;
    }
}

240. 搜索二维矩阵 II

法一：直接暴力

法二：每一行二分法（如果行末元素小于target则直接跳过该行）

法三：从右上角开始遍历，小于就往左走，大于往下走，相等就返回true（类似于二分查找树）