24052 字
64 分钟
算法算法题
Hot100的ACM模式题解

把这份模板复制后改成你的 Hot 100 题解文章。

两数之和#

1. 题面#

1. 两数之和#

难度:简单

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那  两个  整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

进阶: 你可以想出一个时间复杂度小于 O(n^2) 的算法吗?

2. 解法#

Python3 点击展开代码
18 lines 展开代码

3. 反思#

  1. 本题是基础哈希表空间换时间,第一次做的时候没有加else,虽然这题无所谓,但是别的题可能会有区别。
  2. 还有一个细节,我用了dict,实际上覆盖了内置的dict,还是用mp比较好

4. 二刷#

成功考虑到了要不要else要不要加,另外,这题还有其他的解法。算是哈希表的基础应用题。


字母的同分异构词#

1. 题面#

49. 字母异位词分组#

难度:中等

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释:

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"
  • 字符串 "nat""tan" 是字母异位词,因为它们可以重新排列以形成彼此。
  • 字符串 "ate" ,"eat" 和 "tea" 是字母异位词,因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

2. 解法 1 · {}#

Python3 点击展开代码
23 lines 展开代码

3. 解法 2 · defaultdict#

Python3 点击展开代码
20 lines 展开代码

4. 反思#

  1. 实际上做到这里的时候想到用这种方法,但是还是有点小梗塞。容易出错的点:list不能作为key,需要tuple;ord函数别忘了;mp.values()的用法,返回values的迭代器,用list转为答案数组
  2. 如果使用默认数组,不需要先判key空产生[]再append,直接用defaultdict(list),等于设置了键值的值默认为list的默认值空列表;同理,这里设置为int就是默认值为0
  3. 注意输入处理,因为默认复制力扣的输入是有"的,而想去掉双引号,需要用单引号包裹来strip('"')。

5. 二刷#

哎呀,二刷错了啊!!竟然直接把哈希表转tuple当key了,哈希表本身tuple之后只能得到key的元组,计算实在想当也需要key = tuple(sorted(Counter(s).items()))用这种包含完整信息的,但是这样太麻烦了,要么直接用sorted之后当key,要么就是按照原本的做法,打字母表就行了。每个单词的结果作为记数列表当做tuple才是最自然的。不过这次好在想到了空的时候建[]


最长连续序列#

1. 题面#

128. 最长连续序列#

难度:中等

给定一个未排序的整数数组 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

示例 3:

输入:nums = [1,0,1,2]
输出:3

提示:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

2. 解法#

Python3 点击展开代码
20 lines 展开代码

3. 反思#

  1. 这题肯定也是第一时间想到空间换时间,但是没想到哈希存什么。主要是害怕for套for复杂度超过on,但是其实里面是有限次循环,还是on。
  2. 不用set的话问了题友,也是哈希打一遍标记,然后前后找。

4. 二刷#

秒了


移动零#

1. 题面#

283. 移动零#

难度:简单

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意  ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示 :

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

**进阶:**你能尽量减少完成的操作次数吗?

2. 解法#

Python3 点击展开代码
20 lines 展开代码

3. 反思#

  1. 没啥好说的,就是简单的移动插入,跟插入排序有点像,需要注意的是while循环下面别忘了移动变量,这个经常忘记。

4. 二刷#

直接i、j都定义为0就不需要特判n<=1了。

5. 三刷#

啊呀才发现一刷有重大问题!!i、j必须从0开始,特判小于等于1也没必要。如果j默认从1开始,就默许了0号位是有效的了,测试点会出错!!


盛水最多的容器#

1. 题面#

11. 盛最多水的容器#

难度:中等

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明: 你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

2. 题解#

Python3 点击展开代码
17 lines 展开代码

3. 反思#

  1. 这题老是幻视成单调栈,但是实际上不是需求"第一个比xx大/小"的量,卡了半天不知道怎么写。
  2. 但是这题实际上是一个贪心,理论依据是"移动高的那边一定不可能得到更优解",所以只能移动矮的那边去保留希望。这个解释还是让人感觉懵懵的。
  3. 询问码u,最好的解释是"移动小的那根不一定能让水更多,但是大的那根肯定会变少",因为移动大的那根,小的那根被限制住了,无论如何都不会变大,反而使宽度减小。

4. 二刷#

秒,移动短边获得希望。


三数之和#

1. 题面#

15. 三数之和#

难度:中等

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

2. 题解#

Python3 点击展开代码
29 lines 展开代码

3. 二刷#

  1. 这一题的去重是大坑。我使用tuple化list,勉强去重成功。但是最好的方法,其实是移动的时候直接忽略相同元素(排序后相同元素在一起)。所以按照题解一样,如果移动后元素还是一样,直接什么也不做跳过去。
  2. 可以剪枝到len(nums)-2

接雨水#

1. 题面#

42. 接雨水#

难度:困难

给定 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

提示:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

2. 题解1 - 单调栈法#

Python3 点击展开代码
27 lines 展开代码

3. 反思#

  1. 实际解题的思路已经写的很清楚了,重要的就是单调栈的思想。
  2. 注意这里不需要全部弹出,右侧可能没有更高的边界;需要注意的是左侧可能会没有水洼,所以要保护一下空栈。
  3. 这里right、right_val就是当前的i、h,更简的话可以不定义right相关变量

4. 二刷#

二刷的时候把问题想简单了,直接把val做单调栈没有带上坐标,然后直接只看高度差来积水。 比较好的思维方式是,看到弹出结算的加上的水,其实是以curr高度托底,左右第一个比较高的柱子之间的差。

每次比较担心的思维陷阱其实是4、6会不会重复计算水?排除这种情况就可以大胆用长度差*高度差来积水了。

alt text

5. 题解2 - 前后缀最大值法#

Python3 点击展开代码
30 lines 展开代码

6. 题解3 - 双指针法#

上面的前后缀只要算自己头上的水泊,还是比较清晰的。不过仔细观察就会发现开两个数组没必要,用两个变量就可以了,这样就可以压缩成双变量法。

Python3 点击展开代码
17 lines 展开代码

无重复字符的最长子串#

1. 题面#

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

难度:中等

给定一个字符串 s ,请你找出其中不含有重复字符的  最长 子串  的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

2. 题解#

Python3 点击展开代码
18 lines 展开代码

3. 反思#

  1. 我其实感觉滑动窗口的思路比较简单,但是比较考验码力,特别是边界和条件判断的地方,特别容易绕晕。
  2. 我第一版有很多疏漏,现在是更新过的版本。易错点1:left移动的条件不对,应该写在while里面的是"不合法"的条件,移动left直到合法;易错点2:不能用len(window),即使哈希值归0了,键值对还在。

4. 二刷#

想到用滑动窗口了,但是收缩条件一时想不到,还想着遍历整个哈希表看看大于1有无,其实只要看当前位置就行了。 另外还有一个坑点,我有时候会在left收缩的时候复用c,其实多数情况没事,但是收缩的条件这次是包含c的,就不能直接覆盖了,还是建议以后写成d吧。

5. 解法 - 标准滑动窗口法#

Python3 点击展开代码
21 lines 展开代码

6. 三刷#

这次写对了,但是多加了两个没用的if。if只会被用来判断need,window肯定是加一次删一次,不用if。


找到字符串中所有字母异位词#

1. 题面#

438. 找到字符串中所有字母异位词#

难度:中等

