leetcode

发表于 |
| 字数统计 6.5k 字 | 阅读时长 28 分

4.12

两数之和

自己写的：超出时间限制了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res=[]
        nums=sorted(nums) #题目要求返回下标，不能排序了。
        start,end=0,len(nums)-1
        while start<end: #可能陷入死循环了
            if nums[start]+nums[end]==target:
                res.append(start)
                res.append(end)
                start+=1 #忘记循环加1了，之前就死循环了。
            elif nums[start]+nums[end]<target:
                start+=1
            else:
                end-=1
        print(res)

结果：

改进：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res=[]
        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    res.append(i)
                    res.append(j)
        return res

结果：

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hastable=dict()
        for i, num in enumerate(nums):
            if target-num in hastable:
                return [i,hastable[target-num]]
            hastable[num]=i
        return []

借助哈希表，如果target-nums[i]对应的值不在哈希表中，就将nums[i]和下标i存到哈希表里

遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值

如果存在则找到了两个值，并返回这两个值对应的下标。

三数之和

自己写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result=[]
        res=[]
        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    if nums[i]+nums[j]+nums[k]==0:
                        res.append(nums[i])
                        res.append(nums[j])
                        res.append(nums[k])
                        result.append(res)
                        res=[]
                    else:continue
        print(result)
        return result

结果：

问题：输出的三元组有重复的，如[-1,0,1]和[0,1,-1]，不符合题意。使用了三重循环，时间复杂度较大，有待改进。

参考答案：
使用双指针解法，利用排序避免重复答案，头指针start指向第一个元素，尾指针end指向最后一个元素。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums=sorted(nums)
        print(nums)
        n = len(nums)
        ans = []
        for first in range(n):
            if first > 0 and nums[first] == nums[first - 1]:#跳过重复元素
                continue
            if nums[first] > 0:
                break
            second, third = first + 1, n - 1
            while second < third:
                target = -(nums[first] + nums[second])
                if target < 0:
                    break
                while second + 1 < third and nums[third] > target:
                    #nums[third] > target，nums[third]偏大，需要向左移动一位
                    third -= 1
                if nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
                    while second + 1 < third and nums[third] == nums[third - 1]:
                        third -= 1
                    third -= 1
                while second + 1 < third and nums[second] == nums[second + 1]:
                    second += 1
                second += 1
        return ans
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
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        dic = dict()
        res = list()
        target = 0

        for i in nums: #统计nums数组中各个元素的个数
            dic[i] = dic.get(i, 0) + 1

        n1 = [n for n in dic.keys() if n < 0] #小于0的元素集合
        n2 = [n for n in dic.keys() if n > 0] #大于0的元素集合

        if 0 in dic and  dic[0] >= 3: #nums数组中0元素个数大于3
            res.append([0,0,0])

        for i in n1: #i指针在小于0的集合中
            for j in n2: #j指针在大于0的集合中
                k = -i-j # i+j+k=0
                if k in dic:
                    if i < k < j:
                        res.append([i,k,j])
                    elif i <= k < j: #i=k时
                        if dic[i] >= 2: #如果i的个数大于2
                            res.append([i,i,j])
                    elif i < k <= j: #j=k时
                        if dic[j] >= 2: #如果j的个数大于2
                            res.append([i, j, j])
        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
class Solution: #三重循环解法
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() #首先利用sort函数对数组进行排序
        n = len(nums) #利用len函数得到数组的长度
        res = [] #初始化一个返回列表
        for i in range(n): #开始外部大循环
            tmp = -nums[i] #题目要求三者相加为0，这边就是直接取了负号，后面比较方便
            if i > 0 and nums[i] == nums[i - 1]: #如果当前元素和上一个元素相同，则跳过，防止重复解
                continue#这里要注意和上一个元素比较，这样子可以避免漏判，有可能出现相邻两个元素全部征用的可能，例如[-2,-2,4]
            p, q = i + 1, n - 1 #因为i前面的元素作为第一层循环已经遍历过了，这边注意边界条件，防止重复
            while p < q: #双指针的循环结束条件，左右指针相遇了
                if nums[p] + nums[q] == tmp: #首先判断是否满足条件
                    res.append([nums[i], nums[p], nums[q]]) #如果满足条件，放到返回列表中
                    while p < q and nums[p] == nums[p + 1]: #此处用来跳过相同元素，注意比较的方向
                        p += 1 #如果下一个元素相同，则继续右移
                    while p < q and nums[q - 1] == nums[q]: #此处用来跳过相同元素，注意比较的方向
                        q -= 1#如果左边一个元素相同，则继续右移
                    p += 1 #注意一下如果此时的索引位置符合条件，那么在没有重复的情况下，这两个索引均不能用了，所以此时左右指针同时变化
                    q -= 1
                elif nums[p] + nums[q] < tmp: #因为数组是拍过序的，所以如果小了，左指针右移增大元素
                    p += 1
                else: #因为数组是拍过序的，所以如果大了，右指针左移减小元素
                    q -= 1

        return res #返回结果的res

