力扣刷题笔记

392. 判断子序列

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true
1
2

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false
1
2

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
1
2
3

代码

• 双指针法
  时间复杂度 O(N)： 其中 N为字符串 t 的长度。最差情况下需完整遍历 t 。
  空间复杂度 O(1) ： i , j 变量使用常数大小空间。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s: return True
        i = 0
        for c in t:
            if s[i] == c:
                i += 1
                # 若已经遍历完 s ，则提前返回 true
                if i == len(s):
                    return True
        return False
1
2
3
4
5
6
7
8
9
10
11

209. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
1
2
3

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
1
2

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
1
2

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

代码

• 滑动窗口法
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums is None or len(nums)==0:
            return 0
        lenf = len(nums) + 1
        i = j = 0
        total = 0
        while (j<len(nums)):
            total += nums[j]
            j += 1
            while (total >= target):
                lenf = min(lenf, j-i)
                total -= nums[i]
                i += 1
        if lenf == len(nums) + 1:
            return 0
        return lenf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目

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

示例 1：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

示例 2：

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

示例 3：

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

提示：

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

代码

• 滑动窗口法+哈希表
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i)
            dic[s[j]] = j
            res = max(res, j-i)
        return res
1
2
3
4
5
6
7
8
9

383. 赎金信

题目

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false
1
2

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false
1
2

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true
1
2

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

代码

• 一行代码
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return all(ransomNote.count(i)<=magazine.count(i) for i in set(ransomNote))
1
2
3

• 一次for
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        r = list(ransomNote)
        for sss in magazine:
            if sss in r:
                r.remove(sss)
        return len(r)==0
1
2
3
4
5
6
7

205. 同构字符串

题目

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1：

输入：s = "egg", t = "add"
输出：true
1
2

示例 2：

输入：s = "foo", t = "bar"
输出：false
1
2

示例 3：

输入：s = "paper", t = "title"
输出：true
1
2

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

代码

• 双哈希表
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s2t = {}    # 存储s字符串中字符到t字符串字符的映射 
        t2s = {}    # 存储t字符串中字符到s字符串字符的映射
        for sc, tc in zip(s, t):
            if (sc in s2t and s2t[sc] != tc) or (tc in t2s and t2s[tc] != sc):
                # 如果当前s字符和t字符不匹配，直接返回
                return False
            # 更新s字符和t字符的映射关系，如果已经存储的映射不改变结果
            s2t[sc] = tc
            t2s[tc] = sc
        return True
1
2
3
4
5
6
7
8
9
10
11
12

242. 有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1：

输入: s = "anagram", t = "nagaram"
输出: true
1
2

示例 2：

输入: s = "rat", t = "car"
输出: false
1
2

提示：

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

代码

• 计数比较
  时间复杂度 O(M+N)
  空间复杂度 O(1)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool: 
        if len(s) != len(t):
            return False
        hs, ht = {}, {}
        for i in range(len(s)):
            if s[i] in hs:
                hs[s[i]] += 1
            else:
                hs[s[i]] = 1
            if t[i] in ht:
                ht[t[i]] += 1
            else:
                ht[t[i]] = 1
        for i in hs:
            if i not in ht:
                return False
            if hs[i] != ht[i]:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• collections.Counter直接计数比较
  时间复杂度 O(M+N)
  空间复杂度 O(1)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool: 
        return Counter(s) == Counter(t)
1
2
3

49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1：

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

示例 2：

输入: strs = [""]
输出: [[""]]
1
2

示例 3：

输入: strs = ["a"]
输出: [["a"]]
1
2

提示：

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

代码

• 哈希表 + sorted方法
  时间复杂度 O(N)
  空间复杂度 O(1)

class Solution:
    def groupAnagrams(self, strs):
        table = {}
        for s in strs:
            s_ = "".join(sorted(s))
            if s_ not in table:
                table[s_] = [s]
            else:
                table[s_].append(s)
        return list(table.values())
1
2
3
4
5
6
7
8
9
10

1. 两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。
示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

代码

• 哈希表
  时间复杂度 O(N)
  空间复杂度 O(N)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for j,x in enumerate(nums):
            if target - x in idx:
                return [idx[target - x], j]
            idx[x] = j
