IT小白

这个屌丝很懒，什么也没留下！

热门标签

Python版—力扣hot100

作者：IT小白 | 2024-03-02 21:01:12

踩

Python版—力扣hot100

1 前言

有基础的话，可以直接去w3school看教程复习一下基本语法。
之前用C++做过力扣，这次用py再做一遍，当作复习。之前的博客：http://t.csdnimg.cn/oWX7v
持续更新中，一天做几道，欢迎follow

文章目录

2 Hot 100

2.1 两数之和

https://leetcode.cn/problems/two-sum
暴力

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(0, len(nums)-1):
            for j in range(i+1, len(nums)):
                if (target == nums[i] + nums[j]):
                    return [i, j]
        return []
        
1
2
3
4
5
6
7
8

哈希表降低搜索复杂度

class Solution(object):
    def twoSum(self, nums, target):
        hashtable = dict()
        for i, num in enumerate(nums):
            if (target - num in hashtable.keys()):
                return [hashtable[target-num], i]
            hashtable[num] = i
        return []
        
1
2
3
4
5
6
7
8
9

2.2 字母异位词分组

https://leetcode.cn/problems/group-anagrams
排序，当作key

class Solution(object):
    def groupAnagrams(self, strs):
        my_dict = dict()
        for s in strs:
            s1 = sorted(s)
            s1 = str(s1)
            if s1 in my_dict:
                my_dict[s1].append(s)
            else:
                my_dict[s1] = [s]
        res = []
        res = my_dict.values()
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14

用字母出现的次数当作key

class Solution(object):
    def groupAnagrams(self, strs):
        my_dict = dict()
        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord('a')] += 1
            if tuple(counts) in my_dict.keys():
                my_dict[tuple(counts)].append(st)
            else:
                my_dict[tuple(counts)] = [st]
        return my_dict.values()
        
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/

class Solution(object):
    def longestConsecutive(self, nums):
        myset = set(nums)
        res = 0
        for s in myset:
            if (s-1 not in myset):
                n, tmp = 1, s+1
                while (tmp in myset):
                    n += 1
                    tmp += 1
                res = max(n, res)
            else:
                continue
        return res
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.4 移动零

双指针，交换元素

class Solution(object):
    def moveZeroes(self, nums):
        i = j = 0
        n = len(nums)
        while j < n:
            if (nums[j] != 0):
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
            j += 1
        return nums
        
1
2
3
4
5
6
7
8
9
10
11

2.5 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water
双指针，移动板，更新水