4.13

最大子数组和

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

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

自己写的：
没思路。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum=0
        max=nums[0]
        for i in range(0,len(nums)):
            sum+=nums[i]
            if sum>max:
                max=sum
                if sum<0:
                    sum=0
            elif sum<0:
                sum=0
        return max

结果：

参考答案：

1
2
3
4
5
6
7
8
9
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1,len(nums)):
            nums[i]=nums[i]+max(nums[i-1],0)
        return max(nums)

动态规划思想
nums[i-1]和nums[i]相加，如果nums[i-1]比0小，那么对于结果无增益效果，nums[i]直接记录结尾为nums[i]的子串的最大值。

4.15

搜索旋转排序数组

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

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

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

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

关键：时间复杂度为O(log n)，考虑二分查找。

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
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]: # 左边数组有序
                if nums[0] <= target < nums[mid]: # target在0到mid之间
                    r = mid - 1
                else:
                    l = mid + 1
            else: # 右边数组有序
                if nums[mid] < target <= nums[len(nums) - 1]: # target在mid到末尾之间
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

买卖股票的最佳时机

自己写的：用的暴力解法，结果测试用例中有大数据，超时了。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=[0]*len(prices)
        for i in range(0,len(prices)):
            for j in range(i+1,len(prices)):
                tmp=prices[j]-prices[i]
                if tmp>profit[i]:
                    profit[i]=tmp
        return max(profit)

结果：

参考答案：

动态规划思想

  1. 记录【今天之前买入的最小值】
  2. 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
  3. 比较【每天的最大获利】，取最大值即可
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices)<=1: # prices数组长度小于等于1，直接返回0.
                return 0
            minn,maxn=prices[0],0 # 第一天的价格赋予买入的最小值，第一天最大获利为0
            for i in range(1,len(prices)):
                maxn=max(maxn,prices[i]-minn) # maxn代表今天卖出的最大获利，prices[i]-minn代表如果今天卖出的话，获利多少。
                minn=min(minn,prices[i]) # minn代表今天之前买入的最小值
            return maxn

合并区间

自己并没有什么思路

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0]) # 按照区间的左端点排序，排序后的列表中，可以合并的区间一定是连续的。

        merged = [] # merged存储最终的答案
        for interval in intervals:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则的话，我们就可以与上一区间进行合并
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

用数组 merged 存储最终的答案。

首先，将列表中的区间按照左端点升序排序。然后将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

  • 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；

  • 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

4.16

下一个排列

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
    整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。

  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
    给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。
自己写的：

思路：在数组内倒着找试试？不会实现。。。

参考答案：

思路：

  1. 我们希望下一个数 比当前数大，这样才满足 “下一个排列” 的定义。因此只需要 将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
  2. 我们还希望下一个数 增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
    1. 在 尽可能靠右的低位 进行交换，需要 从后向前 查找
    2. 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
    3. 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列
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
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
         # 定义一个将nums中[i,j]区间的元素原地倒排的函数
        def reverse(nums,i,j):
            while(i<j):
                nums[i],nums[j]=nums[j],nums[i]
                i+=1
                j-=1
        # 从右至左找第一个相邻升序对
        n=len(nums)
        firstIndex=-1
        for i in range(n-1,-1,-1):
            if nums[i-1]<nums[i]:
                firstIndex=i-1
                break
        # 如果没有找到升序对，则数组是降序的，即本身是最大的，所以反转数组，使之成为最小的排列
        if firstIndex==-1:
            reverse(nums,0,n-1)
            return
        # 从右至左找第一个大于nums[firstIndex]的大数
        secondeIndex=-1
        for i in range(n-1,firstIndex,-1):
            if nums[i]>nums[firstIndex]:
                secondeIndex=i
                break
        nums[firstIndex],nums[secondeIndex]=nums[secondeIndex],nums[firstIndex]
        reverse(nums,firstIndex+1,n-1)

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

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