1
2
3
4
5
6
7

202. 快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

• 如果这个过程 结果为 1，那么这个数就是快乐数。
  如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
  示例 1：

  输入：n = 19
  输出：true
  解释：
  $1^2$ + $9^2$ = 82
  $8^2$ + $2^2$ = 68
  $6^2$ + $8^2$ = 100
  $1^2$ + $0^2$ + $0^2$ = 1
  示例 2：

  输入：n = 2
  输出：false
  提示：

• $1<=n<=2^{31}-1$

代码

• 暴力解法

  快乐数能收敛至 1：
  如： n = 236 ， 236 → 49 → 97 → 130 → 10 → 1
  非快乐数是会出现循环的：
  如： n = 2， 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，4 出现循环。

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = {1}
        while n not in seen:
            seen.add(n)
            n = sum(int(i) ** 2 for i in str(n))
        return n == 1
1
2
3
4
5
6
7

219. 存在重复元素 II

题目

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：

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

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true
1
2

示例 3：

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

提示：

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

代码

• 哈希表
  时间复杂度$O(n)$
  空间复杂度$O(n)$

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        idx = {}
        for j, x in enumerate(nums):
            if x in idx and abs(idx[x]-j)<=k:
                return True
            idx[x] = j
        return False
1
2
3
4
5
6
7
8

128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
1
2
3

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
1
2

提示：

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

代码

• 集合去除+找最小算连续遍历
  时间复杂度$O(n)$
  空间复杂度$O(n)$

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxLen = 0
        nums = set(nums) # 去除重复元素
        for n in nums:
            if (n-1) not in nums:
                l = 1 
                while n+1 in nums:
                    l += 1
                    n += 1
                maxLen = max(maxLen, l)
        return maxLen
1
2
3
4
5
6
7
8
9
10
11
12

56. 合并区间

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 $intervals[i]=[star{t}_i,en{d}_i]$。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
1
2
3

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
1
2
3

提示：

• $1<=intervals.length<=10^4$
• $intervals[i].length==2$
• $0<=star{t}_i<=en{d}_i<=10^4$

代码

• 排序 + 遍历
  时间复杂度 $O(n\times \log n)$
  空间复杂度 $O(\log n)$。其中 $n$ 为区间个数。

先将第一个区间加入答案，然后依次考虑之后的每个区间：

• 如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点，说明两个区间不会重合，因此我们可以直接将当前区间加入答案数组末尾；
• 否则，说明两个区间重合，我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点，将其置为二者的较大值。
  最后，我们返回答案数组即可。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = [intervals[0]]
        for l, r in intervals[1:]:
            if ans[-1][1] < l:
                ans.append([l, r])
            else:
                ans[-1][1] = max(ans[-1][1], r)
        return ans
1
2
3
4
5
6
7
8
9
10

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 。
1
2
3

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
1
2

提示：

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

代码

• 动态规划
  时间复杂度 $O(n^2)$
  空间复杂度 $O(n)$。