class Solution(object):
    def maxArea(self, height):
        l, r, res = 0, len(height)-1, 0
        while l < r:
            res = max(res, (r-l)*min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res
        
1
2
3
4
5
6
7
8
9
10
11

2.6 三数之和

https://leetcode.cn/problems/3sum
排序，遍历，双指针，记得答案去重。

class Solution(object):
    def threeSum(self, nums):
        n, res = len(nums), []
        if (n < 3):
            return
        nums.sort()
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, n-1
            while l < r:
                sum = nums[i] + nums[l] + nums[r]
                if (sum < 0):
                    l += 1
                elif (sum > 0):
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
        return res
        
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

2.7 接雨水

按列计算，第i列的雨水 = min(左边最高墙的高度，右边最高墙的高度) - 第i列的墙高，O(N2)复杂度，超时了。

class Solution(object):
    def trap(self, height):
        n, res = len(height), 0
        for i in range(n):
            if (i == 0 or i == n-1):
                continue
            l, r = 0, 0
            for j in range(0, i):
                l = max(l, height[j])
            for k in range(i+1, n):
                r = max(r, height[k])
            if min(l, r) - height[i] > 0:
                res += min(r, l) - height[i]
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

dp优化上述过程，O(N)复杂度

class Solution(object):
    def trap(self, height):
        n, res = len(height), 0
        left, right = [0]*n, [0]*n
        left[0], right[n-1] = height[0], height[n-1]
        for i in range(1, n):
            left[i] = max(left[i-1], height[i])
        for j in range(n-2, 0, -1):
            right[j] = max(right[j+1], height[j])
        for k in range(n):
            if (k == 0 or k == n-1):
                continue
            tmp = min(left[k], right[k]) - height[k]
            if tmp > 0:
                res += tmp
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.8 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters
滑动窗口思想的模拟

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        res, tmp = 0, ''
        for ch in s:
            while tmp.find(ch) > -1:
                tmp = tmp[1:]
            tmp += ch
            res = max(res, len(tmp))
        return res

1
2
3
4
5
6
7
8
9
10

滑动窗口，哈希集检测重复字符

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        res = 0
        hashset = set()
        n = len(s)
        j = -1
        for i in range(n):
            if i != 0:
                hashset.remove(s[i-1])
            while j+1 < n and s[j+1] not in hashset:
                hashset.add(s[j+1])
                j += 1
            res = max(res, j-i+1)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

https://leetcode.cn/problems/find-all-anagrams-in-a-string
滑动窗口模拟，可惜超时了

class Solution(object):
    def findAnagrams(self, s, p):
        res = []
        n, n1 = len(s), len(p)
        for i in range(n):
            cnt = 0
            tmp_p = p
            if s[i] in tmp_p:
                cnt += 1
                tmp_p = tmp_p.replace(s[i], '', 1)
                right = i
                while right+1 < n and s[right+1] in tmp_p:
                    cnt += 1
                    tmp_p = tmp_p.replace(s[right + 1], '', 1)
                    right += 1
            if cnt == n1:
                res.append(i)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

滑动窗口，窗口的长度 = p的长度

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        ns, np = len(s), len(p)
        if ns < np:
            return res
        s_cnt = [0]*26
        p_cnt = [0]*26
        for i in range(np):
            s_cnt[ord(s[i]) - ord('a')] += 1
            p_cnt[ord(p[i]) - ord('a')] += 1
        if s_cnt == p_cnt:
            res.append(0)
        for i in range(1, ns-np+1):
            s_cnt[ord(s[i-1])-ord('a')] -= 1
            s_cnt[ord(s[i+np-1]) - ord('a')] += 1
            if s_cnt == p_cnt:
                res.append(i)
        return res

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

2.10 和为 K 的子数组

https://leetcode.cn/problems/subarray-sum-equals-k
神中神的题解，前缀和+字典。
使用暴力会超时

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dic = {0: 1}
        sums, res = 0, 0
        for num in nums:
            sums += num
            res += dic.get(sums-k, 0)
            dic[sums] = dic.get(sums, 0)+1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用前缀和的方法可以解决这个问题，因为我们需要找到和为k的连续子数组的个数。通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。

假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。

通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。

这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。

2.11 滑动窗口最大值

【单调队列滑动窗口最大值【基础算法精讲 27】】 https://www.bilibili.com/video/BV1bM411X72E/?share_source=copy_web&vd_source=aa3fec063f2bca95bca01c76f6509322

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        q = deque()
        for i, x in enumerate(nums):
            # 入
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            # 出
            if i - q[0] >= k:
                q.popleft()
            # 记录答案
            if i >= k-1:
                res.append(nums[q[0]])
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.12 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring
滑动窗口，字典记录是否覆盖了t；对于每一个右边界，寻找size最小的左边界，记录答案。

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        dic = dict()
        need_cnt = len(t)
        # 把t存入字典中，后面的窗口要用到
        for ch in t:
            dic[ch] = dic.get(ch, 0) + 1
        left, start = 0, 0
        size = 100010
        for right, ch in enumerate(s):
            if dic.get(ch, 0) > 0:
                need_cnt -= 1
            dic[ch] = dic.get(ch, 0) - 1
            if need_cnt == 0:
                # 移动左边界，剔除多余的字符
                while dic[s[left]] < 0:
                    c = s[left]
                    dic[c] += 1
                    left += 1
                # 如果size更短了，更新答案
                if right-left+1 < size:
                    size = right - left + 1
                    start = left
                # 破坏左边界，开始下一轮
                dic[s[left]] += 1
                left += 1
                need_cnt += 1
        if size != 100010:
            return s[start:start + size]
        return ''

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
29
30
31
32
33
34
35
36

2.13 最大子数组和

https://leetcode.cn/problems/maximum-subarray
dp：
状态转移：以第i位结尾的最大数组和 = max(nums[i]，以第i-1位结尾的最大数组和+nums[i])

class Solution(object):
    def maxSubArray(self, nums):
        for i, num in enumerate(nums):
            if i==0:
                res = nums[0]
                pre = nums[0]
            else:
                pre = max(pre + num, num)
                res = max(res, pre)
        return res

1
2
3
4
5
6
7
8
9
10
11

更骚的：
如果你是负的，那就用0来代替你，然后从新开始

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)

1
2
3
4
5
6