构造二叉树，使用递归。

参考答案：

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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

使用递归函数时，要注意递归函数的边界：

4.18

子集

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

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

参考答案：

方法一：回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        size = len(nums)
        if size == 0:
            return []

        res = []
        self.__dfs(nums, 0, [], res)
        return res

    def __dfs(self, nums, start, path, res):
        # path：递归路径上的数字
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            # 因为 nums 不包含重复元素，并且每一个元素只能使用一次
            # 所以下一次搜索从 i + 1 开始
            self.__dfs(nums, i + 1, path, res)
            path.pop() # 最后一个数记得pop出来

回溯法：增量构造，类似递归。

方法二：位运算法

数组的每个元素，可以有两个状态：

  • 不在子数组中（用0表示）
  • 在子数组中（用1表示）
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        size = len(nums)
        n = 1 << size # 1左移size位，可以用二进制表示数组中的所有数。
        res = []
        for i in range(n):
            cur = []
            for j in range(size):
                if i >> j & 1: # nums[j]的二进制表示是否为1
                    cur.append(nums[j])
            res.append(cur)
        return res

4.19

二叉树的层序遍历

思路：借用队列完成层序遍历，根节点入队，若他的左右孩子不为none，则依次入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None: return [] # 特判
        que = collections.deque([root]) # 双端队列，比用数组模拟队列速度快
        ans = []
        while len(que) != 0:
            size = len(que)
            level = []
            for _ in range(size): # 遍历当前层节点
                cur = que.popleft() # 从左边弹出队列
                level.append(cur.val) # 将当前节点值加入当前层的列表
                if cur.left != None: que.append(cur.left)
                if cur.right != None: que.append(cur.right)
            ans.append(level) # 将当前层结果加入答案列表
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        que=deque()
        if root==None:
            return []
        else:
            que.append(root) # 如果root不为空的话，就将root放到双端队列中
        res=[] # 记录最终结果
        while True:
            a=[] # 记录当前层的结果
            b=deque() # 构造第二个队列，root出来一个就放到b队列里一个
            while len(que)!=0:
                b.append(que.popleft()) 
            for i in range(len(b)):
                if b[i]!=None: # 如果b[i]不为none，就将b[i]的值放到当前层的结果中，并将他的左右孩子入队。
                    a.append(b[i].val)
                    que.append(b[i].left)
                    que.append(b[i].right)
            if len(a)!=0:
                res+=[a]
            if len(que)==0:
                break
        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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None



# 递归
# 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
# 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn)

# 递归1：二叉树遍历最易理解和实现版本
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        # 前序递归
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
        # # 中序递归 
        # return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
        # # 后序递归
        # return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

# 递归2：通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(cur):
            if not cur:
                return      
            # 前序递归
            res.append(cur.val)
            dfs(cur.left)
            dfs(cur.right) 
            # # 中序递归
            # dfs(cur.left)
            # res.append(cur.val)
            # dfs(cur.right)
            # # 后序递归
            # dfs(cur.left)
            # dfs(cur.right)
            # res.append(cur.val)      
        res = []
        dfs(root)
        return res



# 迭代
# 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
# 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)

# 迭代1：前序遍历最常用模板（后序同样可以用）
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []        
        res = []
        stack = [root]
        # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res
        
        # # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
        # while stack:
        #     cur = stack.pop()
        #     if cur.left:
        #         stack.append(cur.left)
        #     if cur.right:
        #         stack.append(cur.right)
        #     res.append(cur.val)
        # return res[::-1]

# 迭代1：层序遍历最常用模板
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        cur, res = [root], []
        while cur:
            lay, layval = [], []
            for node in cur:
                layval.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            cur = lay
            res.append(layval)
        return res

        
        
# 迭代2：前、中、后序遍历通用模板（只需一个栈的空间）
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]: 
        res = []
        stack = []
        cur = root
        # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res
        
        # # 前序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.left
        #     cur = stack.pop()
        #     cur = cur.right
        # return res
        
        # # 后序，相同模板
        # while stack or cur:
        #     while cur:
        #         res.append(cur.val)
        #         stack.append(cur)
        #         cur = cur.right
        #     cur = stack.pop()
        #     cur = cur.left
        # return res[::-1]
        


