1.两数之和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
链接:https://leetcode-cn.com/problems/two-sum
解读出来的隐藏信息:
- 给定数组不存在重复整数。
- 没说如果不存在对应答案怎么办,那么随便报错或者随便给一个答案都可以。
1 | public class main { |
方法一:暴力法
暴力法很简单,遍历每个元素 xx,并查找是否存在一个值与 target - x 相等的目标元素。
时间复杂度:O(n^2)
空间复杂度:O(1)
1 | class Solution1 { |
方法二:两遍哈希表
为了对运行时间复杂度进行优化,我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在,我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么?哈希表。
通过以空间换取速度的方式,我们可以将查找时间从O(n)降低到 O(1)。哈希表正是为此目的而构建的,它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述,是因为一旦出现冲突,查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数,在哈希表中进行查找的用时应当被摊销为 O(1)。
一个简单的实现使用了两次迭代。在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target - nums[i])是否存在于表中。注意,该目标元素不能是 nums[i]本身!
时间复杂度:O(n)
空间复杂度:O(n)
underscore:下划线
1 | class Solution2 { |
方法三:一遍哈希表
事实证明,我们可以一次完成。在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution3 { |
总结:
该题主要运用了哈希表搜索操作的时间复杂度为O(1)的性质,用哈希表代替暴力搜索,通过空间换时间减小了程序的时间复杂度。
2.两数相加
tips:代码块中的注解、加粗、下划线部分为重点内容。
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
链接:https://leetcode-cn.com/problems/add-two-numbers
1 | public class Main { |
方法:初等数学
就像你在纸上计算两个数字的和那样,我们首先从最低有效位也就是列表 l1 和 l2 的表头开始相加。由于每位数字都应当处于 0…9 的范围内,我们计算两个数字的和时可能会出现 “溢出”。例如,5 + 7 = 12。在这种情况下,我们会将当前位的数值设置为 2,并将进位 carry = 1带入下一次迭代。进位 carry 必定是 0 或 1,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 19。
伪代码如下:
- 将当前结点初始化为返回列表的哑结点。
- 将进位 carry 初始化为 0。
- 将 p和 q分别初始化为列表 l1 和 l2 的头部。
- 遍历列表 l1 和 l2 直至到达它们的尾端。
- 将 x 设为结点 p 的值。如果 p 已经到达 l1 的末尾,则将其值设置为 0。
- 将 y 设为结点 q 的值。如果 q已经到达 l2 的末尾,则将其值设置为 0。
- 设定 sum = x + y + carry。
- 更新进位的值,carry = sum / 10。
- 创建一个数值为(sum mod 10) 的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点。
- 同时,将 p 和 q 前进到下一个结点。
- 检查 carry = 1 是否成立,如果成立,则向返回列表追加一个含有数字 1 的新结点。
- 返回哑结点的下一个结点。
请注意,我们使用哑结点来简化代码。如果没有哑结点,则必须编写额外的条件语句来初始化表头的值。
时间复杂度:O(max(m, n))
空间复杂度:O(max(m, n))
dummy:虚假的
1 | class Solution { |
总结:
- 这道题中就算是每个节点的整数属性都创建了一个新的变量x、y,刷题的时候就是要敢于去多创建变量,帮助自己理清思路,可以在后面理出具体思路之后,再去精简掉一些不必要的变量。
- 做链表相关数据结构时有一个好的方法,就是设置哑节点,这样能帮助我们更快的理清思路,也可以简化很多条件语句代码。
- 重要基础知识:使两个不同对象变量指向同一实例对象,当使用其中一个变量改变对象后,另一个变量再调用该对象时,调用的数据就是改变后的对象数据。
3.无重复字符的最长子串
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
1 | public class Main { |
方法一:滑动窗口
1.思路和算法
我们不妨以示例一中的字符串 abcabcbb 为例,找出 从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。
这样以来,我们就可以使用「滑动窗口」来解决这个问题了:
- 我们使用两个指针表示字符串中的某个子串(的左右边界)。其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的 rk;
- 在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,
- 但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;
在枚举结束后,我们找到的最长的子串的长度即为答案。
2.判断重复字符
在上面的流程中,我们还需要使用一种数据结构来判断 是否有重复的字符,常用的数据结构为哈希集合(即 C++ 中的 std::unordered_set,Java 中的 HashSet,Python 中的 set, JavaScript 中的 Set)。在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。
至此,我们就完美解决了本题。
时间复杂度:O(N)
空间复杂度:O(∣Σ∣),其中∣Σ∣表示字符集的大小
1 | class Solution { |
总结
- String.charAt() 方法用于返回指定字符串索引处的字符。索引范围为从 0 到 length() - 1。
- 在Java中一般我们要运用Map、Set等数据结构时,都是使用他们的实现类HashMap、HashSet。其中Set数据结构常用于存储不可重复的数据。
4.寻找两个正序数组的中位数
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:
输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
示例 4:
输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
1 | public class main { |
方法一:自己写的(迭代)
思路:创建一个新的数组,将原数组中的数值依次比较放入新数组中,合并成一个新的正序数组。
1 | class Solution { |
方法二:二分查找
如果对时间复杂度的要求有log,通常都需要用到二分法,这道题也可以通过二分查找实现。
太过复杂,不再复现,详情见leetcode官网。
总结
- 创建数组的几种写法还是挺重要的,要记牢达到可以直接自己写出来的程度,比如此题中的
(new int[]{0,3,4}, new int[]{1,1,6,7,8})。 - 如果对时间复杂度的要求有log,通常都需要用到二分法。
5.最长回文子串
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
解读传来的隐藏信息:
- 回文串是指这个字符串无论从左读还是从右读,所读的顺序是一样的,简而言之,回文串是左右对称的。
- 单字符字符串也是一个回文串。
1 | public class Main { |
方法一:我自己想出来的(中心扩散法)
思路:主要参考了 这道题的方法,就是抽取每一个字符来进行枚举。对于奇数回文子串,设置两个指针分别从一个字符的两边往外移动,每一对字符都相等才可以继续往外移动。对于偶数回文子串,同样设置两个指针分别从两个相邻相等字符的两边往外移动,每一对字符都相等才可以继续往外移动。最后枚举找出了以每一个字符为中心或者每两个字符为中心的最大回文子串,然后从中找出长度最长的回文子串,即为输入字符串的最长回文子串。
odd:奇数
even:偶数
时间复杂度:O(N^2)
空间复杂度:O(1)
1 | class Solution { |
方法二:暴力法 (Brute Force)
- 根据回文子串的定义,枚举所有长度大于等于 2 的子串,依次判断它们是否是回文;
- 在具体实现时,可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”;
- 在记录最长回文子串的时候,可以只记录“当前子串的起始位置”和“子串长度”,不必做截取。这一步我们放在后面的方法中实现。
说明:暴力解法时间复杂度高,但是思路清晰、编写简单。由于编写正确性的可能性很大,可以使用暴力匹配算法检验我们编写的其它算法是否正确。优化的解法在很多时候,是基于“暴力解法”,以空间换时间得到的,因此思考清楚暴力解法,分析其缺点,很多时候能为我们打开思路。
时间复杂度:O(N^3)
空间复杂度:O(1)
1 | class Solution1 { |
方法三:动态规划
依然从回文串的定义展开讨论:
- 如果一个字符串的头尾两个字符都不相等,那么这个字符串一定不是回文串;
- 如果一个字符串的头尾两个字符相等,才有必要继续判断下去。
- 如果里面的子串是回文,整体就是回文串;
- 如果里面的子串不是回文串,整体就不是回文串。
即:在头尾字符相等的情况下,里面子串的回文性质据定了整个子串的回文性质,这就是状态转移。因此可以把「状态」定义为原字符串的一个子串是否为回文子串。
关键步骤:
- 定义状态:
dp[i][j]表示子串s[i..j]是否为回文子串,这里子串s[i..j]定义为左闭右闭区间,可以取到s[i]和s[j]。 - 定义状态转移方程:
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
时间复杂度:O(N^2)
空间复杂度:O(N^2)
1 | class Solution2 { |
总结:
- String.substring(int i,int j)方法用于截取字符串中索引为i ~ j-1的字符串。
- String.toCharArray()方法用于把字符串分解为字符数组。
- 对于这种找子串的题目,有一种比较常用的思路:对数据中每个元素进行暴力枚举找出要求子串,然后在枚举出的所有子串中比较选出最符合要求的子串输出。
- 刷题时一定要注意边界特殊情况,每次循环时,将索引0、1、end位置的元素代进去看看符不符合要求,不符合要求则单独拿出来用编写特殊语句。
- 刷题时,一般先写好被调用方法,才能完成调用方法的编写,至少一定要先定义好被调用方法的方法名、参数列表、返回值类型。
- 动态规划中的嵌套循环的执行顺序很重要,具体见Solution2中注释。
10.正则表达式匹配(非常重要)
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:
s = “ab”
p = “.*”
输出: true
解释: “.*” 表示可匹配零个或多个(’*’)任意字符(’.’)。
示例 4:
输入:
s = “aab”
p = “c*a*b”
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “mis*is*p*.”
输出: false
链接:https://leetcode-cn.com/problems/regular-expression-matching
1 | public class main { |
方法一:动态规划
动态规划的重要步骤
定义状态:比如本题中用
dp[i][j]来表示长度为i的字符串s和长度为j的正则表达式p是否匹配。思考状态转移方程:也就是由简单状态得到复杂一级状态的计算规则,比如本题中的下图:

初始化边界状态(编写程序时的难点):比如本题中的
dp[0][0]=true和一些特殊的边界情况。
本题思路
使用类似于枚举的暴力法做不出这道题,相比于暴力法,使用动态规划最大的优点就是多出了一个or,可以将.*与任意个字符相匹配的所用情况都囊括进来。
时间复杂度:O(mn),我们需要计算出所有的状态,并且每个状态在进行转移时的时间复杂度为 O(1)。
空间复杂度:O(mn),即为存储所有状态使用的空间。
1 | class Solution1 { |
****总结
- 使用动态规划时,一定要注意二维数组角标的含义,本题中
dp[0][0]表示长度都为0的两个字符串的匹配结果,所以dp[m][n]才是表示长度为m、n的两个字符串的匹配结果。 - boolean初始构造函数默认赋值为false。
- 动态规划的本质就是从最开始的,最容易得到的边界状态值,遵循相同的规则不断由下向上计算得出最终值。
- 考虑边界状态时,一定要注意到边界
dp[0][j]并不全部都是false。当s为空,p为一个字符加上*时也是匹配的这种特殊情况。 - 本题中的or非常重要,通过这个or可以将
.*与任意个字符相匹配的所用情况都囊括进来,这也是这道题一定要用动态规划的原因。
11.盛最多水的容器
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
示例:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
链接:https://leetcode-cn.com/problems/container-with-most-water
1 | public class Main { |
方法一:我自己写的(暴力法)
按顺序已每个数为左边,它右边的每个数再按顺序为右边,枚举出所有面积值,比较选出最大的。
时间复杂度:O(N^2)
空间复杂度:O(1)
1 | class Solution { |
方法二:双指针
在初始时,左右指针分别指向数组的左右两端,计算出盛水面积。
此时我们需要移动一个指针。移动哪一个呢?应该移动对应数字较小的那个指针,因为由于容纳的水量是由两个指针指向的数字中较小值 * 指针之间的距离决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」只可能减小,不可能增加,后者「指针之间的距离」会减小,那么这个乘积只能减小。因此,我们移动数字较小的那个指针,盛水面积才有可能增大。
重复以上步骤,直到两个指针重合,比较选择出最大的盛水面积。
时间复杂度:O(N)
空间复杂度:O(1)
1 | class Solution1 { |
15.三数之和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
链接:https://leetcode-cn.com/problems/3sum
1 | public class Main { |
方法一:排序+三重循环
1 | class Solution { |
方法二:排序+双指针(自己写的)
自己写的,但是写错了,不是真的双指针,主要用来与方法三进行对比,方便理解双指针的方法。
1 | class Solution1 { |
方法三:排序+双指针
1 | class Solution2 { |
总结:
- 工具类Arrays的sort()方法可用对多种数据类型数组按默认规则或者自定义规则排序。
- 三重循环可用于枚举三元素数组。
- 双指针法中左、右指针的定义一定要放在循环的外面,且一旦左右指针相遇就要停止循环。
17.电话号码的字母组合
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:
输入:”23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
1 | public class Main { |
方法一:递归回溯法(自己写的)
分析易得该题的答案输出模式为:在上一步的基础之上添加几种可能形成下一级,通过这种方式逐渐增多。
这种模式一下子就想到了22.括号生成中使用过的递归回溯法。
1 | class Solution { |
方法二:递归回溯法
官方版本,主要就是使用了哈希表,使写法更加简便。
1 | class Solution1 { |
总结:
- 递归回溯法很重要很好用,一定要背出编写过程。
- ArrayList()构造方法默认创建的动态数组就是[],表示内部不含任何子元素,但该动态数组也不是null。注意stringList=[]和stringList=null的意义是完全不一样:第一个表示该动态数组变量指向在内存中真实存在的数据,只不过该动态数组内部还没有存储元素;第二个表示该动态数组变量根本不指向真正存在的内存数据。
- 刷题时Map的实现类一般就用HashMap。
19.删除链表的倒数第N个节点
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:你能尝试使用一趟扫描实现吗?
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
1 | class ListNode { |
方法一:快慢指针(自己写的)
思路:留一个滞后指针,前置指针先走,走到一定位置后,两个指针再同速前行,使得前置指针到达链表末尾时,滞后指针刚好指在需要删除节点的前一个节点。
时间复杂度:O(n)
空间复杂度:O(0)
1 | class Solution { |
方法二:栈
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则,我们弹出栈的第 n 个节点就是需要删除的节点,并且目前栈顶的节点就是待删除节点的前驱节点。这样一来,删除操作就变得十分方便了。
1 | class Solution1 { |
总结:
- 无论是什么时候都要考虑边界特殊情况。
- 考虑倒数相关问题时,可以先想一下能不能使用栈来解决。
20.有效的括号
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
链接:https://leetcode-cn.com/problems/valid-parentheses
1 | public class Main { |
方法一:自己写的(栈)
将字符串中字符一个一个放到栈中,当遇到成对的括号就一起出栈,看最后栈是否为空,为空则说明符合要求,不为空则说明不符合要求。
1 | class Solution { |
方法二:栈+哈希表
我们对给定的字符串 s 进行遍历,当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 s 无效,返回 False。为了快速判断括号的类型,我们可以使用哈希映射(HashMap)存储每一种括号。哈希映射的键为右括号,值为相同类型的左括号。
时间复杂度:O(n)
空间复杂度:O(n+∣Σ∣),其中Σ 表示字符集中不同字符个数
1 | class Solution1 { |
总结
- 跳过本次循环,继续下一次循环用continue;跳出循环用break。
- Stack.peek()方法运行时栈不能为空,否则会报错。
- char没有equals()方法,Character才有;这两种数据类型都不能用==、!=等比较运算符。
- Character.equals()方法的输入参数一定要是单引号表示字符,如果是双引号会被识别成字符串,该方法会直接返回false。
- 遍历输入字符串中字符,只要遇到了右括号,它必须马上和栈顶元素匹配闭合相消,这样才可能是true,一旦有一个右括号没有和栈定元素闭合就是false了。
21.合并两个有序链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists
方法一:递归法
我们可以如下递归地定义两个链表里的 merge 操作(忽略边界情况,比如空链表等):

也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
同时需要考虑边界情况,如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。
时间复杂度:O(n + m),其中 nn 和 mm 分别为两个链表的长度。
空间复杂度:O(n + m)
1 | class Solution1 { |
方法二:迭代法
我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。
时间复杂度:O(n + m)
空间复杂度:O(1)
1 | class Solution { |
总结:
- 方法的输入参数,比如本题中的l1、l2是可以改变的,比如本题中
l1=l1.next;,这样可以少定义几个节点变量,减少空间复杂度。
- 递归法只要递归模型建立好了,就不用去考虑内部运行机制了。就像这道题,已经知道要用递归法的情况下,我还在思考递归函数内部的while循环方法怎么写,这个思路明显就是错了,都已经用递归了,当然就不需要用循环了,也不需要再考虑内部执行机制了。
- 递归法其实最重要的或者说最难的一点,是边界情况的编写或特殊情况的编写,比如此处的一条链表到尾端时的处理,通过条件语句判断出来。一般边界情况要尽量编写的简练。
- 迭代法中又用到了哑节点的概念,一般涉及到链表的题目,要返回链表时,都是通过设置哑节点,返回哑节点的下一个节点。
22.括号生成
tips:代码块中的注解、加粗、下划线部分为重点内容。
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。
示例:
输入:n = 3
输出:[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
链接:https://leetcode-cn.com/problems/generate-parentheses
方法一:暴力法
枚举所有种类的字符数组,共2^2n种,检验出其中有效的,放入结果数组中。
这种思路的关键部分是,每个位置只能是(或)这两种,那么我们要枚举所有字符串的方法就是从null开始,在字符串后添加一个(或),然后又在每一种情况下,在字符串后添加一个(或),一直递归,直到字符串长度达到预期长度。
时间复杂度:O((2^2n)n)
空间复杂度:O(n)
1 | class Solution { |
小结
public void generateString(char[] charList,int nowLength,List<String> stringList)该方法中:- 第一个参数最初为一个空的字符串数组,主要用来提供字符串预期长度,并给不断添加左右括号的字符数组提供一个载体;
- 第二个参数表示现在字符数组中已经添加了几个左右括号字符了;
- 第三个参数主要为枚举结果提供一个载体,一般不会在递归函数中创建新的变量,一般先在递归函数外面定义好变量,将该变量作为参数传入递归函数,由递归函数改变它,递归函数也可以通过这种方式传出运行结果。
一种新的检验括号字符串是否有效的方法:
- 每一个包含第一个括号的子序列中左括号个数不能小于右括号个数,因为无论后面再加上多少个左括号,都不能和前面多出来的右括号配对相消。
- 总的左右括号个数一定要相等。
只要满足以上两个条件,就是有效括号字符串。
方法二:回溯法
方法一还有改进的余地:我们可以只在序列仍然保持有效时才添加 ( 或 ),而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点:
- 如果左括号数量不大于 n,我们可以放一个左括号。
- 如果右括号数量小于左括号的数量,我们可以放一个右括号。
以上两个条件优先级相同,一个字符串同时满足就分裂成两种情况。
这个思路本质上其实就是设定一种左右括号添加顺序的规则,使得遵守这种括号添加规则的字符串到最后都是有效的。
时间复杂度:O((4^n)/sqrt(n))
空间复杂度:O(n)
我自己照这个思路在方法一的基础上写的:
1 | class Solution1 { |
力扣官方答案:
1 | class Solution2 { |
小结:
- 注意我自己写的和官方两种递归方法的差别:
- 我自己写的递归方法中,是没有在递归终止语句后面加上return的,其实这两种写法中,加不加都无所谓,效果是一样的。但是我们要知道区别,如果不加return,则要通过条件语句确保递归终止语句后面的代码不会再执行了。
- (非常重要)官方方法中,后面两个包含递归方法的if代码块中是通过添加
cur.append('(');来改变字符串的,执行第一个代码块时,从递归方法中出来后必须先把添加的字符去掉cur.deleteCharAt(cur.length() - 1);,再进入第二个代码块中执行添加操作;而我自己写的方法是直接给该索引位置的字符重新赋值charList[leftNumber+rightNumber] = ')';,所以不用先删掉之前添加的字符,重新赋值会直接覆盖原来的字符。
方法三:动态规划递归(还没自己实现)
任何一个括号序列都一定是由(开头,并且第一个(一定有一个唯一与之对应的)。这样一来,每一个括号序列可以用(a)b来表示,其中a与b分别是一个合法的括号序列(可以为空)。
那么,要生成所有长度为2*n的括号序列,我们定义一个函数方法generate(n)来返回所有可能的括号序列。那么在函数 generate(n) 的过程中:
- 我们需要枚举与第一个 ( 对应的 ) 的位置 2 * i + 1;
- 递归调用 generate(i) 即可计算 a 的所有可能性;
- 递归调用 generate(n - i - 1) 即可计算 b 的所有可能性;
- 遍历 a 与 b 的所有可能性并拼接,即可得到所有长度为 2 * n 的括号序列。
为了节省计算时间,我们在每次 generate(i) 函数返回之前,把返回值存储起来,下次再调用 generate(i) 时可以直接返回,不需要再递归计算。
时间复杂度:O((4^n)/sqrt(n))
空间复杂度:O((4^n)/sqrt(n))
1 | class Solution3 { |
23.合并K个升序链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2:
输入:lists = []
输出:[]
示例 3:
输入:lists = [[]]
输出:[]
链接:https://leetcode-cn.com/problems/merge-k-sorted-lists
1 | class ListNode { |
方法一:递归+顺序合并(自己写的)
思路:使用递归法合并两个升序链表,然后一个个将剩下的链表按同样的方法合并进来。
1 | class Solution { |
总结:
- 递归和迭代的时间复杂度相同,迭代空间复杂度比递归低。
31.下一个排列
tips:代码块中的注解、加粗、下划线部分为重点内容。
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
链接:https://leetcode-cn.com/problems/next-permutation
1 | public class Main { |
字典序大小:不同排列的大小关系是从左到右逐个比较对应的数字的先后来决定的。其实就是从左到右依次比较每一位上的字符,一旦比较出大小不同则在该位上大的序列大于另一个序列。例如对于5个数字的排列 12354和12345,排列12345小于12354。按照这样的规定,5个数字的所有的排列中最小的是12345,最大的是 54321。
方法一:一边扫描+栈
我们需要从右边找到第一对两个连续的数字 a[i] 和 a[i-1],它们满足 a[i]>a[i-1]。现在,没有对 a[i-1]右侧的重新排列可以创建更大的排列,因为该子数组由数字按降序组成。因此,我们只需要重新排列 a[i-1] 右边的数字,包括它自己。
我们想要创建比当前更大的排列。因此,我们需要将数字 a[i-1] 替换为位于其右侧区域的数字中比它更大的数字中最小的数字a[j]。

我们交换数字 a[i-1]和 a[j]。我们现在在索引i-1处有正确的数字。但目前的排列仍然不是我们正在寻找的排列。我们需要通过仅使用 a[i-1]右边的数字来形成最小的排列。 因此,我们需要放置那些按升序排列的数字,以获得最小的排列。
但是,请记住,在从右侧扫描数字时,我们只是继续递减索引直到我们找到 a[i]和 a[i-1] 这对数。其中,a[i] > a[i-1]。因此,a[i-1]右边的所有数字都已按降序排序。此外,交换 a[i-1]和 a[j]并未改变该顺序。因此,我们只需要反转 a[i-1]之后的数字,以获得下一个最小的字典排列。
1 | class Solution1 { |
32.最长有效括号
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
链接:https://leetcode-cn.com/problems/longest-valid-parentheses
1 | public class Main { |
方法一:枚举+栈(自己写的)
不太行,方法上感觉没问题,但是超出了时间限制。
1 | class Solution { |
非常重要的总结:
判断括号字符串是否有效的方法:
- 栈
- 同时满足以下两个条件:
- 每一个包含第一个括号的子序列中左括号个数不能小于右括号个数,因为无论后面再加上多少个左括号,都不能和前面多出来的右括号配对相消。
- 总的左右括号个数一定要相等。
方法三、方法四也正是有这两种方法衍生出来的。
方法二:动态规划
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution1 { |
方法三:栈
重要:栈底必须放置当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」,这样才能计算出最长有效括号子串的长度。也就是说除了栈底,栈中其他元素只能是右括号的下标。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution2 { |
方法四:判断括号字符串有效的两个条件
重要:从左往右遍历一遍之后,还有从右往左遍历一遍。因为如果只从左往右遍历一遍,则会忽略掉左括号数量永远大于右括号数量这种情况中的有效括号子串。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution3 { |
总结:
非常重要:本题是有效括号题的典范。
33.搜索旋转排序数组
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个升序排列的整数数组 nums ,和一个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
1 | public class Main { |
方法一:二分搜索
可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。拿示例来看,我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分,其中左边 [4, 5, 6] 这个部分的数组是有序的,其他也是如此。
这启示我们可以在常规二分搜索的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分搜索的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:
- 如果 [l, mid - 1] 是有序数组,且 target 的大小满足[nums[l],nums[mid]),则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。
- 如果 [mid, r] 是有序数组,且 target 的大小满足(nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。
时间复杂度:O(logn)
空间复杂度:O(1)
1 | class Solution1 { |
总结:
非常重要:代码块中的注释标注了使用二分搜索法要注意的细节,这是本题的重中之重。
34.在排序数组中查找元素的第一个和最后一个位置
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
1 | public class Main { |
方法一:二分搜索
本题最重要、最关键的思路:分成两步分别去思考,先二分查找左边界位置,再二分查找右边界位置。
时间复杂度:O(logn)
空间复杂度:O(1)
1 | class Solution { |
总结:
还是代码段中的注释很重要,注意使用二分法时的等号细节。
39.组合总和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
其中candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入:candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
链接:https://leetcode-cn.com/problems/combination-sum
方法一:递归回溯法
思路:看到这种要生成多种可能的组合的题目,首先就要考虑一下递归法和递归回溯法。
递归回溯法和递归法还是有一些区别的,回溯法是在递归法的基础之上增加回溯,使得可以重复使用同一个引用对象。
时间复杂度:O(S),其中 S 为所有可行解的长度之和。
空间复杂度:O(target)。(复杂度给出的都是最坏情况)
1 | class Solution { |
42.接雨水
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
链接:https://leetcode-cn.com/problems/trapping-rain-water
方法一:暴力法
既然想不出巧妙的简便方法,打算用暴力法,那么就先思考最暴力的方法,思考最直接的方法。比如此处就思考每一个格子上方盛的水是多少,而不要再去考虑每一个倒三角小水坑怎么得到。每一个格子上方盛的水取决于该格子两边最高的格子中相对较低的那一个。
时间复杂度:O(n^2)
空间复杂度:O(1)
1 | class Solution { |
方法二:动态编程
暴力法的简化,典型的空间换时间,把二重循环编程一重循环。思路就是遍历找出数组中每个数左边(包括该数自己)的最大值,再遍历找出数组中每个数右边的最大值。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution1 { |
方法三:栈
方法四:双指针
后两种方法太难理解了,也太难想到了。
46.全排列
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
链接:https://leetcode-cn.com/problems/permutations
1 | public class Main { |
方法一:回溯法
时间复杂度:O(n*n!),getPermute()的调用次数O(n!) 的,而对于getPermute()调用的每个叶结点(共n!个),我们需要将当前答案使用O(n)的时间复制到答案数组中,相乘得时间复杂度为O(n*n!)。
空间复杂度:O(n),要为每一层递归分配栈空间,这里所需要的额外空间取决于递归的深度,最深递归n层。
1 | class Solution { |
48.旋转图像
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明:
你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
链接:https://leetcode-cn.com/problems/rotate-image
方法一:自己写的
旋转四个等腰三角形,注意一下边界,每个等腰三角形只包括一条等腰边,矩形中心不用考虑。
1 | class Solution { |
49.字母异位词分组
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
链接:https://leetcode-cn.com/problems/group-anagrams
1 | public class Main { |
方法一:排序数组分类
思路:当且仅当它们的排序字符串相等时,两个字符串是字母异位词。
重要:哈希表是一个很好的工具,力扣题中经常使用。在需要用一个标志代表一组具有某种共性的数据时就使用哈希表。
1 | class Solution { |
方法二:按字符计数分类
思路:计算出字符串中每个字符出现的次数,当且仅当它们的字符计数(每个字符的出现次数)相同时,两个字符串是字母异位词。
在Java中,我们的字符数量count的散列化表示将是一个用#字符分隔的字符串。例如,abbccc将表示为#1#2#3#0#0#0...#0,其中总共有26个条目。
该思路和方法同样可以扩展到计算数字字符或者大写字母字符的出现次数计算。
1 | class Solution1 { |
53.最大子序和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
链接:https://leetcode-cn.com/problems/maximum-subarray
方法一:动态规划
思路:定义状态f[i]为以索引i位置数为尾端的所有连续子序列中,和最大的那个连续子序列的和。
(状态转移方程非常巧妙,比较难想,只能硬记这道题)
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
55.跳跃游戏
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
链接:https://leetcode-cn.com/problems/jump-game
方法一:递归回溯法
思路:看到这种可以每一个步骤可以跳一步、两步、三步等不确定步数时,一下就想到了递归回溯法。
1 | //非常重要:List<>这种类型的对象引用变量才可以作为回溯方法的一个参数,来标志回溯到终点是否满足要求。 |
1 | //非常重要: |
方法二:贪心法
只要存在一个位置 x,它本身可以到达,并且它跳跃的最大长度为x+nums[x],这个值大于等于 y,即x+nums[x]≥y,那么位置 y 也可以到达。
换句话说,对于每一个可以到达的位置x,它使得x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。
这样一来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的位置。对于当前遍历到的位置 x,如果它在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用x+nums[x] 更新最远可以到达的位置。
在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回True作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回False作为答案。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution2 { |
56.合并区间
tips:代码块中的注解、加粗、下划线部分为重点内容。
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
链接:https://leetcode-cn.com/problems/merge-intervals
方法一:排序
思路:一定要先将所有的区间按左端点的大小进行排序,这样才能保证可以合并的区间是连续的。
然后就好办了,依次判断每两个连续的区间是否需要合并。
1 | class Solution { |
62.不同路径
tips:代码块中的注解、加粗、下划线部分为重点内容。
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
链接:https://leetcode-cn.com/problems/unique-paths
方法一:递归回溯法
可以是可以,但是十分浪费内存,效率很低,远不如动态规划。
1 | class Solution { |
方法二:动态规划
这种最后要求我们只是输出种数的问题,且每一层的种数与上一层的种数密切相关的情况,完全可以用动态规划来代替递归回溯。
时间复杂度:O(mn)
空间复杂度:O(mn)
1 | class Solution1 { |
64.最小路径和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
链接:https://leetcode-cn.com/problems/minimum-path-sum
方法一:动态规划
在62.不同路径上的基础之上做出一些改进即可。
时间复杂度:O(mn)
空间复杂度:O(mn)
1 | class Solution { |
70.爬楼梯
tips:代码块中的注解、加粗、下划线部分为重点内容。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
链接:https://leetcode-cn.com/problems/climbing-stairs
方法一:动态规划
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
方法二:动态规划
思路:其实状态转移方程每次只需要使用前两个状态,之后再也不用使用到前面的状态。那么完全可以降低动态规划的空间复杂度。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution1 { |
72.编辑距离
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入:word1 = “horse”, word2 = “ros”
输出:3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:
输入:word1 = “intention”, word2 = “execution”
输出:5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
链接:https://leetcode-cn.com/problems/edit-distance
方法一:动态规划
这真的想不到了,只能硬背思路了。
我们可以对任意一个单词进行三种操作:
- 插入一个字符;
- 删除一个字符;
- 替换一个字符。
题目给定了两个单词,设为 A 和 B,这样我们就能够六种操作方法。
但我们可以发现,如果我们有单词 A 和单词 B:
- 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge,单词 B 为 dog 时,我们既可以删除单词 A 的最后一个字符 e,得到相同的 dog,也可以在单词 B 末尾添加一个字符 e,得到相同的 doge;
- 同理,对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的;
- 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat,单词 B 为 cat 时,我们修改单词 A 的第一个字母 b -> c,和修改单词 B 的第一个字母 c -> b 是等价的。
这样以来,本质不同的操作实际上只有三种:
- 在单词 A 中插入一个字符;
- 在单词 B 中插入一个字符;
- 修改单词 A 的一个字符。
这样一来,我们就可以把原问题转化为规模较小的子问题。我们用 A = horse,B = ros 作为例子,来看一看是如何把这个问题转化为规模较小的若干子问题的。
- 在单词 A 中插入一个字符:如果我们知道 horse 到 ro 的编辑距离为 a,那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串,只需要额外的 1 次操作,在单词 A 的末尾添加字符 s,就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串;
- 在单词 B 中插入一个字符:如果我们知道 hors 到 ros 的编辑距离为 b,那么显然 horse 到 ros 的编辑距离不会超过 b + 1,原因同上;
- 修改单词 A 的一个字符:如果我们知道 hors 到 ro 的编辑距离为 c,那么显然 horse 到 ros 的编辑距离不会超过 c + 1,原因同上。
那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)。
注意:为什么我们总是在单词 A 和 B 的末尾插入或者修改字符,能不能在其它的地方进行操作呢?答案是可以的,但是我们知道,操作的顺序是不影响最终的结果的。例如对于单词 cat,我们希望在 c 和 a 之间添加字符 d 并且将字符 t 修改为字符 b,那么这两个操作无论为什么顺序,都会得到最终的结果 cdab。
你可能觉得 horse 到 ro 这个问题也很难解决。但是没关系,我们可以继续用上面的方法拆分这个问题,对于这个问题拆分出来的所有子问题,我们也可以继续拆分,直到:
- 字符串 A 为空,如从 转换到 ro,显然编辑距离为字符串 B 的长度,这里是 2;
- 字符串 B 为空,如从 horse 转换到 ,显然编辑距离为字符串 A 的长度,这里是 5。
因此,我们就可以使用动态规划来解决这个问题了。我们用 D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
如上所述,当我们获得 D[i][j-1],D[i-1][j] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。
- D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符,我们在 A 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i][j-1] + 1;
- D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符,我们在 B 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i-1][j] + 1;
- D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符,我们修改 A 的第 i 个字符使它们相同,那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地,如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同,那么我们实际上不需要进行修改操作。在这种情况下,D[i][j] 最小可以为 D[i-1][j-1]。
那么我们可以写出如下的状态转移方程:
若 A 和 B 的最后一个字母相同:
D[i][j]=min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1])=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)
若 A 和 B 的最后一个字母不同:
D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])
对于边界情况,一个空串和一个非空串的编辑距离为 D[i][0] = i 和 D[0][j] = j,D[i][0] 相当于对 word1 执行 i 次删除操作,D[0][j] 相当于对 word1执行 j 次插入操作。
综上我们得到了算法的全部流程。
时间复杂度:O(mn)
空间复杂度:O(mn)
1 | class Solution { |
总结
- 和10.正则表达式匹配一样,这种涉及到字符串比较,包括字符顺序比较的题目,一般都是用动态规划。而像49.字母异位词分组这种不涉及顺序比较的字符串比较,则可以直接枚举出每个字符的出现次数来比较。
75.颜色分类
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
进阶:
你可以不使用代码库中的排序函数来解决这道题吗?
你能想出一个仅使用常数空间的一趟扫描算法吗?
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1]
输出:[0,1,2]
示例 3:
输入:nums = [0]
输出:[0]
示例 4:
输入:nums = [1]
输出:[1]
链接:https://leetcode-cn.com/problems/sort-colors
方法一:暴力法
思路:一次遍历计算出每种颜色的个数,二次遍历给数组重新赋值
1 | class Solution { |
方法二:双指针
思路:分别设置指针表示头部和尾部,遍历数组,当数据为0时与头部位置交换,并将头部位置后移一位;当数据为2时与尾部位置交换,并将尾部位置前移一位,同时重新遍历一次该位置。也就是说要保证头部位置以前全是0,尾部位置以后全是2。
1 | class Solution1 { |
总结
双指针可以用于减少遍历次数。
76.最小覆盖子串
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:本题要考虑t中相同字符的个数;如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
示例 2:
输入:s = “a”, t = “a”
输出:”a”
链接:https://leetcode-cn.com/problems/minimum-window-substring
方法一:滑动窗口法
思路
设置左右两个指针:
- 右指针一直后移,直到两指针之间涵盖t中所有字符;
- 这时再后移左指针,直到两指针之间不再涵盖t中所有字符;
- 这时再后移右指针,如此循环,直到找出两指针之间涵盖t中所有字符的情况中两指针距离最小的情况。
以上想到的这个思路是正确的,就是编程实现起来不太容易,实现形式也可以有很多种,自己要记住一种能自己写出来。
步骤
以上思路更准确的步骤描述:
- 不断增加right使滑动窗口增大,直到窗口包含了t的所有元素;
- 不断增加left使滑动窗口缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值;
- 让left再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从步骤一开始执行,寻找新的满足条件的滑动窗口,如此反复,直到right超出了字符串S范围。(这一步很重要且很容易忽略)
1 | class Solution { |
78.子集
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
链接:https://leetcode-cn.com/problems/subsets
方法一:递归回溯
非常重要:这个递归回溯的特点就是:不考虑顺序。
之前的递归回溯,一般都是要考虑每个元素的顺序,注意这个不考虑顺序的递归回溯是如何避免选取到元素相同、顺序不同的列表元素的。
1 | class Solution { |
79.单词搜索
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false
链接:https://leetcode-cn.com/problems/word-search
方法一:深度优先搜索
这道题本质上其实也是递归回溯法,但是不同于之前一直用的递归函数定义方法,之前一直定义递归函数方法返回值类型为void,这里要定义递归函数返回值类型为每一层递归的判断结果boolean。
这里深度优先搜索体现在先不管结果如何,一直往下递归,到递归终止条件再返回,只有每一层的返回值都为true,才会使最外层递归方法的返回值也为true。
1 | class Solution { |
84.柱状图中最大的矩形
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例:
输入: [2,1,5,6,2,3]
输出: 10
链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram
方法一:暴力法
找出每个柱形所对应的以此柱为最高柱的矩形,思路就是找出每个柱形两边第一个比该柱低的柱形。
1 | class Solution { |
方法二:单调栈
空间换时间,将二重循环转化成一重循环。
思路:维护一个单调栈,通过单调栈可以一次遍历找出每个柱行左边第一个小于他的柱行的位置,再通过一次遍历找出右边第一个小于他的柱行的位置。
1 | class Solution1 { |
总结
这道题其实和42.接雨水很像,方法一暴力法都是枚举每一个柱形作为高,方法二都是在方法一暴力法的基础上空间换时间。
85.最大矩形
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例 1:
输入:matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出:6
解释:最大矩形如上图所示。
链接:https://leetcode-cn.com/problems/maximal-rectangle
方法一:柱状图_枚举高暴力法+动态规划
思路:对每一行建立柱状图,也就是分别研究矩阵的每一行作为矩形的底时所能求到的最大矩形,所以每次对一行建立柱状图时,只需考虑该行及其上方的格子。
同时用动态规划求出每个字符为1的格子与其上方字符为1的格子共同构成的最大高度。
时间复杂度:O(n^2*m)
空间复杂度:O(n*m)
1 | class Solution { |
方法二:柱状图_枚举高单调栈优化+动态规划优化
思路:在使用单调栈优化求解柱状图最大矩形的基础上。另外其实动态规划也可以优化,因为每求一行的状态时,只需用到上一行的状态,用完就不再需要,所以动态规划状态可以从二维优化为一维。所以其实这种方法比第一种在时间和空间上复杂度都减小了。
时间复杂度:O(n*m)
空间复杂度:O(m)
1 | class Solution1 { |
总结
其实本题就是一个84.柱状图中最大的矩形的二维展开,在84题的每种方法上都可以扩展衍生出该题对应的方法,比如84题主要有三种方法:枚举宽暴力法、枚举高暴力法、枚举高单调栈优化,本题中我们选择后两种方法来进行二维扩展。
94.二叉树的中序遍历
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树的根节点root,返回它的中序遍历。
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
方法一:递归
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
方法二:栈
二叉树的前中后序遍历除了递归方法,都可以用栈来进行迭代遍历出来。
中序遍历思路:当每个节点有左子节点时,先不遍历该节点,将该节点放入栈中,直到找到没有左子节点的节点,再开始遍历节点,然后查看该节点有无右子节点,如有则重复上述步骤。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution1 { |
96.不同的二叉搜索树
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
链接:https://leetcode-cn.com/problems/unique-binary-search-trees
方法一:动态规划
状态:
G(n):长度为 n 的序列能构成的不同二叉搜索树的个数。
F(i, n):以i为根、序列长度为 n 的不同二叉搜索树个数(1≤i≤n)。
状态转移方程:



时间复杂度:O(n^2)
空间复杂度:O(n)
1 | class Solution { |
98.验证二叉搜索树
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
链接:https://leetcode-cn.com/problems/validate-binary-search-tree
方法一:中序遍历
思路:二叉搜索树中序遍历结果为单调递增或者单调递减。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
101.对称二叉树
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3
链接:https://leetcode-cn.com/problems/symmetric-tree
方法一:中序遍历
思路:对称二叉树分别按左中右和右中左的顺序进行中序遍历的结果应该一样。
重要:这种方法错了,因为中序遍历结果不能唯一确定树的形状,不同形状的树可能具有相同的中序遍历结果。
方法二:递归
思路:给定两个一开始都指向根节点的指针,使两指针始终延相反方向前进,两指针指向的值一直相等即对称。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
总结
- 重温了一下前中后序遍历的迭代方法,感觉还是得硬记啊,要自己直接想出来还是有点难。
- 本题除了递归,一样可以使用迭代+栈的方法,二叉树相关题目的很多递归解法都可以转换成迭代+栈的解法。
102.二叉树的层序遍历
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
方法一:队列(广度优先搜索)
思路:就是数据结构课程中讲解的使用队列对二叉树进行层序遍历的方法,只不过本题中要添加一些步骤,使得能够识别出每个节点所在的层数。
每次把一整层的节点数量计算出来,然后遍历这层的每个节点同时将该节点的子节点放入队列中,当遍历完该层节点时,队列中刚好就全是下一层的所有节点,这样又可以计算出下一层的节点数量。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
104.二叉树的最大深度
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最大深度 3 。
链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
方法一:递归
二叉树这里好多题目都可以用递归来做,所以遇到二叉树的题目都先想想递归。
时间复杂度:O(n)
空间复杂度:O(height),其中height表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。也就是说,如果每层递归函数的空间复杂度为n,总空间复杂度即为n*递归层数。
1 | class Solution { |
105.从前序与中序遍历序列构造二叉树
tips:代码块中的注解、加粗、下划线部分为重点内容。
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树: 3
/
9 20
/
15 7
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
方法一:递归
思路:就是数据结构课程中的重构思路。
1 | class Solution { |
114.二叉树展开为链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树,原地将它展开为一个单二叉树。
例如,给定二叉树
1
/
2 5
/ \
3 4 6
将其展开为:1
2
3
4
5
6
链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
方法一:前序遍历
重要:原地创建的意思就是不能new新的节点,只能在原来的节点的基础之上修改节点子链接。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
方法二:寻找前驱节点
思路:找到左子树的最右最下的节点(也就是前序遍历或中序遍历最后访问的节点),作为右子树的父节点。
也就是说分析每个节点A,找到该节点的前驱节点B,把节点A的右子树切下来,将该右子树接到前驱节点B的右子节点,然后再把节点A左子树切下来放到节点A的右边。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution1 { |
121.买卖股票的最佳时机
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
方法一:动态规划
1 | class Solution { |
122.买卖股票的最佳时机2
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
方法一:动态规划
1 | class Solution { |
123.买卖股票的最佳时机3
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4:
输入:prices = [1]
输出:0
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
方法一:动态规划
巧思题,要硬记。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
124.二叉树中的最大路径和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入:[1,2,3]
1
/
2 3输出:6
示例 2:
输入:[-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7输出:42
链接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
方法一:递归
重要:一定要理解,在二叉树中的一条路径一定是先上升然后下降的,或者只有上升或只有下降。不可能有两个或以上的方向变化。
所以任何一条路径一定是一个根节点加上一个左单度左子树和一个单度右子树。(单度子树就是指所有节点的度都为1或0的子树)
1 | class Solution { |
128.最长连续序列
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
进阶:你可以设计并实现时间复杂度为 O(n) 的解决方案吗?
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
链接:https://leetcode-cn.com/problems/longest-consecutive-sequence
方法一:排序+动态规划
注意:重复元素不重复增加最长连续序列的长度,但是也不中断最长连续序列长度的增加。
1 | class Solution { |
方法二:HashSet
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution1 { |
136.只出现一次的数字
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
链接:https://leetcode-cn.com/problems/single-number
方法一:HashSet
常见时间复杂度有:常数阶O(1),对数阶O(logn),线性阶O(n),线性对数阶O(nlogn),平方阶O(n^2),立方阶O(n^3)
本题所要求的 线性时间复杂度,即要求时间复杂度为O(n)。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
方法二:位运算
位运算中的异或运算满足:
- 任何数与0异或结果都为自身,
- 任何数与自身异或结果都为0,
- 异或运算符合交换律和结合律。
根据以上条件将输入数组中所有整数全部异或,则最终结果应为只出现一次的那个整数。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution1 { |
补充
Java提供的位运算符有:左移<<、右移>> 、无符号右移>>>、位与& 、位或|、位非~、位异或^,除了位非~是一元操作符外,其它的都是二元操作符。
139.单词拆分
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2:
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。
示例 3:
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false
链接:https://leetcode-cn.com/problems/word-break
方法一:递归回溯法
思路:尝试找出与字符串s前若干的字符相匹配的所有列表中的字符串,然后将剩下字符串s剩下的部分重复上述步骤。
1 | class Solution { |
方法二:动态规划+HashSet
时间复杂度:O(n^2)
空间复杂度:O(n)
1 | class Solution1 { |
141.环形链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:你能用 O(1)(即,常量)内存解决此问题吗?
示例 1:
输入:head = [3,2,0,-4]
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2]
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
链接:https://leetcode-cn.com/problems/linked-list-cycle
方法一:双指针
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
方法二:HashSet
思路:每经过一个节点,就查询集合是否已存在该节点,不存在则加入集合中。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution1 { |
142.环形链表加强
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
说明:不允许修改给定的链表。
进阶:你是否可以使用 O(1) 空间解决此题?
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii
方法一:双指针
思路:这里其实是三指针法,当快慢指针相遇时,此时第三个指针从头部出发,同时慢指针继续前进,当两者相遇时,根据数学计算可得,它们相遇的点即为入环节点。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
146.LRU缓存机制
tips:代码块中的注解、加粗、下划线部分为重点内容。
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1。
- void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
链接:https://leetcode-cn.com/problems/lru-cache
方法一:HashMap+双向链表
其实我自己已经想到了这两个数据结构,但就是不知道怎么去应用和编写。
一般这种专门考察数据结构应用的题目,面试官期望我们能够自己实现一个双向链表,而不是使用语言自带的。
get和put方法时间复杂度:O(1)
空间复杂度:O(capacity)
1 | class LRUCache { |
148.排序链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
示例 1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
示例 3:
输入:head = []
输出:[]
链接:https://leetcode-cn.com/problems/sort-list
十大排序算法

不要求多了,至少前面5中排序算法的原理、复杂度、实现必须要掌握。
方法一:插入排序
思路:重建一个新链表,将原链表中的节点一个一个按大小顺序添加到新链表当中去。
时间复杂度:O(n^2)
空间复杂度:O(1)
1 | class Solution { |
方法二:递归实现的归并排序
思路:
- 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 22 步,慢指针每次移动 11 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
- 使用递归对两个子链表分别排序。
- 将两个排序后的子链表合并,得到完整的排序后的链表。可以使用21. 合并两个有序链表的做法,将两个有序的子链表进行合并。
时间复杂度:O(nlogn)(可以看出复杂度中出现logn的两种常见情况:二分法、递归)
空间复杂度:O(logn)(空间复杂度主要是由递归造成的,递归的空间复杂度一般都是O(logn),将递归转换成迭代即可减小空间复杂度。)
1 | class Solution1 { |
方法三:迭代实现的归并排序
时间复杂度:O(nlogn)
空间复杂度:O(1)
具体实现代码不再复写,就上将方法二中的两个递归函数中的递归改成迭代。
152.乘积最大子数组
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
链接:https://leetcode-cn.com/problems/maximum-product-subarray
方法一:动态规划
本题与题[53.最大子序和]有一定类似,但又有所不同,因为本题中的乘积要考虑负负得正。
考虑当前位置如果是一个负数的话,那么我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。如果当前位置是一个正数的话,我们更希望以它前一个位置结尾的某个段的积也是个正数,并且希望它尽可能地大。于是这里我们可以再维护一个fmin(i),它表示以第i个元素结尾的乘积最小子数组的乘积,那么我们可以得到这样的动态规划转移方程:

时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
155.最小栈
tips:代码块中的注解、加粗、下划线部分为重点内容。
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入:
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.
链接:https://leetcode-cn.com/problems/min-stack
方法一:辅助栈
在原有保存数据栈的基础之上再创建一个栈来保存每个栈顶元素对应的最小元素,也就是说两个栈长度始终相等,辅助栈中每个元素为数据栈中对应元素为栈顶时,数据栈中的最小元素值。
四个操作的时间复杂度均为:O(1)
空间复杂度:O(n)
1 | class MinStack { |
160.相交链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
编写一个程序,找到两个单链表相交的起始节点。
示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。
链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists
方法一:双指针
用暴力法或者HashSet当然都可以,只不过一个时间复杂度高了,一个空间复杂度高了。
使用双指针,一个遍历A+B,一个遍历B+A,若A、B相交,则两指针必相遇,且相遇点即为相交点;不相交则遍历到底也不相遇。
时间复杂度:O(m+n)
空间复杂度:O(1)
1 | class Solution { |
169.多数元素
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
链接:https://leetcode-cn.com/problems/majority-element
方法一:摩尔投票法
1 | class Solution { |
188.买卖股票的最佳时机4
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
方法一:动态规划
本题就是在【力扣刷题】_123.买卖股票的最佳时机3的基础之上进行改写即可。
时间复杂度:O(kn)
空间复杂度:O(k)
1 | class Solution { |
198.打家劫舍
tips:代码块中的注解、加粗、下划线部分为重点内容。
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
链接:https://leetcode-cn.com/problems/house-robber
方法一:动态规划
1 | class Solution { |
200.岛屿数量
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出:1
示例 2:
输入:grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出:3
链接:https://leetcode-cn.com/problems/number-of-islands
方法一:递归
岛屿问题的本质实际上就是矩阵网格结构的递归遍历问题,这类问题最关键的难点就是某节点是否已经遍历过了的判断。
思路:将所有已经遍历过了的陆地格子的值改写成’0’。
时间复杂度:O(mn)
空间复杂度:O(mn)
1 | class Solution { |
206.反转链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
链接:https://leetcode-cn.com/problems/reverse-linked-list
方法一:递归
该题的递归方法是巧思,要硬记。
经过这道题的递归方法,感觉自己对于递归的理解和递归的变式还是掌握得不够充分。
思路:本题的关键,将head.next作为递归方法的输入参数之后,head的next属性还是指向原来哪个节点的,只不过哪个节点现在变成了一个链表的尾端。
1 | class Solution { |
方法二:迭代
1 | class Solution1 { |
207.课程表
tips:代码块中的注解、加粗、下划线部分为重点内容。
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
链接:https://leetcode-cn.com/problems/course-schedule
本题的解题思路是通过拓扑排序判断此课程安排图是否是有向无环图(DAG)。
拓扑排序原理:对DAG的顶点进行排序,使得对每一条有向边 (u,v),均有u(在排序记录中)比v先出现。亦可理解为对某点v而言,只有当v的所有源点均出现了,v才能出现。
方法一:广度优先遍历BFS
把课程编号看作图的节点,先决条件看作有向边。
用一个数组记录图中每个节点的入度,也就是被多少条有向边作为被指向端;并用动态数组记录每个节点所指向的其他节点。
维护一个队列,每次把入度为0的节点放入队列中,一个一个删除队列中的节点,并把被删除节点所指向的所有节点的入度都减1,再重复维护该队列直到队列为空。最后如果还剩下了节点没有被删,则就是组成环的节点和边;如果没有节点了,则说明图中没有环。
时间复杂度O(N+M): 遍历一个图需要访问所有节点和所有临边,N和M分别为节点数量和临边数量;
空间复杂度O(N+M): 为建立邻接表所需额外空间,邻接表edge长度为N,并存储M条临边的数据。
1 | class Solution { |
方法二:深度优先遍历DFS/递归
这个递归也非常重要,也是递归中的一个巧思。
思路:创建一个辅助数组,用来记录图中每个节点的被访问状态,0表示未被访问,-1表示在以其他节点为起点沿有向边进行访问时被访问过,1表示在以该节点为起点沿有向边进行访问时被访问过。
我们依次对图中每一个节点进行递归访问,若节点状态为-1则表示之前访问也没出问题,不用再访问;若节点状态为1表示出现了环,直接返回false。
时间复杂度O(N+M)
空间复杂度O(N+M)
1 | class Solution1 { |
208.实现Trie前缀树
tips:代码块中的注解、加粗、下划线部分为重点内容。
实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree
方法一:Trie前缀树的实现
本题实际上就是前缀树Trie的基本实现,帮助我们理解前缀树这种数据结构的原理。
前缀树一般就是用来保存只含有小写字符的字符串,其实一般就是用来保存一个HashMap的所有key。
前缀树数据结构中最重要的同样是节点和节点中对于其他节点的链接,只不过前缀树中的节点中只有是否为终点这个特有属性,剩下的就是表示链接的节点数组。前缀树中每个节点一共可以有26个节点链接,用数组来表示,每个对应的数组索引用来表示一个特定的字符。比如List[0]不为空时,表示该节点中存有字符’a’这个链接,并通过它指向下一个节点。
1 | class Trie { |
总结
重要:如果是全局变量,包装类Boolean是会被默认赋值为null,而基础类型boolean会被默认赋值为false的,该赋值过程应该是在类加载的时候赋值的。如果是局部变量,当你不赋值去使用的时候,编译器会直接报错,所以局部变量肯定是没有默认值的。
215.数组中的第K个最大元素
tips:代码块中的注解、加粗、下划线部分为重点内容。
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array
方法一:堆排序
1 | class Solution { |
221.最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。
示例 1:
输入:matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出:4
示例 2:
输入:matrix = [[“0”,”1”],[“1”,”0”]]
输出:1
示例 3:
输入:matrix = [[“0”]]
输出:0
链接:https://leetcode-cn.com/problems/maximal-square
方法一:动态规划
1 | class Solution { |
方法二:动态规划简化
在我自己写的基础之上优化了一步。
1 | class Solution { |
226.翻转二叉树
翻转一棵二叉树。
示例:
输入:
4
/
2 7
/ \ /
1 3 6 9
输出:
4
/
7 2
/ \ /
9 6 3 1
链接:https://leetcode-cn.com/problems/invert-binary-tree
方法一:递归
1 | class Solution { |
234.回文链表
tips:代码块中的注解、加粗、下划线部分为重点内容。
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
链接:https://leetcode-cn.com/problems/palindrome-linked-list
方法一:辅助栈
回文串:回文串就是正读和反读都一样的字符串
思路:先找到链表中点,把前半段入栈,后半段依次与栈顶比较,相同则出栈,不同则不是回文链表,最后栈为空则为回文链表。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
方法二:双指针
寻找链表中点,并在此过程中反转前半段链表,然后双指针从中点分别往左右出发,不同则不是回文链表,直到走到两端都相同则为回文链表。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution1 { |
236.二叉树的最近公共祖先
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
方法一:递归
本题需要我们依靠自己的智慧去定义当该方法返回值为null时代表什么。
非常重要:此处我们定义当该方法返回null时表示p、q全都不在该二叉树root中。
该方法比我自己想出来的方法【剑指刷题】_面试题68_2.二叉树的最近公共祖先要简洁多了,还是硬记这种吧。
1 | class Solution { |
238.除自身以外数组的乘积
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
链接:https://leetcode-cn.com/problems/product-of-array-except-self
方法一:巧思
巧思题:遍历两边,第一遍把每个元素左边的元素都乘起来放入该位置。第二遍从后往前把每个元素右边的元素都乘起来再乘上左边元素的乘积。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
239.滑动窗口最大值
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
示例 3:
输入:nums = [1,-1], k = 1
输出:[1,-1]
示例 4:
输入:nums = [9,11], k = 2
输出:[11]
示例 5:
输入:nums = [4,-2], k = 2
输出:[4]
链接:https://leetcode-cn.com/problems/sliding-window-maximum
方法一:辅助队列
思路:创建一个辅助队列,保存当前窗口中依次从大到小的数值,每次删除数值时查看是不是删除了尾部最大元素;每次添加数值时查看是不是添加进了比头部元素大的数值,是则将当前头部元素先删除,直到头部元素不小于新增元素,再把新增元素放入辅助队列头部。
因为这里要查看队头和队尾的元素,所以用双端队列。
1 | class Solution { |
240.搜索二维矩阵2
tips:代码块中的注解、加粗、下划线部分为重点内容。
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1:
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false
链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii
方法一:巧思
巧思题。
思路:从矩阵的右上角开始寻找,当前格子元素大于target则将格子左移,当格子元素小于target则将格子右移,重复上述步骤直到找到该元素或超出矩阵。
1 | class Solution { |
279.完全平方数
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
链接:https://leetcode-cn.com/problems/perfect-squares
方法一:动态规划
巧思题,要硬记。
思路:就是利用动态规划前面的数据,通过枚举比较得出每一个数的最少完全平方数个数。
时间复杂度:O(n^1.5)
空间复杂度:O(n)
1 | class Solution { |
283.移动零
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
链接:https://leetcode-cn.com/problems/move-zeroes
方法一:双指针
思路:左指针指向已处理好序列中首个零,右指针指向未处理序列的首个元素。
1 | class Solution { |
287.寻找重复数
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,找出 这个重复的数 。
示例 1:
输入:nums = [1,3,4,2,2]
输出:2
示例 2:
输入:nums = [3,1,3,4,2]
输出:3
示例 3:
输入:nums = [1,1]
输出:1
示例 4:
输入:nums = [1,1,2]
输出:1
链接:https://leetcode-cn.com/problems/find-the-duplicate-number
方法一:原地置换
巧思题,要硬记。
思路与【剑指刷题】_面试题3.数组中重复的数字相同。
1 | class Solution { |
297.二叉树的序列化与反序列化
tips:代码块中的注解、加粗、下划线部分为重点内容。
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。
示例 1:
1
/
2 3
/
4 5输入:root = [1,2,3,null,null,4,5]
输出:[1,2,3,null,null,4,5]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[1,2]
链接:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
方法一:层序遍历+辅助队列
要将一个二叉树序列化其实也就是要将一个二叉树与一个唯一的字符串对应起来。
1 | class Codec { |
300.最长递增子序列
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
方法一:动态规划
巧思题,要硬记
一定要理解的一个关键点:如果一个数比它的前面某一个数小那么该数一定不在递增子序列中。因为如果该数在递增子序列中,那么它前面那个数比它大也一定可以进入递增子序列中,那么如果它前面那个数进入了递增子序列,该数自己就一定不能进入递增子序列。
时间复杂度:O(n^2)
空间复杂度:O(n)
1 | class Solution { |
301.删除无效的括号
tips:代码块中的注解、加粗、下划线部分为重点内容。
删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:
输入: “()())()”
输出: [“()()()”, “(())()”]
示例 2:
输入: “(a)())()”
输出: [“(a)()()”, “(a())()”]
示例 3:
输入: “)(“
输出: [“”]
链接:https://leetcode-cn.com/problems/remove-invalid-parentheses
方法一:递归回溯
1 | class Solution { |
309.最佳买卖股票时机含冷冻期
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
方法一:动态规划
巧思题,要硬记。
思路:把买入股票看作亏钱,卖出股票看作赚钱,主要考虑三种状态,持有股票、冷冻期、卖出了股票且非冷冻期。
时间复杂度:O(n)
空间复杂度:O(n)
1 | class Solution { |
312.戳气球
tips:代码块中的注解、加粗、下划线部分为重点内容。
有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1:
输入:nums = [3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167
示例 2:
输入:nums = [1,5]
输出:10
链接:https://leetcode-cn.com/problems/burst-balloons
方法一:递归+动态规划
巧思题,要硬记。
这种题目出出来纯粹就是恶心人的!!!
1 | class Solution { |
【力扣刷题】_322.零钱兑换
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
示例 4:
输入:coins = [1], amount = 1
输出:1
示例 5:
输入:coins = [1], amount = 2
输出:2
链接:https://leetcode-cn.com/problems/coin-change
方法一:动态规划
巧思题,要硬记。
非常重要,思路与【力扣刷题】_279.完全平方数思路相似。
1 | class Solution { |
337.打家劫舍3
tips:代码块中的注解、加粗、下划线部分为重点内容。
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \2 3
\ \
3 1输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3 / \4 5
/ \ \
1 3 1输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
链接:https://leetcode-cn.com/problems/house-robber-iii
方法一:递归
本方法思路与【力扣刷题】_198.打家劫舍的思路相似,在此基础上改写。
1 | class Solution { |
方法二:递归+动态规划+HashMap
由于第一种方法中需要对很多节点重复使用rob方法进行计算,浪费了大量时间,可以采用【力扣刷题】_312.戳气球中记忆化递归的思路进行优化,每对一个节点使用rob方法,则将该计算值保存到哈希表中。
1 | class Solution1 { |
338.比特位计数
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
链接:https://leetcode-cn.com/problems/counting-bits
方法一:暴力法
1 | class Solution { |
方法二:动态规划
巧思题,要硬记。
思路:位运算i&(i-1)得到的就是将i的二进制表达式从右往左第一个1变成0,所表示的数。
1 | class Solution1 { |
347.前K个高频元素
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
链接:https://leetcode-cn.com/problems/top-k-frequent-elements
方法一:优先队列+HashMap
类似面试题40.最小的k个数中的堆排序方法的思路,不同之处是本题中自定义优先队列的比较器为比较哈希表中的值。
1 | class Solution { |
394.字符串解码
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例 1:
输入:s = “3[a]2[bc]”
输出:”aaabcbc”
示例 2:
输入:s = “3[a2[c]]”
输出:”accaccacc”
示例 3:
输入:s = “2[abc]3[cd]ef”
输出:”abcabccdcdcdef”
示例 4:
输入:s = “abc3[cd]xyz”
输出:”abccdcdcdxyz”
链接:https://leetcode-cn.com/problems/decode-string
方法一:递归
存粹就是体力活,没有太多技术含量。
1 | class Solution { |
399.除法求职
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题,其中 queries[j] = [Cj, Dj] 表示第 j 个问题,请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案,则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串,也需要用 -1.0 替代这个答案。
注意:输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况,且不存在任何矛盾的结果。
示例 1:
输入:equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出:[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释:
条件:a / b = 2.0, b / c = 3.0
问题:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果:[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2:
输入:equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出:[3.75000,0.40000,5.00000,0.20000]
示例 3:
输入:equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
输出:[0.50000,2.00000,-1.00000,-1.00000]
链接:https://leetcode-cn.com/problems/evaluate-division
方法一:带权并查集
非常重要,详细解释可以自行查看答案解析。
本质上给到我们的数据描述的是一个有向图,有向图问题常用带权并查集方法解决。
1 | class Solution { |
406.根据身高重建队列
tips:代码块中的注解、加粗、下划线部分为重点内容。
假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。
示例 1:
输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释:
编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2:
输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
链接:https://leetcode-cn.com/problems/queue-reconstruction-by-height
方法一:从低到高考虑
巧思题,要硬记。
思路:先将原队列按身高排好序。如果我们在初始时建立一个包含n个位置的空队列,而我们每次将一个人放入队列中时,会将一个「空」位置变成「满」位置,那么当我们放入第i个人时,我们需要给他安排一个「空」位置,并且这个「空」位置前面恰好还有ki个「空」位置,用来安排给后面身高更高的人。也就是说,第i个人的位置,就是队列中从左往右数第ki+1 个「空」位置。
1 | class Solution { |
416.分割等和子集
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum
方法一:动态规划
巧思题,要硬记。
重要关键点:将本体转化成一个这样的判断问题:使用数组中的一部分元素相加,能不能组成数组总额的一半,其中每个元素最多使用一次。
1 | class Solution { |
相关问题
「力扣」上的 0-1 背包问题:
「力扣」第 416 题:分割等和子集(中等);
「力扣」第 474 题:一和零(中等);
「力扣」第 494 题:目标和(中等);
「力扣」第 879 题:盈利计划(困难);
「力扣」上的 完全背包问题:
「力扣」第 322 题:零钱兑换(中等);
「力扣」第 518 题:零钱兑换 II(中等);
「力扣」第 1449 题:数位成本和为目标值的最大数字(困难)。
437.路径总和3
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3/ \
3 2 11
/ \
3 -2 1返回 3。和等于 8 的路径有:
5 -> 3
5 -> 2 -> 1
-3 -> 11
链接:https://leetcode-cn.com/problems/path-sum-iii
方法一:递归
1 | class Solution { |
438.找到字符串中所有字母异位词
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
说明:
- 字母异位词指字母相同,但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
输入:
s: “cbaebabacd” p: “abc”输出:
[0, 6]解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:
输入:
s: “abab” p: “ab”输出:
[0, 1, 2]解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。
链接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
方法一:滑动窗口
1 | class Solution { |
448.找到所有数组中消失的数字
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]输出:
[5,6]
链接:https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
方法一:原地置换
老问题【力扣刷题】_287.寻找重复数的升级版了,做了挺多次了。
原地置换方法的关键:自己在草稿纸上画一个例子,然后画出置换过程,辅助编写代码。
1 | class Solution { |
461.汉明距离
tips:代码块中的注解、加粗、下划线部分为重点内容。
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y,计算它们之间的汉明距离。
注意:
0 ≤ x, y < 2^31.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑上面的箭头指出了对应二进制位不同的位置。
链接:https://leetcode-cn.com/problems/hamming-distance
方法一:位运算
1 | class Solution { |
494.目标和
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例:
输入:nums: [1, 1, 1, 1, 1], S: 3
输出:5
解释:-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。
链接:https://leetcode-cn.com/problems/target-sum
方法一:递归
1 | class Solution { |
方法二:动态规划
其实也可以转化成一个背包问题,如【力扣刷题】_416.分割等和子集。
但是这里涉及正负,状态的定义就要考虑很复杂的边界问题,比寻常背包问题麻烦多了。
1 | class Solution1 { |
538.把二叉搜索树转换为累加树
tips:代码块中的注解、加粗、下划线部分为重点内容。
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下,二叉搜索树满足下列约束条件:
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例 1:
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
输入:root = [0,null,1]
输出:[1,null,1]
示例 3:
输入:root = [1,0,2]
输出:[3,3,2]
示例 4:
输入:root = [3,2,4,1]
输出:[7,9,4,10]
链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree
方法一:从右往左中序遍历
1 | class Solution { |
543.二叉树的直径
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/
2 3/ \
4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
链接:https://leetcode-cn.com/problems/diameter-of-binary-tree
方法一:递归
二叉树中的这种路径最多也就只有一个转折点,也就是说最多也就是先升后降,不可能有多次转折。
本方法采用类似于后序遍历的递归,避免了重复计算同一个节点的深度,极大减小了时间复杂度。
1 | class Solution1 { |
560.和为K的子数组
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
链接:https://leetcode-cn.com/problems/subarray-sum-equals-k
方法一:HashMap
巧思题,要硬记。
1 | class Solution { |
581.最短无序连续子数组
tips:代码块中的注解、加粗、下划线部分为重点内容。
给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组,并输出它的长度。
示例 1:
输入:nums = [2,6,4,8,10,9,15]
输出:5
解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
示例 2:
输入:nums = [1,2,3,4]
输出:0
示例 3:
输入:nums = [1]
输出:0
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
方法一:巧思
首先我们需要找到原数组在哪个位置开始不是升序的。我们从头开始遍历数组,一旦遇到降序的元素,我们记录最小元素为 min。类似的,我们逆序扫描数组 nums,当数组出现升序的时候,我们记录最大元素为 max。然后,我们再次遍历 nums 数组并通过与其他元素进行比较,来找到 min 和 max 在原数组中的正确位置。我们只需要从头开始找到第一个大于 min 的元素,从尾开始找到第一个小于 max 的元素,它们之间就是最短无序子数组。
1 | class Solution { |
617.合并二叉树
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
链接:https://leetcode-cn.com/problems/merge-two-binary-trees
方法一:递归
1 | class Solution { |
647.回文子串
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:”abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”
示例 2:
输入:”aaa”
输出:6
解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
链接:https://leetcode-cn.com/problems/palindromic-substrings
方法一:中心扩散法
1 | class Solution { |
714.买卖股票的最佳时机含手续费
tips:代码块中的注解、加粗、下划线部分为重点内容。
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
方法一:动态规划
本题主要在【力扣刷题】_309.最佳买卖股票时机含冷冻期的基础上进行改写即可。
时间复杂度:O(n)
空间复杂度:O(1)
1 | class Solution { |
739.每日温度
tips:代码块中的注解、加粗、下划线部分为重点内容。
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
链接:https://leetcode-cn.com/problems/daily-temperatures
方法一:辅助栈
创建两个栈,主栈保存从下到上单调递减的温度数据,辅栈中保存主栈中每一个温度在数组中的位置。
1 | class Solution { |