class Solution:
    def lengthOfLIS(self, nums: [int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
1
2
3
4
5
6
7
8
9

435. 无重叠区间

题目

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1：

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
1
2
3

示例 2：

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
1
2
3

示例 3：

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
1
2
3

提示：

• $1<=intervals.length<=10^5$
• $intervals[i].length==2$
• $-5\ast 10^4<=star{t}_i<en{d}_i<=5\ast 10^4$

代码

• 动态规划
  时间复杂度 $O(n^2)$
  空间复杂度 $O(n)$。
  注：超时

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        dp = [1] * n
        intervals.sort(key=lambda a: a[1])
        for i in range(n):
            for j in range(i-1,-1,-1):
                if intervals[i][0] >= intervals[j][1]:
                    dp[i] = max(dp[i], dp[j]+1)
                    break
            dp[i] = max(dp[i], dp[i-1])
        return n - max(dp)
1
2
3
4
5
6
7
8
9
10
11
12

• 贪心
  时间复杂度 $O(n\times \log n)$
  空间复杂度 $O(\log n)$

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        end, cnt = float('-inf'), 0
        for s, e in sorted(intervals, key=lambda x: x[1]):
            if s >= end:
                end = e
            else: 
                cnt += 1
        return cnt
1
2
3
4
5
6
7
8
9

646. 最长数对链

题目

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。
1
2
3

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
1
2
3

提示：

• $n==pairs.length$
• $1<=n<=1000$
• $-1000<=lef{t}_i<righ{t}_i<=1000$

代码

• 动态规划
  时间复杂度 $O(n^2)$
  空间复杂度 $O(n)$。

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        dp = [1] * n
        pairs.sort(key=lambda x:x[1])
        for i in range(n):
            for j in range(i-1,-1,-1):
                if pairs[i][0] > pairs[j][1]:
                    dp[i] = max(dp[i], dp[j]+1)
                    break
            dp[i] = max(dp[i], dp[i-1])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12

• 贪心
  时间复杂度 $O(n\times \log n)$
  空间复杂度 $O(\log n)$

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        end, cnt = float('-inf'), 0
        for s, e in sorted(pairs, key=lambda x: x[1]):
            if s > end:
                cnt += 1
                end = e
        return cnt
1
2
3
4
5
6
7
8

452. 用最少数量的箭引爆气球

题目

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
1
2
3
4
5

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
1
2
3

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
1
2
3
4
5

提示：

• $1<=points.length<=10^5$
• $points[i].length==2$
• $-2^{31}<=x_{start}<x_{end}<=2^{31}-1$

代码

• 动态规划
  时间复杂度 $O(n^2)$
  空间复杂度 $O(n)$。
  注：超时

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        n = len(points)
        dp = [1] * n
        points.sort(key=lambda x:x[1])
        for i in range(n):
            for j in range(i-1,-1,-1):
                if points[i][0] > points[j][1]:
                    dp[i] = max(dp[i], dp[j]+1)
                    break
            dp[i] = max(dp[i], dp[i-1])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12

• 贪心
  时间复杂度 $O(n\times \log n)$
  空间复杂度 $O(\log n)$

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        end, cnt = float('-inf'), 0
        for s, e in sorted(points, key=lambda x: x[1]):
            if s > end:
                cnt += 1
                end = e
        return cnt
1
2
3
4
5
6
7
8

172. 阶乘后的零

题目

给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1
示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
1
2
3

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
1
2
3

示例 3：

输入：n = 0
输出：0
1
2

提示：

• $0<=n<=10^4$

代码

• 贪心
  时间复杂度 $O(\log n)$
  空间复杂度 $O(1)$。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        cnt = 0
        while(n):
            n //= 5
            cnt += n
        return cnt
1
2
3
4
5
6
7

50. Pow(x, n)

题目

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

• -100.0 < x < 100.0
• $-2^{31}<=n<=2^{31}-1$
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• $-10^4<=x^n<=10^4$

代码

• 一次遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(1)$。
  注：超时

class Solution:
    def myPow(self, x: float, n: int) -> float:
        res = 1
        while n:
            res *= x
            n -= 1
        return res
1
2
3
4
5
6
7

• 快速幂 迭代
  时间复杂度 $O(\log n)$
  空间复杂度 $O(1)$。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0: return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1
        return res
1
2
3
4
5
6
7
8
9
10

• 递归
  如果 n 是负数，那么相当于求 (1/x)^(-n)。
  如果 n 是正数 且 奇数，那么结果需要单独乘以 x
  如果 n 是正数 且 偶数，求(x²⁾(n/2)，一直递归下去即可。
  时间复杂度 $O(1)$
  空间复杂度 $O(1)$。

class Solution:
    def myPow(self, x, n):
        if n == 0:
            return 1
        if n < 0:
            x = 1 / x
            n = -n
        if n % 2:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n / 2)
1
2
3
4
5
6
7
8
9
10

70. 爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

代码

• 动态规划
  可转化为 求斐波那契数列的第 n 项
  时间复杂度 $O(n)$
  空间复杂度 $O(1)$。

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n-1):
            a, b = b, a+b
        return b
1
2
3
4
5
6

• 列表+动态规划
  可转化为 求斐波那契数列的第 n 项
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

class Solution:
    def climbStairs(self, n: int) -> int:
        s=[1,2]
        if n<=2:
            return s[n-1]
        while len(s)<n:
            s.append(s[-1]+s[-2])
        return s[-1]
1
2
3
4
5
6
7
8

198. 打家劫舍

题目

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

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

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
1
2
3
4

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
1
2
3
4

提示：

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

代码

• 动态规划
  时间复杂度 $O(n)$
  空间复杂度 $O(1)$。

class Solution:
    def rob(self, nums: List[int]) -> int:
        cur, pre = 0, 0
        for x in nums:
            cur, pre = max(cur, pre + x), cur
        return cur
1
2
3
4
5
6

139. 单词拆分

题目

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

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1
2
3

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
1
2
3
4

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2

提示：

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

代码

• 动态规划
  时间复杂度 $O(n^2)$
  空间复杂度 $O(1)$。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(n):
            for j in range(i+1,n+1):
                if dp[i] == True and s[i:j] in wordDict:
                    dp[j] = True
        return dp[-1]
1
2
3
4
5
6
7
8
9
10

322. 零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

示例 2：

输入：coins = [2], amount = 3
输出：-1
1
2

示例 3：

输入：coins = [1], amount = 0
输出：0
1
2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

代码

• 动态规划
  时间复杂度 $O(n\ast amount)$
  空间复杂度 $O(amount)$。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[inf]*(amount+1)
        dp[0]=0 
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i]=min(dp[i],dp[i-coin]+1)
        return -1 if dp[-1]== inf else dp[-1]