# 迭代3：标记法迭代（需要双倍的空间来存储访问状态）：
# 前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
# 而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [(0, root)]
        while stack:
            flag, cur = stack.pop()
            if not cur: continue
            if flag == 0:
                # 前序，标记法
                stack.append((0, cur.right))
                stack.append((0, cur.left))
                stack.append((1, cur))
                
                # # 后序，标记法
                # stack.append((1, cur))
                # stack.append((0, cur.right))
                # stack.append((0, cur.left))
                
                # # 中序，标记法
                # stack.append((0, cur.right))
                # stack.append((1, cur))
                # stack.append((0, cur.left))  
            else:
                res.append(cur.val)  
        return res
        
        # # 层序，标记法
        # res = []
        # queue = [(0, root)]
        # while queue:
        #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
        #     if not cur: continue
        #     if flag == 0:
                  # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
        #         queue.append((1, cur))
        #         queue.append((0, cur.left))
        #         queue.append((0, cur.right))
        #     else:
        #         res.append(cur.val)
        # return res



# 莫里斯遍历
# 时间复杂度：O(n)，n为节点数，看似超过O(n)，有的节点可能要访问两次，实际分析还是O(n)，具体参考大佬博客的分析。
# 空间复杂度：O(1)，如果在遍历过程中就输出节点值，则只需常数空间就能得到中序遍历结果，空间只需两个指针。
# 如果将结果储存最后输出，则空间复杂度还是O(n)。

# PS：莫里斯遍历实际上是在原有二叉树的结构基础上，构造了线索二叉树，
# 线索二叉树定义为：原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点
# emmmm，好像大学教材学过，还考过

# 此处只给出中序遍历，前序遍历只需修改输出顺序即可
# 而后序遍历，由于遍历是从根开始的，而线索二叉树是将为空的左右子节点连接到相应的顺序上，使其能够按照相应准则输出
# 但是后序遍历的根节点却已经没有额外的空间来标记自己下一个应该访问的节点，
# 所以这里需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
# 具体参考大佬博客

# 莫里斯遍历，借助线索二叉树中序遍历（附前序遍历）
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        # cur = pre = TreeNode(None)
        cur = root

        while cur:
            if not cur.left:
                res.append(cur.val)
                # print(cur.val)
                cur = cur.right
            else:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right
                if not pre.right:
                    # print(cur.val) 这里是前序遍历的代码，前序与中序的唯一差别，只是输出顺序不同
                    pre.right = cur
                    cur = cur.left
                else:
                    pre.right = None
                    res.append(cur.val)
                    # print(cur.val)
                    cur = cur.right
        return res



# N叉树遍历
# 时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。
# 空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。
# 将根节点推出栈后，需要将这些节点都放入栈，共有 M−1个节点，因此栈的大小为 O(M)。


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

# N叉树简洁递归
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root: return []
        res = [root.val]
        for node in root.children:
            res.extend(self.preorder(node))
        return res

# N叉树通用递归模板
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        def helper(root):
            if not root:
                return
            res.append(root.val)
            for child in root.children:
                helper(child)
        helper(root)
        return res

# N叉树迭代方法
class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        s = [root]
        # s.append(root)
        res = []
        while s:
            node = s.pop()
            res.append(node.val)
            # for child in node.children[::-1]:
            #     s.append(child)
            s.extend(node.children[::-1])
        return res

4.23

无重复字符的最长子串

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

自己写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_n=0
        tmp=0
        dict_str={}
        if s=="":
            return 0
        for i in s:
            dict_str[i]=False
        print(dict_str)
        for i in s:
            if dict_str[i]==True:
                tmp=0
            dict_str[i]=True
            tmp+=1
            if tmp>max_n:
                max_n=tmp
        return max_n

错误：

类似dvd这种两边有重复字符，中间的子串就被忽略了。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

4.24

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre=None
        node=head
        while node!=None:
            nextnode=node.next
            node.next=pre
            pre=node
            node=nextnode
        return pre #  函数的返回值是ListNode*类型的，所以返回这个链表的头节点就可以了。leetcode会根据这个头节点进行遍历，直至NULL为止。若遍历到的链表与答案一致，则判定正确

-------------本文结束感谢阅读-------------