给定两个字符串 s 和 p,找到 s 中所有 p 的  异位词  的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

示例 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" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 10^4
  • s 和 p 仅包含小写字母

2. 题解#

Python3 点击展开代码
43 lines 展开代码

3. 反思#

  1. 这题是非常值得反复练习的滑动窗口题目,我重写的时候又弄错了,将right - left == len(p)作为while条件,这样还要先移动right,非常复杂容易出错。正确的一体化思路,应当是将valid个数合格作为左边收缩的起点,收缩一直进行到valid不满足为止。
  2. 左右的操作实际上是对称的,取值、移动,右侧先动哈希再看valid,左侧先看valid再动哈希。其中的区别在于,left是看先满足再丢弃,right是先拿取再看是否满足。

4. 二刷#

哎哟我,二刷的时候又弄错了,混淆了固定窗口的滑动和变长度窗口的滑动。上面的题解是为了和其他窗口valid放在while中对上从而做的调整,ans判读也移动到了收缩内部。但是我们可以写这题的标准滑动窗口,将判断放后面,然后对于固定窗口的题,可以直接把长度作为while的判断。

5. 题解2 - 标准固定窗口#

Python3 点击展开代码
40 lines 展开代码

和为k的子数组#

1. 题面#

560. 和为 K 的子数组#

难度:中等

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

2. 题解#

Python3 点击展开代码
14 lines 展开代码

3. 反思#

  1. 本题一开始用滑动窗口写,但滑动窗口要求窗口扩大时 total 单调递增,即所有元素必须 >= 0。本题 nums[i] 取值范围 [-1000, 1000],包含负数,while total > k 缩窗口的逻辑不成立——踢掉一个负数 total 反而变大,可能漏掉合法子数组。反例:nums=[-1,-1,1], k=0,正确答案是 1(整个数组),滑动窗口会输出 0。
  2. 正确做法是前缀和+哈希表:遍历时维护 cur(前缀和),对于每个位置,查哈希表中 cur - k 出现的次数。本质上和两数之和是同一个套路——cur - k = 之前某个前缀和,那中间那段的和就是 k。

4. 二刷#

知道为什么不能用滑动窗口,然后能写出前缀和+哈希表。


滑动窗口最大值#

1. 题面#

239. 滑动窗口最大值#

难度:困难

给你一个整数数组 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]

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

2. 解法 1 · 单调队列#

Python3 点击展开代码
25 lines 展开代码

3. 解法 2 · 堆#

Python3 点击展开代码
18 lines 展开代码

4. 反思#

  1. 这题一开始想到的还是滑动窗口,但是不知道怎么维护max的回退,一开始想到用栈,但是栈没办法处理退出的就是最大值,第二个大值在哪这个问题。
  2. 这题的破局关键其中之一就是存储下标。对于可能有重复值的题目,存下标是最安全稳妥的方法。
  3. 这题的标准思路是单调队列,单调队列常被用来解决"有效性窗口"的问题,比如这题,就是维持了一系列候选有效的max值,left移动就看左边的第一个值有没有过期(也就是看最大值有没有过期)
  4. 同样可以用堆来解决,两者思路差不多,都是存储候选,left移动看看候选最大值有没有过期,过期让老二上。(但是复杂度跌到onlogn了)
  5. 特别注意,这里无论是队列长度还是堆长度,都跟窗口的长度无关。所以我们判断窗口是否合法,还是要用下标来判断。

5. 二刷#

被秒了。。直接用堆,但是收缩时只看堆顶不对,这个写法只会在"离开的元素刚好等于当前最大值"时弹一下,否则堆里会残留很多已经不在窗口里的旧元素。必须要加上过期机制,比如加入坐标一起入堆,然后看坐标判断过期,或者干脆跟题解一样用单调队列。


最小覆盖子串#

1. 题面#

76. 最小覆盖子串#

难度:困难

给定两个字符串 s 和 t,长度分别是 m 和 n,返回 s 中的  最短窗口 子串 ,使得该子串包含 t 中的每一个字符( 包括重复字符 )。如果没有这样的子串,返回空字符串 ""

测试用例保证答案唯一。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入:s = "a", t = "a"
输出:"a"
解释:整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

提示:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • st 由英文字母组成

进阶: 你能设计一个在 O(m + n) 时间内解决此问题的算法吗?

Python3 点击展开代码
44 lines 展开代码

2. 反思#

  1. 滑动窗口果然容易码错。虽然对称的left、right操作已经记熟了,但是仍然忘记先看need再哈希。
  2. 满足条件再收缩,收缩前就已经满足的,在收缩代码里拿答案;收缩后才合法的,在收缩完成后拿答案。两种情况取决于写的while,一定要注意分辨。

3. 二刷#

写错了。这次虽然写对了在need中才加入哈希的逻辑,但是收缩还是写错了。

  1. 收缩时不能一见到 d in need 就直接 valid -= 1,还要进一步看if window[d] == need[d]。因为valid只记录是否达到过合法,即使window再进元素也只会加哈希表,反之减少元素也不一定会损失合法性,可以脑内模拟
  2. 注意valid等于的时候判断位置,应该在收缩刚开始。

4. 三刷#

我草,三刷暴露出了重要问题,观察以下两种写法

Python3 点击展开代码
4 lines 展开代码

Python3 点击展开代码
4 lines 展开代码

乍一看两者没什么区别,但是这里由于只要小于window数量小于need就会削减,只要数量不够,每次移出字符都在疯狂扣分,导致 valid 错乱!

虽然我们肯定是要移动的,但是我们最好在移动之前看看是不是正好有效,如果是的才减少valid,这样就不会滥减valid。顺带一提,第一种情况leetcode反例"dinitrophenylhydrazinetrinitrophenylmethylnitramine"和"trinitrophenylmethylnitramine"。

这是固定窗口用滑动窗口解的bug,上一题直接用范围判断其实都没事,因为我们收缩的时候会保证valid达标,所以不可能会出现无辜收缩乱扣valid的情况。不过为了统一,记住以后先判断 window[c2] == need[c2],决定是否要 valid -= 1,再 window[c2] -= 1


最大子数组和#

1. 题面#

53. 最大子数组和#

难度:中等

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

2. 题解#

Python3 点击展开代码
19 lines 展开代码

3. 反思#

  1. 这题被叫做Kadane算法,他其实是一种动态规划的思想的优化简化,用于处理另起炉灶还是继续加入的选择哪个更好,然后维持一个全局的最优ans

4. 二刷#

二刷用了标准dp写出来,不过也是想了一段时间。

5. 题解2 - 标准dp#

Python3 点击展开代码
16 lines 展开代码

合并区间#

1. 题面#

56. 合并区间#

难度:中等

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 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] 可被视为重叠区间。

示例 3:

输入:intervals = [[4,7],[1,4]]
输出:[[1,7]]
解释:区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

2. 题解#

Python3 点击展开代码
28 lines 展开代码

3. 反思#

  1. 这题重合需要注意可能传进去之前的,传入的左端点还不一定按时间排序,需要自己排序一下。
  2. 排序算法intervals.sort(key = lambda x0)可以简写成intervals.sort()。因为python的sort可以默认按照第一项排序。

4. 二刷#

只有按左端点排序之后,才能on排序。这题标准解就是sort之后只看右断点,不用多想。


轮转数组#

1. 题面#

189. 轮转数组#

难度:中等

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

进阶:

  • 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的  原地  算法解决这个问题吗?