方法二：分治的思想
在这里插入图片描述

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        def sub(nums, l, r):
            if l == r:
                return nums[l]
            mid = (l+r) >> 1
            return max(sub(nums, l, mid), sub(nums, mid+1, r), cross(nums, l, mid, r))

        def cross(nums, l, mid, r):
            left_sum_max = 0
            start_left = mid-1
            s1 = 0
            while start_left >= l:
                s1 += nums[start_left]
                left_sum_max = max(left_sum_max, s1)
                start_left -= 1

            right_sum_max = 0
            start_right = mid+1
            s2 = 0
            while start_right <= r:
                s2 += nums[start_right]
                right_sum_max = max(right_sum_max, s2)
                start_right += 1
            return left_sum_max + nums[mid] + right_sum_max

        n = len(nums)
        if n == 0:
            return 0
        return sub(nums, 0, n-1)

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
29
30
31
32
33
34
35
36

2.14 合并区间

https://leetcode.cn/problems/merge-intervals
先对最左端点排序，然后merge

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        intervals.sort()
        n = len(intervals)
        i = 0
        while i < n:
            l, r = intervals[i][0], intervals[i][1]
            while i+1 < n and r >= intervals[i+1][0]:
                r = max(r, intervals[i+1][1])
                i += 1
            res.append([l, r])
            i += 1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.15 轮转数组

https://leetcode.cn/problems/rotate-array
方法一：时间空间复杂度都是O(N)

class Solution(object):
    def rotate(self, nums, k):
        new_nums = list(nums)
        n = len(nums)
        for i in range(n):
            nums[(i+k) % n] = new_nums[i]

1
2
3
4
5
6
7

方法二：旋转

nums = "----->-->"; k =3
result = "-->----->";

reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
this visualization help me figure it out :)
1
2
3
4
5
6
7

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def reverse(i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        n = len(nums)
        reverse(0, n-1)
        reverse(0, k % n-1)
        reverse(k % n, n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.16 除自身以外数组的乘积

https://leetcode.cn/problems/product-of-array-except-self
太难了，O(N)的复杂度并且还不能使用除法

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        res = [1]*n
        l, r = 1, 1  # 从左右开始累乘
        for i in range(n):
            # 左边的乘积
            res[i] *= l
            l *= nums[i]
            # 右边的乘积
            res[n-1-i] *= r
            r *= nums[n-1-i]
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.17 缺失的第一个正数

哈希表记录，时间空间复杂度都是O(N)

class Solution(object):
    def firstMissingPositive(self, nums):
        s = set()
        n = len(nums)
        for num in nums:
            s.add(num)
        for i in range(1, n+1):
            if i not in s:
                return i
        return n+1

1
2
3
4
5
6
7
8
9
10
11

时间N，空间1

from typing import List


class Solution:

    # 3 应该放在索引为 2 的地方
    # 4 应该放在索引为 3 的地方

    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            # 先判断这个数字是不是索引，然后判断这个数字是不是放在了正确的地方
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                self.__swap(nums, i, nums[i] - 1)

        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1

        return size + 1

    def __swap(self, nums, index1, index2):
        nums[index1], nums[index2] = nums[index2], nums[index1]

作者：liweiwei1419
链接：https://leetcode.cn/problems/first-missing-positive/solutions/7703/tong-pai-xu-python-dai-ma-by-liweiwei1419/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

2.18 矩阵置零

https://leetcode.cn/problems/set-matrix-zeroes
两个bool数组记录行列是否为0，然后再遍历一次，为matrix置零。
时间复杂度：O(mn)
空间复杂度：O(m+n)

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        helper_m, helper_n = [False]*m, [False]*n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    helper_m[i] = helper_n[j] = True
        for i in range(m):
            for j in range(n):
                if helper_m[i] or helper_n[j]:
                    matrix[i][j] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

优化空间复杂度，挺没意思的。。。
时间复杂度：O(mn)
空间复杂度：O(1)

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        # 记录第一行和第一列是否有0
        flag_col0, flag_row0 = False, False
        for i in range(m):
            if matrix[i][0] == 0:
                flag_col0 = True
        for j in range(n):
            if matrix[0][j] == 0:
                flag_row0 = True
        # 将各个元素的0信息记录到第一行和第一类中，例如matrix[5][3]==0，那么matrix[5][0] = matrix[0][3] = 0
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        # 根据第一行和第一列中记录的信息为matrix置零
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        # 处理matrix的第一行和第一列
        if flag_col0:
            for i in range(m):
                matrix[i][0] = 0
        if flag_row0:
            for j in range(n):
                matrix[0][j] = 0

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
29
30
31
32
33
34

2.19 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix
顺时针螺旋打印矩阵
可以通过总元素个数跳出循环，也可以通过l r t b判断来跳出循环

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
        nums = (r+1)*(b+1)
        res = []
        if not matrix or not matrix[0]:
            return res
        # while nums > 0:
        while l <= r and t <= b:
            # 最上行
            for j in range(l, r+1):
                res.append(matrix[t][j])
                nums -= 1

            # 最右列
            for i in range(t+1, b+1):
                res.append(matrix[i][r])
                nums -= 1
            if l < r and t < b:
                # 最下行
                for j in range(r-1, l, -1):
                    res.append(matrix[b][j])
                    nums -= 1

                # 最左列
                for i in range(b, t, -1):
                    res.append(matrix[i][l])
                    nums -= 1

            # 更新left right top bottom
            l, r, t, b = l + 1, r - 1, t + 1, b - 1
        return res

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
29
30
31
32
33
34
35
36
37

2.20 旋转图像

https://leetcode.cn/problems/rotate-image
把一个矩阵顺时针旋转90度 = 先转置，再水平镜像

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 先转置
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 在水平镜像
        for i in range(n):
            for j in range(n/2):
                matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.21 搜索二维矩阵 II

方法一：从右上角开始搜索，如果该元素比target大，那么往左边搜索；如果小于target，那么往下搜索。
时间复杂度：O(n+m)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n-1
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:
                i += 1
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：逐行/逐列二分

class Solution(object):
    def searchMatrix(self, matrix, target):
        def search(i, l, r):
            mid = (l+r)/2
            while l <= r:
                if target == matrix[i][mid]:
                    return mid
                elif target < matrix[i][mid]:
                    return search(i, l, mid-1)
                else:
                    return search(i, mid+1, r)

        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            if search(i, 0, n-1) >= 0:
                return True
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.22 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/
方法一：哈希表或哈希集
时间：O(M+N)
空间：O(M)

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        dic = dict()
        while headA:
            dic[headA] = dic.get(headA, 0) + 1
            headA = headA.next
        while headB:
            dic[headB] = dic.get(headB, 0) + 1
            if dic[headB] == 2:
                return headB
            headB = headB.next
        return None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：双指针
时间：O(M+N)
空间：O(1)
初始化p,q分别指向头节点。
如果两链表相交，设A的长度为a+c，B的长度为b+c，那么p和q走过a+b+c长度之后，会指向同一节点。
如果两链表不相交，p和q走过a+b之后，都指向None，也会跳出while循环。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA == None or headB == None:
            return None
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.23 反转链表

https://leetcode.cn/problems/reverse-linked-list
迭代
开始的时候：pre, cur = None, head
结束的时候：pre = 反转后的链表的head，cur = None

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归

第一轮出栈，head为5，head.next为空，返回5
第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
          把当前节点的子节点的子节点指向当前节点
          此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
          此时链表为1->2->3->4<-5
          返回节点5
第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
          此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
          此时链表为1->2->3<-4<-5
          返回节点5
第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
          此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
          此时链表为1->2<-3<-4<-5
          返回节点5
第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
          此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
          此时链表为1<-2<-3<-4<-5
          返回节点5
出栈完成，最终头节点5->4->3->2->1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead

1
2
3
4
5
6
7
8
9
10
11
12
13

2.24 回文链表

https://leetcode.cn/problems/palindrome-linked-list
方法一：复制到数组中，再比较
时间和空间都是O(N)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        return nums == nums[::-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：先找到链表的中点，再翻转后半部分链表，再比较
时间：O(N)
空间：O(1)

class Solution(object):
    def isPalindrome(self, head):
        if head is None:
            return True
        # 先找到链表的中点
        first_half_end = self.find_first_half(head)
        # 反转后半部分链表
        second_half_start = self.reverse_list(first_half_end.next)
        while head and second_half_start:
            if head.val != second_half_start.val:
                return False
            head = head.next
            second_half_start = second_half_start.next
        return True

    def find_first_half(self, head):
        p = head
        q = head
        while q.next and q.next.next:
            p, q = p.next, q.next.next
        return p

    def reverse_list(self, head):
        pre, cur = None, head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

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
29
30
31

2.25 环形链表

https://leetcode.cn/problems/linked-list-cycle
快慢指针，时间O(N)，空间O(1)

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        p = head
        q = head
        while q.next and q.next.next:
            p, q = p.next, q.next.next
            if p == q:
                return True
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

哈希集肯定也是可以的，空间复杂度更高一些。

2.26 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii
这是个数学题啊，还是快慢指针，接上题。
快慢指针在环中相遇后，相遇点不一定是环的入口。
此时让第三个指针从head出发，一次走一步，slow继续走，他们会在环的入口相遇。纯数学题。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                while head != slow:
                    head, slow = head.next, slow.next
                return slow
        return None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.27 合并两个有序链表

方法一：双指针迭代
最开始申请一个dummy节点，整个过程中，dum是已完成的尾节点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dum = ListNode()
        res = dum
        p, q = list1, list2
        while p and q:
            if p.val <= q.val:
                dum.next = p
                p = p.next
            else:
                dum.next = q
                q = q.next
            dum = dum.next
        dum.next = p if p else q
        return res.next

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

方法二：递归

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

1
2
3
4
5
6
7
8
9
10
11
12
13

这个图很好：l1 = 1, l2 = 3，那么l1.next =merge(l1的2，l2的3),，并且要 return l1
在这里插入图片描述

2.28 两数相加

https://leetcode.cn/problems/add-two-numbers
方法一：模拟迭代

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        res = dum = ListNode(-1)
        while l1 or l2:
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0
            num, carry = (num1+num2+carry, 0) if num1+num2 + \
                carry <= 9 else (num1+num2+carry-10, 1)
            dum.next = ListNode(num)
            dum = dum.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry:
            dum.next = ListNode(carry)
        return res.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：递归

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        return self.helper(l1, l2, 0)

    def helper(self, l1, l2, carry):
        if l1 is None and l2 is None and carry == 0:
            return None
        sum1, sum2 = 0, 0
        if l1:
            sum1 = l1.val
            l1 = l1.next
        if l2:
            sum2 = l2.val
            l2 = l2.next
        sum = sum1 + sum2 + carry
        node = ListNode(sum % 10)
        node.next = self.helper(l1, l2, sum / 10)
        return node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

更简洁的写法
https://leetcode.cn/problems/add-two-numbers/solutions/2327008/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        return self.helper(l1, l2, 0)

    def helper(self, l1, l2, carry):
        if l1 is None and l2 is None:
            return ListNode(carry) if carry else None
        if l1 is None:  # 这个if是为了保证：l1总是l1和l2中，后为空的那个
            l1, l2 = l2, l1
        carry += l1.val + (l2.val if l2 else 0)
        l1.val = carry % 10
        l1.next = self.helper(l1.next, l2.next if l2 else None, carry/10)
        return l1

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list
快慢指针

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        fast = head
        for i in range(n):
            fast = fast.next
        slow = ListNode(0, head)
        res = slow
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return res.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.30 两两交换链表中的节点

方法一：迭代

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        res = node0 = ListNode(0, head)
        while node0.next and node0.next.next:  # 有两个节点就可以交换
            node1, node2 = node0.next, node0.next.next
            node0.next = node2  # 0->2
            node1.next = node2.next  # 1->3
            node2.next = node1  # 2->1
            node0 = node1
        return res.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：递归
请看注释。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 终止条件
        if head is None or head.next is None:
            return head
        # 赋值
        node1 = head
        node2 = head.next
        node3 = node2.next
        # node2 -> node1 -> 递归返回的链表头
        node2.next = node1
        node1.next = self.swapPairs(node3)
        return node2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.31 K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group
方法一：递归

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        cur = head
        cnt = 0
        # 判断是否有k个节点
        while cur and cnt < k:
            cur = cur.next
            cnt += 1
        flag = True if cnt == k else False
        if flag:  # 如果有k个，那么递归吧，返回的是啥画个图就懂了
            cur = self.reverseKGroup(cur, k)
            while cnt:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                cnt -= 1
            return cur
        else:  # 没有k个，就不动，返回头节点
            return head

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

方法二：纯模拟，没有任何技巧

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        dum = ListNode(0, head)
        pre = dum
        while head:
            tail = pre
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dum.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            pre.next, tail.next = head, nex
            pre = tail
            head = tail.next
        return dum.next

    # 翻转一个链表
    def reverse(self, head, tail):
        dum = ListNode(0, head)
        pre = head
        cur = head.next
        while pre is not tail:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre, dum.next

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
29
30
31
32
33
34

2.32 随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer
前两种方法：时间空间都是N
方法一：哈希表，两次循环

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        cur = head
        dic = dict()
        # 把原链表和新构造的链表通过字典关联起来
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        # 再用一个循环完成对新链表每个结点的next域和random域的赋值
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
        return dic[head]

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
29
30
31

方法二：哈希表的递归写法

class Solution(object):

    dic = dict()

    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        # 如果字典中没有当前节点，那么创建节点
        if self.dic.get(head) is None:
            self.dic[head] = Node(head.val)
            # 检查next和random的情况，完成赋值
            self.dic[head].next = self.copyRandomList(head.next)
            self.dic[head].random = self.copyRandomList(head.random)
        return self.dic[head]
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法三：复制连接，再断开
时间N，空间1

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head is None:
            return None
        cur = head
        # 1、复制各node，并建立连接：1->2->3 变成 1->1_new->2->2_new->3->3_new
        while cur:
            tmp = Node(cur.val)
            tmp.next = cur.next
            cur.next = tmp
            cur = tmp.next
        # 2、构建新链表的random指向
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3、拆分两链表，返回新链表的头节点
        cur = res = head.next
        pre = head
        while cur.next:
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre, cur = pre.next, cur.next
        pre.next = None # 处理原链表的尾节点
        return res

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
29
30
31

2.33 排序链表

https://leetcode.cn/problems/sort-list
https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd
方法一：自顶向下归并
时间：O(nlogn)
空间：O(logn)

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 1、终止条件。如果没有节点或者只有一个节点，那么return
        if head is None or head.next is None:
            return head
        # 2、找到中间节点并断开链表，递归下探。1->2->3->4 变成 1->2 3->4，mid是3
        slow = fast = head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        mid = slow.next
        slow.next = None
        l, r = self.sortList(head), self.sortList(mid)
        # 3、合并两个有序链表
        dum = res = ListNode()
        while l and r:
            if l.val <= r.val:
                dum.next = l
                l = l.next
            else:
                dum.next = r
                r = r.next
            dum = dum.next
        dum.next = l if l else r
        return res.next

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
29

方法二：自底向上归并。时间复杂度 O(nlogn)，空间复杂度 O(1)
迭代的写法

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        length, sublen = 0, 1
        res = ListNode(0, head)
        # 1、得到链表的长度
        while head:
            head = head.next
            length += 1
        # 2、当sublen小于length时：
        while sublen < length:
            pre, cur = res, res.next
            while cur:
                # 找到第一个长度为sublen的链表，头节点为left
                left = cur
                for i in range(sublen-1):
                    if cur.next:
                        cur = cur.next
                    else:
                        break
                # 如果left长度没到sublen，直接将left附加到上一个链表结尾
                if not cur.next:
                    pre.next = left
                    break
                # 找第二个长度为sublen的链表，头节点为right
                right = cur.next
                cur.next = None  # 断开
                cur = right
                for i in range(sublen-1):
                    if cur.next:
                        cur = cur.next
                    else:
                        break
                # 处理rihgt链表与后续链表
                tmp = None
                if cur.next:
                    tmp = cur.next
                    cur.next = None
                cur = tmp
                # 将l和r这两个sublen长度的链表合并
                merged = self.mergeTwo(left, right)
                pre.next = merged
                while pre.next:
                    pre = pre.next
            sublen *= 2
        return res.next

    def mergeTwo(self, l1, l2):
        dum = ListNode()
        res = dum
        while l1 and l2:
            if l1.val <= l2.val:
                dum.next = l1
                l1 = l1.next
            else:
                dum.next = l2
                l2 = l2.next
            dum = dum.next
        dum.next = l1 if l1 else l2
        return res.next

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

2.34 合并 K 个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists
方法一：借用合并两个升序链表，遍历即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        l0 = None
        for l in lists:
            l0 = self.mergeTwo(l0, l)
        return l0

    def mergeTwo(self, l1, l2):
        dum = ListNode()
        res = dum
        while l1 and l2:
            if l1.val <= l2.val:
                dum.next = l1
                l1 = l1.next
            else:
                dum.next = l2
                l2 = l2.next
            dum = dum.next
        dum.next = l1 if l1 else l2
        return res.next

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
29
30
31

方法二：二分分治

class Solution(object):
    def mergeKLists(self, lists):
        return self.merge(lists, 0, len(lists)-1)

    def merge(self, lists, l, r):
        if l == r:
            return lists[l]
        if l > r:
            return None
        mid = (l+r)/2
        return self.mergeTwo(self.merge(lists, l, mid), self.merge(lists, mid+1, r))

    def mergeTwo(self, l1, l2):
        dum = ListNode()
        res = dum
        while l1 and l2:
            if l1.val <= l2.val:
                dum.next = l1
                l1 = l1.next
            else:
                dum.next = l2
                l2 = l2.next
            dum = dum.next
        dum.next = l1 if l1 else l2
        return res.next

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

方法三：优先队列
python自带的heapq，利用val进行排序。先存第一列，再逐个pop最小的元素。

class Solution(object):
    def mergeKLists(self, lists):
        dum = ListNode()
        res = dum
        # 创建一个小顶堆
        import heapq
        heap = []
        # 将k个链表的第一个元素加入堆中
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i))
                lists[i] = lists[i].next
        # 当堆不为空时
        while heap:
            val, idx = heapq.heappop(heap)
            dum.next = ListNode(val)
            dum = dum.next
            if lists[idx]:
                heapq.heappush(heap, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return res.next
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.35 LRU 缓存

照着灵神的题解写的，本题使用双向链表 + 哈希表实现O(1)的LRU。增加一个dum节点简化流程。
https://leetcode.cn/problems/lru-cache/solutions/2456294/tu-jie-yi-zhang-tu-miao-dong-lrupythonja-czgt

# 定义一个类
class Node:

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


# 解决方法为双向链表 + 字典
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dum = Node()
        self.dum.prev = self.dum
        self.dum.next = self.dum
        self.dic = dict()

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 如果有这个节点，那么直接覆盖value即可
        node = self.get_node(key)
        if node:
            node.value = value
            return
        # 如果没有key，就new一个
        node = Node(key, value)
        self.dic[key] = node
        self.push_front(node)  # 放在最上面
        # 如果大于容量了,删掉最后一个
        if len(self.dic) > self.capacity:
            last = self.dum.prev
            del self.dic[last.key]
            self.remove(last)

    # 通过key查询node
    def get_node(self, key):
        if key not in self.dic.keys():
            return None
        node = self.dic[key]
        self.remove(node)
        self.push_front(node)
        return node

    # 删除一个node
    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    # 在链表头，即dum后面，添加一个node
    def push_front(self, node):
        node.prev = self.dum
        node.next = self.dum.next
        node.prev.next = node
        node.next.prev = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2.36 二叉树的中序遍历

方法一：递归

class Solution(object):
    def inorderTraversal(self, root):
        res = []  # 将 res 定义为方法内的局部变量
        if not root:
            return res  # 返回空列表
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

1
2
3
4
5
6
7

class Solution(object):
    def inorderTraversal(self, root):
        def dfs(cur):
            if not cur:
                return
            dfs(cur.left)
            res.append(cur.val)
            dfs(cur.right)

        res = []
        dfs(root)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：迭代
显式地维护一个栈。

class Solution(object):
    def inorderTraversal(self, root):
        res = []
        stk = []
        cur = root
        while cur or stk:
            while cur:
                stk.append(cur)
                cur = cur.left
            cur = stk.pop()
            res.append(cur.val)
            cur = cur.right
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.37 二叉树的最大深度

方法一：dfs

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

1
2
3
4
5
6

方法二：bfs，利用队列层序遍历
首先将root入队。对于每一层，先利用tmp存储它的下一层，再将tmp赋值给q，再++res

class Solution(object):
    def maxDepth(self, root):
        res = 0
        if root is None:
            return res
        q = [root]
        tmp = []
        while q:
            tmp = []
            for node in q:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            q = tmp
            res += 1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.38 翻转二叉树

方法一：递归

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def dfs(root):
            if not root:
                return
            if root.left or root.right:
                root.left, root.right = root.right, root.left
            dfs(root.left)
            dfs(root.right)

        dfs(root)
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：迭代
出栈一个节点，首先把它的左右孩子入栈，其次交换左右孩子。

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        st = [root]
        while st:
            node = st.pop()
            if node.left:
                st.append(node.left)
            if node.right:
                st.append(node.right)
            node.left, node.right = node.right, node.left
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.39 对称二叉树

递归：

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def dfs(l, r):
            if l is None and r is None:
                return True
            if l is None or r is None:
                return False
            return l.val == r.val and dfs(l.left, r.right) and dfs(l.right, r.left)

        return dfs(root, root)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

迭代：

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 如果根节点为空或者没有左右孩子，那么为对称二叉树
        if root is None or not (root.left or root.right):
            return True
        que = [root.left, root.right]
        while que:
            l = que.pop()
            r = que.pop()
            # 如果都为空，继续循环
            if not l and not r:
                continue
            # 两者有一个空，那么就不是对称的
            if l is None or r is None:
                return False
            if l.val != r.val:
                return False
            que.append(l.left)
            que.append(r.right)
            que.append(l.right)
            que.append(r.left)
        return True

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

2.40 二叉树的直径

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0

        # return root的最大深度，并且维护全局变量res，即以root为根节点的二叉树的直径（不一定要经过root）
        def helper(root):
            if root is None:
                return 0
            l = helper(root.left)
            r = helper(root.right)
            self.res = max(self.res, l+r)
            return 1+max(l, r)
        helper(root)
        return self.res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.41 二叉树的层序遍历

迭代写法：对于第k层，首先记录这层的节点数，对于每一个节点，首先pop出来，再将其左右孩子入队，再将其val记录到答案中。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return None
        que = [root]
        res = []
        while que:
            size = len(que)
            tmp = []
            for _ in range(size):
                node = que.pop(0)
                if node.left: que.append(node.left)
                if node.right: que.append(node.right)
                tmp.append(node.val)
            res.append(tmp)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

迭代写法：
每次递归的时候都需要带一个 lev (表示当前的层数)。如果当前行对应的 list 不存在，就加入一个空 list 进去。

class Solution(object):
    def levelOrder(self, root):
        res = []

        def dfs(root, lev):
            if root is None:
                return
            if lev == len(res):
                res.append([])
            res[lev].append(root.val)
            dfs(root.left, lev+1)
            dfs(root.right, lev+1)
        dfs(root, 0)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

递归分治

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        def dfs(nums, l, r):
            if l > r:
                return None
            mid = l+r >> 1
            node = TreeNode(nums[mid], dfs(nums, l, mid-1), dfs(nums, mid+1, r))
            return node
        return dfs(nums, 0, len(nums)-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.43 验证二叉搜索树

方法一：递归

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def dfs(root, lo, hi):
            if root is None:
                return True
            val = root.val
            if val <= lo or val >= hi:
                return False
            if dfs(root.left, lo, val) is False or dfs(root.right, val, hi) is False:
                return False
            return True
        return dfs(root, float('-inf'), float('inf'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：中序遍历
进行中序遍历，中序遍历的结果一定是升序的。维护一个最小值，利用栈，边中序，边比较当前元素是否小于这个最小值。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        st = []
        res = True
        init = float('-inf')
        while st or root:
            while root:
                st.append(root)
                root = root.left
            root = st.pop()
            res = res and root.val > init
            init = root.val
            root = root.right
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

中序遍历，找第k个即可

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        st = []
        cnt = 0
        while (st or root) and cnt < k:
            while root:
                st.append(root)
                root = root.left
            root = st.pop()
            res = root.val
            root = root.right
            cnt += 1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.45 二叉树的右视图

就是二叉树的层序遍历，每次记录最右边的元素
bfs：

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return None
        res = []
        que = [root]
        while que:
            size = len(que)
            res.append(que[-1].val)
            for _ in range(size):
                node = que.pop(0)
                if node.left: que.append(node.left)
                if node.right: que.append(node.right)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

dfs：深度优先搜索，这次从right侧深度

class Solution(object):
    def rightSideView(self, root):
        res = []

        def dfs(lev, root):
            if root is None:
                return
            if lev == len(res):
                res.append(root.val)
            dfs(lev+1, root.right)
            dfs(lev+1, root.left)
        dfs(0, root)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.46 二叉树展开为链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        def dfs(root):
            if root is None:
                return
            l = dfs(root.left)
            r = dfs(root.right)
            # 把操作后的左孩子接到 root.right
            root.left = None
            root.right = l
            # 把操作后的右孩子，接到root的最右下角
            tmp = root
            while tmp.right:
                tmp = tmp.right
            tmp.right = r
            return root
        root = dfs(root)
# 作者：小太子仔
# 链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/791939/di-gui-jie-jue-by-xiao-xiu-8-h021/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

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

递归写法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def dfs(p_start, p_end, i_start, i_end):
            if p_start > p_end:
                return None
            idx = inorder.index(preorder[p_start])
            size = idx - i_start
            root = TreeNode(preorder[p_start]
                            ,dfs(p_start+1, p_start+size, i_start, idx-1)
                            ,dfs(p_start+size+1, p_end, idx+1, i_end))
            return root
        n = len(preorder)
        return dfs(0, n-1, 0, n-1)

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

2.48 路径总和 III

方法一：朴素的递归。
首先搜索所有节点，再对于每个当前节点，搜索以其为根的所有（往下的）路径，同时累加路径总和为 targetSum的所有路径。
O(N2)

class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: int
        """
        self.res = 0

        def dfs(root, curSum):
            if root is None:
                return
            curSum += root.val
            if curSum == targetSum:
                self.res += 1
            dfs(root.left, curSum)
            dfs(root.right, curSum)

        def traverse(root):
            if root is None:
                return
            dfs(root, 0)
            traverse(root.left)
            traverse(root.right)

        traverse(root)

        return self.res

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
29

方法二：前缀和

3 其他

快速排序

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def quicksort(l, r):
            if l >= r:
                return
            i, j, pivot = l, r, nums[l]
            while i < j:
                while i < j and nums[j] >= pivot:
                    j -= 1
                while i < j and nums[i] <= pivot:
                    i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[i], nums[l] = nums[l], nums[i]
            quicksort(l, i-1)
            quicksort(i+1, r)

        quicksort(0, len(nums)-1)
        return nums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/182416