1
2
3
4
5
6
7
8

518. 零钱兑换 II

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
1
2
3
4
5
6
7

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
1
2
3

示例 3：

输入：amount = 10, coins = [10] 
输出：1
1
2

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

代码

• 动态规划
  时间复杂度 $O(n\ast amount)$
  空间复杂度 $O(amount)$。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp=[0]*(amount+1)
        dp[0]=1
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i]+=dp[i-coin]
        return dp[-1]
1
2
3
4
5
6
7
8

20. 有效的括号

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

输入：s = "()[]{}"
输出：true
1
2

示例 3：

输入：s = "(]"
输出：false
1
2

提示：

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

代码

• 辅助栈法
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'(':')','[':']','{':'}','?':'?'}
        stack = ['?']
        for sss in s:
            if sss in dic: stack.append(sss)
            elif dic[stack.pop()]!=sss: return False
        return len(stack)==1
1
2
3
4
5
6
7
8

71. 简化路径

题目

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。
示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 
1
2
3

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
1
2
3

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
1
2
3

示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"
1
2

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，‘.’，‘/’ 或 ‘_’ 组成。
• path 是一个有效的 Unix 风格绝对路径。

代码

• 栈解决,把当前目录压入栈中,遇到…弹出栈顶,最后返回栈中元素.
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        path = path.split('/')
        for c in path:
            if c == '..': 
                if stack:
                    stack.pop()
            elif c and c != '.':
                stack.append(c)
        return '/' + '/'.join(stack)
1
2
3
4
5
6
7
8
9
10
11

155. 最小栈

题目

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

实现 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提示：

• $-2^{31}<=val<=2^{31}-1$
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 $3\ast 10^4$ 次

代码

• 栈
  时间复杂度 $O(1)$
  空间复杂度 $O(n)$。

class MinStack:

    def __init__(self):
        self.stack = []
        self.minstack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minstack or val <= self.minstack[-1]:
            self.minstack.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.minstack[-1]:
            self.minstack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

150. 逆波兰表达式求值

题目

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
1
2
3

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
1
2
3
4

示例 3：

输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
1
2
3
4
5
6
7
8
9

提示：

• $1<=tokens.length<=10^4$
• tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数
  逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

代码