2. 题解 1 · 切片#

Python3 点击展开代码
7 lines 展开代码

3. 题解 2 · 三次翻转#

Python3 点击展开代码
17 lines 展开代码

4. 题解 3 · 环状替换#

每个元素直接跳到它最终该去的位置,一条链跳到底。但是当n与k不互质的情况下,一轮走不完,所以外层必须要从start=0,1,…,gcd(n,k)-1 各启动一轮。(当然,我们也不用非要算这个gcd,直接维持一个全局的count,只要所有数都交换过了,就停止)

Python3 点击展开代码
28 lines 展开代码

5. 反思#

  1. 如果不限制空间,这题cpp也能直接建立队列做。python切片的复杂度是O(k),会创建新列表
  2. 但是本题想考察的重点其实是你能不能写出O(1)的算法,也就是真的原地。
  3. 三次翻转是比较常规的方法,后面链表题也是这么写的。
  4. 环状替换比较绕,比较硬核,到时候有空再看看吧。

6. 二刷#

别忘了python不支持自定义起点终点的反转。


除自身以外数组的乘积#

1. 题面#

238. 除了自身以外数组的乘积#

难度:中等

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

不要使用除法, 且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 输入 保证 数组 answer[i]32 位 整数范围内

进阶: 你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)

2. 题解 1 · 前缀后缀积O(n)#

Python3 点击展开代码
20 lines 展开代码

3. 题解 2 · 空间O(1)#

Python3 点击展开代码
22 lines 展开代码

4. 反思#

  1. 经典前缀后缀题,需要注意的是不常用的后缀怎么设置数组(边界问题)

缺失的第一个正数#

1. 题面#

41. 缺失的第一个正数#

难度:困难

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

输入:nums = [1,2,0]
输出:3
解释:范围 [1,2] 中的数字都在数组中。

示例 2:

输入:nums = [3,4,-1,1]
输出:2
解释:1 在数组中,但 2 没有。

示例 3:

输入:nums = [7,8,9,11,12]
输出:1
解释:最小的正数 1 没有出现。

提示:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

2. 题解#

Python3 点击展开代码
19 lines 展开代码

3. 反思#

  1. 这题不给你用额外的空间,但是要想到下标和数值本身是有关系的,直接用下标来对应就行了。

4. 二刷#

想到了用下标存对应数,但是要记住判读一下值的范围(可能超出下标了)。另外原理是,不管里面存的什么数,第一个不在范围内的正数一定在最大下标+1范围内 。


矩阵置零#

1. 题面#

73. 矩阵置零#

难度:中等

给定一个 _m_ x _n_ 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

示例 1:

输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

进阶:

  • 一个直观的解决方案是使用 O(_m__n_) 的额外空间,但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(_m_ + _n_) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗?

2. 题解#

Python3 点击展开代码
28 lines 展开代码

3. 题解 · 常数空间#

Python3 点击展开代码
55 lines 展开代码

4. 反思#

  1. 也是限制空间,这时候一定要活用原本的结构。

5. 二刷#

秒了,但是要注意标记、对标记的时候,都不要用第一行或者第一列了,不然有一个0就直接先给第一行标满,然后全0了


螺旋矩阵#

54. 螺旋矩阵#

难度:中等

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

1. 题解#

Python3 点击展开代码
38 lines 展开代码

2. 二刷#

二刷用了变动即判断的思路,写的可能代码更多,但是思路更加清晰

3. 题解2 - 变动即判定#

Python3 点击展开代码
42 lines 展开代码

旋转图像#

1. 题面#

48. 旋转图像#

难度:中等

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[[7,4,1],[8,5,2],[9,6,3]]

示例 2:

输入:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

2. 题解#

Python3 点击展开代码
20 lines 展开代码

3. 二刷#

秒了,这玩意也就考一遍套路


搜索二维矩阵 II#

240. 搜索二维矩阵 II#

难度:中等

编写一个高效的算法来搜索 _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

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -10^9 <= target <= 10^9

1. 题解#

Python3 点击展开代码
30 lines 展开代码

2. 反思#

  1. 其实建议直接记住,另外注意输入的时候最后target的处理方式,即我们先拿到所有数据,然后再提取需要的量(用切片)

3. 二刷#

右上角的要用i、j和m、n分开,思路倒是见一次就会了


相交链表#

160. 相交链表#

难度:简单

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意 ,函数返回结果后,链表必须 保持其原始结构

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headAheadB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

示例 2:

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,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
输出:No intersection
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

提示:

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 10^4
  • 1 <= Node.val <= 10^5
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listAlistB 没有交点,intersectVal0
  • 如果 listAlistB 有交点,intersectVal == listA[skipA] == listB[skipB]

进阶: 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?

1. 题解#

Python3 点击展开代码
67 lines 展开代码

2. 反思#

  1. 如果是正常做思路非常简单的,但是如果要用ACM模式做,就要熟练掌握怎么写这些额外函数、怎么建链表,貌似精力都放在这上面来了。这题没让输出链表,不然还要写一个print_linked_list函数。

3. 二刷#

不过是构建相交链表麻烦点,还有注意p可能为None,注意空值保护


反转链表#

1. 题面#

206. 反转链表#

难度:简单

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶: 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

2. 题解#

Python3 点击展开代码
38 lines 展开代码

3. 反思#

  1. 这题多重赋值是Python最优雅的翻转链表方案,但是这一句要注意顺序问题。左边第一个目标是 curr.next,它会先把"旧 curr 的 next"改掉,然后再更新 prev 和 curr,这个顺序才是对的。

4. 二刷#

秒了。注意多重赋值顺序


回文链表#

1. 题面#

234. 回文链表#

难度:简单

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

示例 1:

输入:head = [1,2,2,1]
输出:true

示例 2:

输入:head = [1,2]
输出:false

提示:

  • 链表中节点数目在范围[1, 10^5]
  • 0 <= Node.val <= 9

进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

2. 题解#

Python3 点击展开代码
42 lines 展开代码

3. 反思#

  1. 本题是找中点、翻转的合并。关键点在于根据fast的位置,可以判断出链表的奇偶,从而决定从什么位置开始翻转后半部分。

4. 二刷#

差点又掉坑里了,一定要fast and fast.next才行,然后,加dummy是偶数中前/奇数中间,不加dummy是偶数中后/奇数中间#

环形链表#

1. 题面#

141. 环形链表#

难度:简单

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos-1 或者链表中的一个 有效索引

进阶: 你能用 O(1)(即,常量)内存解决此问题吗?

2. 题解#

Python3 点击展开代码
38 lines 展开代码

3. 反思#

  1. 注意这题的ACM模式,在建链表的时候也建一个nodes数组,这样方便我们直接看pos的位置。

4. 二刷#

二刷就先不做了,一眼可以想到快慢指针法,但是定义输入比较麻烦,一般不会出这样的题目。

5. 三刷#

出现了以下的错误写法:

Python3 点击展开代码
9 lines 展开代码

这要是没有环直接就炸了,一定要记得一个fast and fast.next的逻辑,非常常用。


环形链表 II#

1. 题面#

142. 环形链表 II#

难度:中等

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置( 索引从 0 开始 )。如果 pos-1,则在该链表中没有环。 注意:pos 不作为参数进行传递 ,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

进阶: 你是否可以使用 O(1) 空间解决此题?

2. 题解#

Python3 点击展开代码
44 lines 展开代码