• 栈
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            try:
                stack.append(int(token))
            except:
                nums2 = stack.pop()
                nums1 = stack.pop()
                stack.append(self.operate(nums1,nums2,token))
        return stack[0]
    def operate(self,nums1,nums2,token):
        if token == '+':
            return nums1 + nums2
        elif token == '-':
            return nums1 - nums2
        elif token == '*':
            return nums1 * nums2
        elif token == '/':
            return int(nums1 / nums2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

104. 二叉树的最大深度

题目

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

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

输入：root = [3,9,20,null,null,15,7]
输出：3
1
2

示例 2：

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

提示：

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

代码

• 递归
  深度优先搜索（DFS）之后序遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
1
2
3
4
5
6
7
8
9
10

• 层序遍历
  广度优先搜索（BFS）
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

100. 相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false
1
2

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false
1
2

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• $-10^4<=Node.val<=10^4$

代码

• 递归
  深度优先搜索（DFS）之后序遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None: return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

226. 翻转二叉树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false
1
2

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false
1
2

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• $-10^4<=Node.val<=10^4$

代码

• 递归
  深度优先搜索（DFS）之后序遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None: return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

101. 对称二叉树

题目

给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：

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

示例 2：

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

提示：

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

代码

• 递归 在相同二叉树基础上改动
  深度优先搜索（DFS）之后序遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None: return p is q
        return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left, root.right)
1
2
3
4
5
6
7
8
9
10
11
12

226. 翻转二叉树

题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：[]
1
2

提示：

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

代码

• 递归
  深度优先搜索（DFS）之后序遍历
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root
1
2
3
4
5
6
7
8
9
10
11

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

题目

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

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

示例 2：

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

提示：

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

代码

• 递归
  时间复杂度 $O(n^2)$
  空间复杂度 $O(n^2)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:return None
        left_size = inorder.index(preorder[0])
        left = self.buildTree(preorder[1:1+left_size], inorder[:left_size])
        right = self.buildTree(preorder[1+left_size:], inorder[1+left_size:])
        return TreeNode(preorder[0], left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13

• 递归+哈希表
  时间复杂度 $O(n)$
  空间复杂度 $O(n)$。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        index = {x: i for i, x in enumerate(inorder)}

        def dfs(pre_l: int, pre_r: int, in_l: int, in_r: int) -> Optional[TreeNode]:
            if pre_l == pre_r:  # 空节点
                return None
            left_size = index[preorder[pre_l]] - in_l  # 左子树的大小
            left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l, in_l + left_size)
            right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size, in_r)
            return TreeNode(preorder[pre_l], left, right)

        return dfs(0, len(preorder), 0, len(inorder))  # 左闭右开区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

106. 从中序与后序遍历序列构造二叉树

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

112. 路径总和

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。
示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
1
2
3

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
1
2
3
4
5
6

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
1
2
3

提示：

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

代码

• 递归 DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root: return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
1
2
3
4
5
6
7
8
9
10
11
12

141. 环形链表

题目

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

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

代码

• 快慢指针
  龟兔赛跑 要是有环 快慢指针迟早相遇

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        s = f = head
        while f and f.next:
            s = s.next
            f = f.next.next
            if s == f:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

21. 合并两个有序链表

题目

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

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

示例 2：

输入：l1 = [], l2 = []
输出：[]
1
2

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
1
2

提示：

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

代码

• 递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None: return list2
        if list2 is None: return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        list2.next = self.mergeTwoLists(list2.next,list1)
        return list2
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 哨兵

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = init = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return init.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

88. 合并两个有序数组

题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
1
2
3
4

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
1
2
3
4

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
1
2
3
4
5

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• $-10^9<=nums1[i],nums2[j]<=10^9$
  进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

代码

• 切片原地修改
  时间复杂度$O(m+n)$
  空间复杂度$O(1)$

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0: nums1[:] = nums2 # 切片操作不会改变地址
        if m and n:
            nums1[:] = nums1[:m]
            nums1.extend(nums2)
            nums1.sort()
1
2
3
4
5
6
7
8
9
10

• 切片原地修改
  时间复杂度$O(m+n)$
  空间复杂度$O(1)$

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0: nums1[:] = nums2 # 切片操作不会改变地址
        if m and n:
            nums1[:] = nums1[:m]
            nums1.extend(nums2)
            nums1.sort()
1
2
3
4
5
6
7
8
9
10

• 倒序双指针
  时间复杂度$O(m+n)$
  空间复杂度$O(1)$

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p2 >= 0:
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15