3. 反思#

  1. 没啥好说的,记结论

4. 二刷#

同上题,二刷跳过


合并两个有序链表#

1. 题面#

21. 合并两个有序链表#

难度:简单

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1l2 均按 非递减顺序 排列

2. 题解#

Python3 点击展开代码
48 lines 展开代码

3. 二刷#

秒了


两数相加#

1. 题面#

2. 两数相加#

难度:中等

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

  • 每个链表中的节点数在范围 [1, 100]
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

2. 题解#

Python3 点击展开代码
48 lines 展开代码

3. 反思#

  1. 依旧直接背板,一定要熟练。易错点两个,一个是l1不为空才能next,另一个是carry和total都是本轮算本轮的,千万别+=

4. 二刷#

二刷犯下的错误是next之前忘了判断l1 or l2是否已经为空了。其他倒是没什么可说的。

5. 拓展1 - 正序字符串#

如果给的是正序两个字符串怎么办,这是一般的符合直觉的大数加法题,解法也合直觉,从末尾往前加,最后返回答案的时候进行一次翻转。注意用ord(字符)-ord('0')转数字即可。

Python3 点击展开代码
18 lines 展开代码

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

1. 题面#

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

难度:中等

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

进阶: 你能尝试使用一趟扫描实现吗?

2. 题解#

Python3 点击展开代码
46 lines 展开代码

3. 反思#

  1. 注意点只有一个,就是删除节点要加dummy,因为头也可能被删

4. 二刷#

注意点同上,不用重复写了


两两交换列表中的节点#

1. 题面#

24. 两两交换链表中的节点#

难度:中等

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

2. 题解 1 · 直接翻转#

Python3 点击展开代码
48 lines 展开代码

3. 题解 2 · 递归处理#

Python3 点击展开代码
39 lines 展开代码

4. 反思#

  1. 这题第一种解法在解决k个翻转的时候也很给力,递归的解法最容易理解代码最简洁,都需要掌握

5. 二刷#

递归秒了。注意如果准备直接翻转的话要自己额外定义tail(也就是每次翻转的curr)


k个一组翻转链表#

1. 题面#

25. K 个一组翻转链表#

难度:困难

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶: 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

2. 题解#

Python3 点击展开代码
57 lines 展开代码

3. 题解 2 · 递归#

Python3 点击展开代码
45 lines 展开代码

4. 反思#

  1. 和上提一样,一个直接做,一个递归。直接做有助于思考三指针翻转后的指针都在哪,递归则是容易理解好做的思路。

5. 二刷#

递归很容易想到,这次我用了一个辅助函数来统计k,和递归内走k格子看空不空一样。


随机链表的复制#

1. 题面#

138. 随机链表的复制#

难度:中等

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝 。 深拷贝应该正好由 n全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。 复制链表中的指针都不应指向原链表中的节点

例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为 null

你的代码 接受原链表的头节点 head 作为传入参数。

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

提示:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.randomnull 或指向链表中的节点。

2. 题解#

Python3 点击展开代码
72 lines 展开代码

3. 反思#

  1. 重点看solution部分,但是也可以看一下python的厉害。先用replace换成可以解析的字面量,然后用ast.literal_eval(…),可以直接解析,将字符串形式的嵌套列表,转化为真列表。

4. 二刷#

没有再刷了,输入输出弄的太麻烦,思路其实很简单。originToClone[p].next = originToClone[p.next]这句话理解清楚就行。


排序链表#

1. 题面#

148. 排序链表#

难度:中等

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0, 5 * 10^4]
  • -10^5 <= Node.val <= 10^5

**进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

2. 题解 1 · 数组复制#

Python3 点击展开代码
32 lines 展开代码

3. 题解 2 · 归并排序#

Python3 点击展开代码
60 lines 展开代码

4. 反思#

  1. 这一题想看的是解法二,解法一纯钻空子。注意这里有三步,首先设置递归出口,然后快慢指针寻找中点(注意这里的fast设置在head.next的起点,就可以自然让slow停在mid前面,不用借助dummy),最后递归排序两边。后面是标准的排序两个有序链表的过程。
  2. 然后就是力扣里面函数本身带self,记得递归的时候self.func

5. 二刷#

  1. 想到用分治了,不断进行下去直到两边都有序。但是问题是忘记了最关键的部分,也就是mid = slow.next和slow.next = None。为什么要先断开后面的链表?否则左侧会一直走到右侧,就不是想要的合并两边有序链表了。不用担心会被切碎碎,因为后面合并的步骤会组装起来。
  2. 虽然跟这题关系不大,但是合并时p.next = left if left else right可以体现python的简洁美。

6. 拓展#

这一题,就是经典的归并排序链表版。我们下面可以给出数组版本的归并排序:

Python3 点击展开代码
26 lines 展开代码

一般我们喜欢把merge函数拎出去,这样看起来更清楚。本题的链表归并排序,也可以写成这样:

Python3 点击展开代码
43 lines 展开代码

7. 题解3#

竟然有人面试被问到了链表的快速排序,那就也在这里做一下。一般快排做法是选枢纽,断三段,最后递归排序左右两段,然后拼接。在链表中,这个pivot一般就取头结点(数组中是randomint)。(不用 tail 也能 append,但是每次需要遍历到末尾。为了方便append,我们改动一下尾插法,让每次返回的一个元组,包含head和tail节点)。

Python3 点击展开代码
44 lines 展开代码

合并 K 个升序链表#

1. 题面#

23. 合并 K 个升序链表#

难度:困难

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 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 = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4

2. 题解 1 · 堆排序#

Python3 点击展开代码
57 lines 展开代码

3. 题解 2 · 分治#

Python3 点击展开代码
80 lines 展开代码

4. 反思#

  1. 第一种方案是用堆自动排序,体现了堆可以存很多种不同的结果;第二种则是分治算法的体现,理解稍微复杂,实际上就是分成两边做让递归数尽可能矮。本质上也是先分两边不断递归排完left、right,然后进行两个有序链表合并的归并。

5. 二刷#

理解了归并排序之后,这次也能轻松写出归并算法了,但是递归出口还是写错了。要注意两个:

  1. 递归出口不用写2,可以交给后面统一分治;
  2. 递归出口返回的一定要是函数期望返回的类型,这是底线。

本题比上述题解更简洁的做法如下:

Python3 点击展开代码
58 lines 展开代码

LRU缓存#

1. 题面#

146. LRU 缓存#

难度:中等

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 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

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 10^5
  • 最多调用 2 * 10^5getput

2. 题解#

Python3 点击展开代码
90 lines 展开代码

3. 反思#

  1. 这题代码看似复杂,实际上就是打一个双链表板子。

4. 二刷#

最近听到面试的时候经常会被问LRU的升级版,比如支持并发的LRU,支持TTL的LRU,很恶心。接下来给一个带TTL和并发锁的最简单升级版:

Python3 点击展开代码
76 lines 展开代码

二叉树的中序遍历#

1. 题面#

94. 二叉树的中序遍历#

难度:简单

给定一个二叉树的根节点 root ,返回 它的 中序 遍历

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?


Python3 点击展开代码
68 lines 展开代码

2. 反思#

  1. 中序遍历不难,主要是ACM模式读取和建树。ast读取列表,replace把null换成None。
  2. 板子的易错点:层序建树要时刻用i监督是否超过data长度,打印层序的时候别忘了先判空再入队,然后就是空树的各种边界保护。

3. 二刷#

秒了。树的二刷只写核心代码,不过确实也发现自己写不好建树了。其实就是注意用i标识数组有没有走完,遇到None的时候不管(我们的数组里有None,但是不能挂)


二叉树的最大深度#

1. 题面#

104. 二叉树的最大深度#

难度:简单

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

提示:

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

2. 题解#

Python3 点击展开代码
53 lines 展开代码

3. 二刷#

秒了

4. 题解2#

最简单的方案其实是让dfs直接返回深度

Python3 点击展开代码
12 lines 展开代码

翻转二叉树#

1. 题面#

226. 翻转二叉树#

难度:简单

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

示例 2:

输入:root = [2,1,3]
输出:[2,3,1]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目范围在 [0, 100]
  • -100 <= Node.val <= 100

2. 题解#

Python3 点击展开代码
68 lines 展开代码

3. 反思#

  1. 有时候会担心翻转之后dfs会不会乱了,或者需要调整成先right后left。其实不用,dfs只是为了遍历,即使左右换了,还是可以遍历,只不过遍历顺序变了。

4. 二刷#

秒了

5. 解法2#

学完了树形dp之后,这题更自然会让我想到从下往上组装,因此可以解法如下:

Python3 点击展开代码
16 lines 展开代码

对称二叉树#

1. 题面#

101. 对称二叉树#

难度:简单

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

  • 树中节点数目在范围 [1, 1000]
  • -100 <= Node.val <= 100

进阶: 你可以运用递归和迭代两种方法解决这个问题吗?

2. 题解#

Python3 点击展开代码
73 lines 展开代码

3. 反思#

  1. 第一次写懵逼,第二次写想看左侧左根右和右侧右根左是否一样,样例虽然能过,但是忽略了其实一个顺序是确定不了树的。

4. 二刷#

被秒了。想到了是分别走,但是没想到用递归,递归的核心代码非常简洁,看清判断的条件,用and链接左左右右、左右右左即可。


二叉树的直径#

1. 题面#

543. 二叉树的直径#

难度:简单

给你一棵二叉树的根节点,返回该树的 直径

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root

两节点之间路径的 长度 由它们之间边数表示。

示例 1:

输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2:

输入:root = [1,2]
输出:1

提示:

  • 树中节点数目在范围 [1, 10^4]
  • -100 <= Node.val <= 100

2. 题解#

Python3 点击展开代码
77 lines 展开代码

3. 反思#

  1. 这题有一个dfs直接计算最大深度,可以仔细看一下写法。
  2. 中间比较更新一个nonlocal量是常用的递归更新全局量。

4. 二刷#

被秒了。其实就是求最大深度的代码,然后中间记录更新一下直径。


二叉树的层序遍历#

1. 题面#

102. 二叉树的层序遍历#

难度:中等

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

2. 题解 1 · 队列法#

Python3 点击展开代码
76 lines 展开代码

3. 题解 2 · dfs+depth#

Python3 点击展开代码
73 lines 展开代码

4. 题解 3 · IDDFS#

Python3 点击展开代码
87 lines 展开代码

5. 反思#

  1. 这题我记得面试考过一次,不用队列BFS,所以就总结一下所有广搜的方法。

6. 二刷#

队列法随便秒。dfs+depth的方法有点忘了,再看看。核心在于用depth == len(ans)来判断新层。


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

1. 题面#

108. 将有序数组转换为二叉搜索树#

难度:简单

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。

示例 1:

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums严格递增 顺序排列

2. 题解#

Python3 点击展开代码
75 lines 展开代码

3. 反思#

  1. 一开始以为要写ACL树,吓死我了。这一题主要注意两点,一个是两半递归的时候,切片的位置要避开root,然后mid从长度或者从长度-1开始切都是对的,正好得到的就是示例两种答案(偏左和偏右)。
  2. 另一点是这题需要打印空,升级了一下print,具体写法是不在入队前检查None,在加ans时检查None。

4. 二刷#

果然一刷没亲自写出来的题印象就不深,又没写出来。思路其实很简单,就是不断拉出来重点当root就行了。


验证二叉搜索树#

1. 题面#

98. 验证二叉搜索树#

难度:中等

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

提示:

  • 树中节点数目范围在[1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1

2. 题解#

Python3 点击展开代码
67 lines 展开代码

3. 反思#

  1. 这题易错点是容易只考虑当前父子直接递归,BST的约束是跨越整个树的,这样会漏掉跨层约束。
  2. 真正的做法是一直维持上下界,往左走要更新上界(因为左边都要小),往右走更新上界,遍历一遍全部判断。

4. 二刷#

算是弄出来了,但是记得判空永远在最前面,因为要访问val。#

二叉搜索树中第 K 小的元素#

1. 题面#

230. 二叉搜索树中第 K 小的元素#

难度:中等

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(k 从 1 开始计数)。

示例 1:

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

提示:

  • 树中的节点数为 n
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?

2. 题解 1#

Python3 点击展开代码
70 lines 展开代码

3. 题解 2 · 进阶#

Python3 点击展开代码
87 lines 展开代码

4. 反思#

  1. 进阶方法运用了python动态绑定属性的方法,很巧妙。

5. 二刷#

这第二种方法也太哈人了,代码不长,但是逻辑好绕啊。我们先要走一遍,给每个节点多维持一个子树大小属性。注意,这里的size的含义,是以当前node为根的子树的size,当然要+1包含自身。然后,我们去找左边size为k-1的,如果左边不够k-1了,直接去右边找k-1-left_size,这就是核心代码。


二叉树的右视图#

1. 题面#

199. 二叉树的右视图#

难度:中等

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例 1:

**输入:**root = [1,2,3,null,5,null,4]

输出: [1,3,4]

解释:

示例 2:

**输入:**root = [1,2,3,4,null,null,null,5]

输出:[1,3,4,5]

解释:

示例 3:

输入: root = [1,null,3]

输出: [1,3]

示例 4:

**输入:**root = []

输出: []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

2. 题解#

Python3 点击展开代码
73 lines 展开代码

3. 二刷#

层序遍历看q[-1]即可


二叉树展开为链表#

1. 题面#

114. 二叉树展开为链表#

难度:中等

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

提示:

  • 树中结点数在范围 [0, 2000]
  • -100 <= Node.val <= 100

进阶: 你可以使用原地算法(O(1) 额外空间)展开这棵树吗?

2. 题解#

Python3 点击展开代码
83 lines 展开代码

3. 题解 · 进阶#

Python3 点击展开代码
87 lines 展开代码

4. 反思#

  1. 第二种原地结果比较难想,多看看板子。

5. 二刷#

被秒杀,重新看板子,说实话非常绕。。

6. 题解2#

本题实际上还有一种非常通俗容易解决的方案,我们会发现展开后的顺序实际上就是先序遍历的顺序,那么我们可以反着来(右左根),逆着先序将每个节点接到上一个的前面,最终就可以完成。不过这种解法也是空间O(h)就是了。

Python3 点击展开代码
13 lines 展开代码

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

1. 题面#

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

难度:中等

给定两个整数数组 preorderinorder ,其中 preorder 是二叉树的 先序遍历inorder 是同一棵树的 中序遍历 ,请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorderinorder无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

2. 题解#

Python3 点击展开代码
85 lines 展开代码

3. 反思#

  1. 这题的难点在切片的位置判断,需要多练习。

4. 二刷#

大体想到了解决方式,就是preorder的下标处理还是有点问题。中左右切分的时候,左的长度已经用idx给出,其实可以直接在示例数组上自己切一下看看。


路径总和 III#

1. 题面#

437. 路径总和 III#

难度:中等

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

示例 1:

输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。

示例 2:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

2. 题解#

Python3 点击展开代码
71 lines 展开代码

3. 反思#

  1. 这题好难,得用两个递归。首先是找从这个节点开始,递归找有没有路径。然后递归每个节点加上当前和左右的路径和。能自己写出这题的递归已经对树的递归非常熟练了。

4. 反思#

被秒了,对于这种,起点可以是根也可以不是的,大部分需要用到递归式子运算。比如这题的返回count_from(root, targetSum)+ solution(root.left, targetSum)+ solution(root.right, targetSum),这里count_from仅表示以xx为起点的有多少路径符合条件,而solution本身是整个树有多少符合的(即count_all),所以这是两层递归在一起。


二叉树的最近公共祖先#

1. 题面#

236. 二叉树的最近公共祖先#

难度:中等

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:"对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是它自己的祖先 )。"

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

提示:

  • 树中节点数目在范围 [2, 10^5] 内。
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同
  • p != q
  • pq 均存在于给定的二叉树中。

2. 题解 · parent属性#

Python3 点击展开代码
68 lines 展开代码

3. 题解 2 · 递归#

Python3 点击展开代码
60 lines 展开代码

4. 反思#

  1. 这题第二种LCA算法是最优雅的解法,请记住板子。

5. 二刷#

还是没想到递归方法,但是LCA算法的确看起来优雅。几个要点,solution表示子树中p、q的最近公共祖先,而出口是找到p、q或者为空,上交left和right两个信息,只有left和right都非空(也就是左右两边找到了),由于是从底向上的,所以就是第一个汇合的地方。如果只有一遍是空的,那应该将非空返回上去继续找。(由于还要满足祖先深度尽可能大,所以找到root继续上交)


二叉树中的最大路径和#

1. 题面#

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

难度:困难

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

示例 1:

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

提示:

  • 树中节点数目范围是 [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000

2. 题解#

Python3 点击展开代码
62 lines 展开代码

3. 反思#

  1. 我草,好难,暂时不看,回头理解背板

4. 二刷#

本题结合二叉树直径一起看!

5. 拓展#

本题和二叉树直径题,都是"答案都可能在某个节点这里,把左边一条链 + 当前节点 + 右边一条链 拼起来"的题目,每个节点都尝试作为"拐点"结算一次答案。

Python3 点击展开代码
5 lines 展开代码

return必须写成单链状态来返回父节点,因为父节点只能接左边或右边的一条。而更新答案的时候,两边都加。 并排记忆如下:

  1. 二叉树直径
Python3 点击展开代码
7 lines 展开代码
  1. 二叉树最大路径和
Python3 点击展开代码
7 lines 展开代码

岛屿数量#

1. 题面#

200. 岛屿数量#

难度:中等

给你一个由 '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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0''1'

2. 题解#

Python3 点击展开代码
37 lines 展开代码

3. 反思#

  1. dfs在图里的经典用法

4. 二刷#

二刷中,我把dfs写成了这样:

Python3 点击展开代码
13 lines 展开代码

AI说,这不是稳妥的写法,大多数人写dfs的时候,会首先判断是否合法,然后再走四个方向,就是按照第一次的题解一样,在入口判断是否有越界或者等于'1'。


腐烂的橘子#

1. 题面#

994. 腐烂的橘子#

难度:1433

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

  • 0 代表空单元格;
  • 1 代表新鲜橘子;
  • 2 代表腐烂的橘子。

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1

示例 1:

输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
输出:4

示例 2:

输入:grid = [[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个方向上。

示例 3:

输入:grid = [[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 012

2. 题解#

Python3 点击展开代码
40 lines 展开代码

3. 反思#

  1. 这种题看起来思路简单,但是比较考验你的写法和边界条件,建议平时多敲练习。

4. 二刷#

想到的方法solution解决每轮感染,返回是否有修改的flag。如果没修改且不存在新鲜橘子就结束了,这种方式修改需要先遍历单独标记,然后再统一腐烂。

其实题解的方法还是比较好的,这是一种多源头bfs的解法,很直观且容易理解(因为橘子每次最多感染一层),对比之前的岛屿问题,则是多源dfs。


课程表#

1. 题面#

207. 课程表#

难度:中等

你这个学期必须选修 numCourses 门课程,记为 0numCourses - 1

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai必须 先学习课程 bi

  • 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1

请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false

示例 1:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

示例 2:

输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

提示:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

2. 题解#

Python3 点击展开代码
38 lines 展开代码

3. 反思#

  1. 拓扑排序给有向图判环是经典算法。

4. 二刷#

有点忘了建图的语句了,邻接表建图法可以多复习一下。


实现 Trie (前缀树)#

1. 题面#

208. 实现 Trie (前缀树)#

难度:中等

Trie (发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补全和拼写检查。

请你实现 Trie 类:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false

示例:

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
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

提示:

  • 1 <= word.length, prefix.length <= 2000
  • wordprefix 仅由小写英文字母组成
  • insertsearchstartsWith 调用次数 总计 不超过 3 * 10^4

2. 题解#

Python3 点击展开代码
79 lines 展开代码

3. 反思#

  1. 记住思路了背板很简单

4. 二刷#

差不多能秒,还是多看板子,写的很优雅。


全排列#

1. 题面#

46. 全排列#

难度:中等

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

2. 题解#

Python3 点击展开代码
33 lines 展开代码

3. 反思#

  1. 用python写的话,一般都是把递归写成函数中的函数,而不是用全局量。这一题的思路不难,主要是递归设计容易弄错。

4. 二刷#

首先是dfs的选择,适用于选择一条答案走到底再回头。另外,二刷选择了set,当然这一题数值不重复是没问题的,但是最好记录"下标是否使用过",这样有重复元素也没关系。也就是说,我们用seen = [False] * n


子集#

1. 题面#

78. 子集#

难度:中等

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

2. 题解#

Python3 点击展开代码
27 lines 展开代码

3. 反思#

  1. 同样是比较标准的递归,属于是不能回头查的递归,所以维持一个深度i(这里就是num的长度),递归过程中达到深度存下所有叶子答案

4. 二刷#

这一题也可以像上一题一样遍历添加,然后回溯,只要给dfs维持一个start就可以保证不重复添加。这种方法可以保证顺序比较符合人类直觉:

Python3 点击展开代码
20 lines 展开代码

电话号码的字母组合#

1. 题面#

17. 电话号码的字母组合#

难度:中等


给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = "2"
输出:["a","b","c"]

提示:

  • 1 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

2. 题解#

Python3 点击展开代码
30 lines 展开代码

3. 反思#

  1. 又是一个很好的递归,这题的情形是求笛卡尔积,跟上一题一样,是固定位数的递归,不过上一题是选或不选,这一题是选什么,所以多了一个循环来看选什么,递归写在循环里。

4. 二刷#

写错了一个关键的点,就是这题同样属于逐位判断,dfs维持一个位置(换句话说不能回头选)。


组合总和#

1. 题面#

39. 组合总和#

难度:中等

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

2. 题解#

Python3 点击展开代码
31 lines 展开代码

3. 反思#

  1. 本题是可以重复选的,其实也是只要分为选和不选,但是选的时候不用移动i就行了。然后同时用i和target监视。

4. 二刷#

第一遍错误按照所有组合算总和,223、232、322都算进去了。但是,实际上可以维持一个循环开始搜索的位置start就可以保证不回头选,这也说明了维持位置i和维持start开始遍历是某些情况等效的:

  • i 版本:显式地写"选 / 不选当前下标"
  • start 版本:用 for 一次性枚举"从当前下标开始能选谁"

其实后一种情况可以适配的情况还更多,包括组合、子集、组合总和I/II、固定长度组合都可以用。

Python3 点击展开代码
22 lines 展开代码

括号生成#

1. 题面#

22. 括号生成#

难度:中等

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

2. 题解#

Python3 点击展开代码
33 lines 展开代码

3. 反思#

  1. 难点在dfs的边界条件,还有这里传入的量也不一样,每一题dfs可以灵活传入不同的量,也可以直接按每题都dfs空,把需要维护的量写外面nonlocal。

4. 二刷#

SKIP了,括号好烦好烦,等会做专题一并解决。


单词搜索#

1. 题面#

79. 单词搜索#

难度:中等

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出:true

示例 2:

输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出:true

示例 3:

输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardword 仅由大小写英文字母组成

进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

2. 题解#

Python3 点击展开代码
46 lines 展开代码

3. 反思#

  1. 多源dfs,注意图dfs的时候要标记自身(或者用visted的),递归完再恢复。有越界和非字母两种返回情形。

分割回文串#

1. 题面#

131. 分割回文串#

难度:中等

给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

2. 题解#

Python3 点击展开代码
33 lines 展开代码

N皇后#

1. 题面#

51. N 皇后#

难度:困难

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

2. 题解#

Python3 点击展开代码
40 lines 展开代码

搜索插入位置#

1. 题面#

35. 搜索插入位置#

难度:简单

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums无重复元素升序 排列数组
  • -10^4 <= target <= 10^4

2. 题解 · 左闭右闭#

Python3 点击展开代码
20 lines 展开代码

3. 题解 · 左闭右开#

Python3 点击展开代码
18 lines 展开代码

4. 反思#

  1. 本题主要是要注意,在左闭右闭过程中,二分搜索中全T的情况,这样要判断末尾,left不会停到数组外。但是如果是左闭右开就无所谓。

搜索二维矩阵#

1. 题面#

74. 搜索二维矩阵#

难度:中等

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false

示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

2. 题解#

Python3 点击展开代码
23 lines 展开代码

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

1. 题面#

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

难度:中等

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

2. 题解#

Python3 点击展开代码
40 lines 展开代码

3. 反思#

  1. 采取了统一的TTFFF方法,注意左闭右开left最后可能出界,然后右边界的时候可能left-1越界,细看边界保护就好。

4. 二刷#

统一采用left落在第一个T的二分查找,即左闭右开,然后特殊判断是否满足题目要求即可。


搜索旋转排序数组#

1. 题面#

33. 搜索旋转排序数组#

难度:中等

整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 向左旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2]

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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

2. 题解#

Python3 点击展开代码
53 lines 展开代码

3. 反思#

  1. 这里findK对于找pivot的方法比较巧妙,可以仔细看看。

4. 二刷#

二刷写错了找pivot的方式,属于错误判断了FFFTTT和FFFTFF,用趋势来判断不行,必须用数组最后一位来判断,小于等于它的为右半边的T,大于它的为左半边的F。

但是,这一题更好的解法是直接一次二分,因为二分之后总有一半是有序的,先看target在不在这个有序区间内,在就进入这半边,不在就去另一边。

Python3 点击展开代码
23 lines 展开代码

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

1. 题面#

153. 寻找旋转排序数组中的最小值#

难度:中等

已知一个长度为 n 的数组,预先按照升序排列,经由 1n旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1n 次旋转

2. 题解#

Python3 点击展开代码
19 lines 展开代码

寻找两个正序数组的中位数#

1. 题面#

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

难度:困难

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 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

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

2. 题解#

Python3 点击展开代码
42 lines 展开代码

3. 反思#

  1. 直接O(m+n)很简单,二分太复杂了好恶心,暂时先不看。

有效的括号#

1. 题面#

20. 有效的括号#

难度:简单

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

**输入:**s = "()"

**输出:**true

示例 2:

**输入:**s = "()[]{}"

**输出:**true

示例 3:

**输入:**s = "(]"

**输出:**false

示例 4:

**输入:**s = "([])"

**输出:**true

示例 5:

**输入:**s = "([)]"

**输出:**false

提示:

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

2. 题解#

Python3 点击展开代码
24 lines 展开代码

最小栈#

1. 题面#

155. 最小栈#

难度:中等

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["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.

提示:

  • -2^31 <= val <= 2^31 - 1
  • poptopgetMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 10^4

2. 题解#

Python3 点击展开代码
51 lines 展开代码

字符串编码#

1. 题面#

394. 字符串解码#

难度:中等

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。

测试用例保证输出的长度不会超过 10^5

示例 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"

提示:

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

2. 题解#

Python3 点击展开代码
35 lines 展开代码

每日温度#

1. 题面#

739. 每日温度#

难度:中等

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示:

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

2. 题解#

Python3 点击展开代码
19 lines 展开代码

柱状图中最大的矩形#

1. 题面#

84. 柱状图中最大的矩形#

难度:困难

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

输入: heights = [2,4]
输出: 4

提示:

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

2. 题解#

Python3 点击展开代码
28 lines 展开代码

3. 反思#

  1. 一定要注意还可以向左延伸。单调递增栈 -> 找左侧第一个比curr小的;单调递减栈 -> 找右侧第一个比弹出大的

数组中的第K个最大元素#

1. 题面#

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

难度:中等

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

2. 题解#

Python3 点击展开代码
40 lines 展开代码

3. 反思#

  1. 快速选择算法,没听说过!还得细看。

前 K 个高频元素#

1. 题面#

347. 前 K 个高频元素#

难度:中等

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

**输入:**nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2:

**输入:**nums = [1], k = 1

输出:[1]

示例 3:

**输入:**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出: [1,2]

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

2. 题解#

Python3 点击展开代码
22 lines 展开代码

数据流的中位数#

1. 题面#

295. 数据流的中位数#

难度:困难

中位数 是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -10^5 <= num <= 10^5
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 10^4 次调用 addNumfindMedian

2. 题解#

Python3 点击展开代码
46 lines 展开代码

买卖股票的最佳时机#

1. 题面#

121. 买卖股票的最佳时机#

难度:简单

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

2. 题解#

Python3 点击展开代码
20 lines 展开代码

跳跃游戏#

1. 题面#

55. 跳跃游戏#

难度:中等

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

2. 题解#

Python3 点击展开代码
19 lines 展开代码

跳跃游戏 II#

1. 题面#

45. 跳跃游戏 II#

难度:中等

给定一个长度为 n0 索引 整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在索引 i 处,你可以跳转到任意 (i + j) 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 n - 1

2. 题解#

Python3 点击展开代码
26 lines 展开代码

划分字母区间#

1. 题面#

763. 划分字母区间#

难度:1443

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。例如,字符串 "ababcc" 能够被分为 ["abab", "cc"],但类似 ["aba", "bcc"]["ab", "ab", "cc"] 的划分是非法的。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s

返回一个表示每个字符串片段的长度的列表。

示例 1:

输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。

示例 2:

输入:s = "eccbbbbdec"
输出:[10]

提示:

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

2. 题解#

Python3 点击展开代码
25 lines 展开代码

爬楼梯#

1. 题面#

70. 爬楼梯#

难度:简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

2. 题解#

Python3 点击展开代码
14 lines 展开代码

杨辉三角#

1. 题面#

118. 杨辉三角#

难度:简单

给定一个非负整数 _numRows,_生成「杨辉三角」的前 numRows 行。

「杨辉三角」 中,每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

2. 题解#

Python3 点击展开代码
22 lines 展开代码

打家劫舍#

1. 题面#

198. 打家劫舍#

难度:中等

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 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 。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

2. 题解#

Python3 点击展开代码
18 lines 展开代码

3. 反思#

  1. 注意这里dp[i]的含义,我们不需要遍历前面最大的dp,只要看dp[i-2]就行

完全平方数#

1. 题面#

279. 完全平方数#

难度:中等

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

  • 1 <= n <= 10^4

2. 题解#

Python3 点击展开代码
17 lines 展开代码

3. 反思#

  1. 这题好像默认一定能选出来,否则的话输出dp[n]还需要加一个无穷保护。

零钱兑换#

1. 题面#

322. 零钱兑换#

难度:中等

给你一个整数数组 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

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

2. 题解#

Python3 点击展开代码
17 lines 展开代码

3. 反思#

  1. 同样是完全背包问题,易错点是忘了让dp[0] = 0了。

单词拆分#

1. 题面#

139. 单词拆分#

难度:中等

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 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

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • swordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

2. 题解#

Python3 点击展开代码
24 lines 展开代码

3. 反思#

  1. 注意完全背包防止覆盖,最大最小问题往往会有min、max里面加上本身,T or F问题则是or一下本身。

最长递增子序列#

1. 题面#

300. 最长递增子序列#

难度:中等

给你一个整数数组 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

提示:

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

进阶:

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2. 题解#

Python3 点击展开代码
14 lines 展开代码

3. 反思#

  1. 本题的dp有点变化,首先是全部要初始化成1,因为至少也有本身数字这一个序列,所以也不需要初始化一个边界兜底。然后就是,最后要求的不是到最后一位的最长递增子序列,所以应该在dp里面找最大值。

乘积最大子数组#

1. 题面#

152. 乘积最大子数组#

难度:中等

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意 ,一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何子数组的乘积都 保证 是一个 32-位 整数

2. 题解#

Python3 点击展开代码
23 lines 展开代码

3. 反思#

  1. 本题考虑负数的翻转,需要额外维护变量,比较恶心

分割等和子集#

1. 题面#

416. 分割等和子集#

难度:中等

给你一个 只包含正整数非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

2. 题解 1 · 递归(时间超限)#

Python3 点击展开代码
22 lines 展开代码

3. 题解 2 · 0/1背包#

Python3 点击展开代码
26 lines 展开代码

4. 反思#

  1. 这是一道0/1背包,注意和完全背包区分来学

最长有效括号#

1. 题面#

32. 最长有效括号#

难度:困难

给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号 子串 的长度。

左右括号匹配,即每个左括号都有对应的右括号将其闭合的字符串是格式正确的,比如 "(()())"

示例 1:

输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""
输出:0

提示:

  • 0 <= s.length <= 3 * 10^4
  • s[i]'('')'

2. 题解#

Python3 点击展开代码
31 lines 展开代码

3. 反思#

  1. 这题算是dp的大boss了。。

不同路径#

1. 题面#

62. 不同路径#

难度:中等

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 "Start" )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 "Finish" )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10^9

2. 题解#

Python3 点击展开代码
22 lines 展开代码

3. 反思#

  1. 标准的多维dp

最小路径和#

1. 题面#

64. 最小路径和#

难度:中等

给定一个包含非负整数的 _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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

2. 题解#

Python3 点击展开代码
26 lines 展开代码

3. 反思#

  1. 没啥说的,还是二维dp

最长回文子串#

1. 题面#

5. 最长回文子串#

难度:中等

给你一个字符串 s,找到 s 中最长的 回文 子串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

2. 题解 1 · 二维dp#

Python3 点击展开代码
38 lines 展开代码

3. 题解 2 · 中心拓展#

Python3 点击展开代码
32 lines 展开代码

最长公共子序列#

1. 题面#

1143. 最长公共子序列#

难度:中等

给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。

示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。

示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。

提示:

  • 1 <= text1.length, text2.length <= 1000
  • text1text2 仅由小写英文字符组成。

2. 题解#

Python3 点击展开代码
19 lines 展开代码

编辑距离#

1. 题面#

72. 编辑距离#

难度:中等

给你两个单词 word1word2请返回将 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')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1word2 由小写英文字母组成

2. 题解#

Python3 点击展开代码
30 lines 展开代码

3. 反思#

  1. 上面两题都是把两个字符串当做二维DP,天然就是"第一个串处理到 i,第二个串处理到 j",算是比较经典

只出现一次的数字#

1. 题面#

136. 只出现一次的数字#

难度:简单

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入: nums = [2,2,1]

输出: 1

示例 2 :

输入: nums = [4,1,2,1,2]

输出: 4

示例 3 :

输入: nums = [1]

输出: 1

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

2. 题解#

Python3 点击展开代码
11 lines 展开代码

多数元素#

1. 题面#

169. 多数元素#

难度:简单

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入:nums = [3,2,3]
输出:3

示例 2:

输入:nums = [2,2,1,1,1,2,2]
输出:2

提示:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • 输入保证数组中一定有一个多数元素。

进阶: 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

2. 题解#

Python3 点击展开代码
24 lines 展开代码

3. 反思#

  1. 这题的幽默之处在于你用Counter硬记数反而时间还更快了。。这就是底层优化的力量么

颜色分类#

1. 题面#

75. 颜色分类#

难度:中等

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 012 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1]
输出:[0,1,2]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i]012

进阶:

  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

2. 题解#

Python3 点击展开代码
28 lines 展开代码

下一个排列#

1. 题面#

31. 下一个排列#

难度:中等

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3][1,3,2][3,1,2][2,3,1]

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

  • 例如,arr = [1,2,3] 的下一个排列是 [1,3,2]
  • 类似地,arr = [2,3,1] 的下一个排列是 [3,1,2]
  • arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]

示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]

示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

2. 题解#

Python3 点击展开代码
32 lines 展开代码

3. 反思#

  1. 通常叫下一个排列算法,还是直接看板子理解意思即可。

寻找重复数#

1. 题面#

287. 寻找重复数#

难度:中等

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1:

输入:nums = [1,3,4,2,2]
输出:2

示例 2:

输入:nums = [3,1,3,4,2]
输出:3

示例 3 :

输入:nums = [3,3,3,3,3]
输出:3

提示:

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

进阶:

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

2. 题解#

Python3 点击展开代码
28 lines 展开代码

专题阅读

算法

这篇文章属于同一条阅读链。你可以直接在这里切换,不用再回到列表页重新找。

当前进度7 / 7

留言区

留言

欢迎纠错、补充、交流。昵称和评论内容必填;如果你愿意,也可以留下联系方式,仅站主可见。

0

正在加载评论...

0 / 2000

阅读导航

文章目录

当前阅读位置将在这里显示

0 节