LeetCode刷题

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

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

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

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

时间复杂度：$O(n)$
空间复杂度：$O(n)$

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

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

建立字典，建立唯一的key

1
2
3
4
5
6
7
8
9
10
11
12
# 对于列表，每个字符串对应一个索引，for循环依据索引找到字符串
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp=collections.defaultdict(list)
        #type:defaultdict,访问一个不存在的键，它会自动创建一个空列表 [] 作为值，并把这个键存进去，而不会报错
        # sorted()返回排号序的字符列表
        # "连接符".join(列表)返回字符串，作为唯一的key
        for str in strs:# O(n)
            key="".join(sorted(str))# 排序：O(klogk):分logk层，每层都操作k次，粘贴：O(k),一共O(klogk+k)
            mp[key].append(str)# O(1)
        
        return list(mp.values())
  • 在 Python 中，字典类型本身没有 append 方法。append 方法是列表（list）的一个方法，用于向列表末尾添加一个元素。
    时间复杂度：$O(nklogk)$
    空间复杂度：$O(nk)$
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp=collections.defaultdict(list)
        for st in strs: #O(n)
            counts = [0] * 26
            # ord()：返回字符的 ASCII 码
            for ch in st: #O(k)
                # 得到字母索引0~25
                counts[ord(ch) - ord("a")] += 1 
            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)
        return list(mp.values())
对象类型能否做 Key理由
字符串 (str)能不可变，且哈希计算非常快。
数字 (int/float)能不可变。
元组 (tuple)能不可变（只要元组内部的元素也是不可变的）。
列表 (list)不能可变。你可以随时 append 修改它，这会导致哈希值失效。
字典 (dict)不能可变。

最长连续序列

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

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st=set(nums)
        ans=0
        for x in st:
            if x-1 in st:
                continue
            y=x+1
            while y in st:
                y+=1
            ans = max(ans,y-x)
        return ans

  • 时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

    1. 创建集合 set(nums)：这一步将所有元素放入集合中，时间复杂度为 O(n)。
    2. 主循环 for x in st：这个循环会遍历集合中的每个元素。乍一看似乎会有 O(n) 次迭代，但关键在于循环内部的优化。
    3. 关键优化 if x-1 in st: continue：这个条件检查非常重要。它确保只有当 x 是某个连续序列的起点时（即 x-1 不在集合中），才会继续执行后续操作。这意味着对于任何连续序列，我们只会在该序列的最小元素处执行完整的 while 循环。
    4. while 循环：对于每个连续序列的起点，while 循环会计算该序列的长度。每个元素在所有 while 循环中最多被访问一次。
    5. 总体分析：
    • 每个元素最多被访问两次：
      • 一次在主循环中
      • 一次在 while 循环中（当它属于某个以更小数字开始的序列时）
    • 由于每个元素被访问的次数是常数级别的，所以总体时间复杂度为 O(n)。

  • 空间复杂度分析：

    1. st=set(nums)：这里创建了一个集合来存储输入数组的所有唯一元素。在最坏情况下，如果输入数组中的所有元素都是唯一的，那么这个集合将包含n个元素，因此空间复杂度为O(n)。
    2. ans=0：一个整数变量，占用常数空间O(1)。
    3. 循环变量x和y：这些也是常数空间O(1)。

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

1
2
3
4
5
6
7
8
9
10
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j=0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[i],nums[j]=nums[j],nums[i]
                j+=1
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        m=0
        for x in nums:# 扫描速度不慢于赋值速度
            if x!=0:
                nums[m]=x
                m+=1
        for n in range(m,len(nums)):
            nums[n]=0

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

1
2
3
4
5
6
7
8
class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 时间复杂度O(n^2)
        ans=0
        for i in range(len(height)-1):
            for j in range (i+1,len(height)):
                    ans= max(ans,min(height[i],height[j])*(j-i))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
                left,right=0,len(height)-1
        ans=0
        while left<right:
            area= min(height[left],height[right])*(right-left)
            ans=max(area,ans)
            if height[left]<height[right]:
                left+=1
            else:
                right -=1
        return ans

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

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 threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        ans=[]
        for i in range(0,len(nums)-2):
            if nums[i]>0:
                break
            if i >0 and nums[i]==nums[i-1]:
                continue
            l=i+1
            r=len(nums)-1
            while l<r:
                total= nums[i]+nums[l]+nums[r]
                if total==0:
                    ans.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
                elif total<0:
                    l+=1
                else:
                    r-=1

        return ans

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def trap(self, height: List[int]) -> int:
        leftmax=[0]*len(height)
        leftmax[0]=height[0]
        rightmax=[0]*len(height)
        rightmax[len(height)-1]=height[-1]
        ans=0
        for i in range(1,len(height)):
            leftmax[i]=max(height[i],leftmax[i-1])
        for j in range(len(height)-2,-1,-1):
            rightmax[j]=max(height[j],rightmax[j+1])
        for m in range(len(height)):
            ans=ans+min(leftmax[m],rightmax[m])-height[m]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        l=0
        r=len(height)-1
        ans=0
        leftmax=height[l]
        rightmax=height[r]
        while l<=r:
            if leftmax<rightmax:
                ans=ans+leftmax-height[l]
                l+=1
                leftmax=max(leftmax,height[l])
            else:
                ans=ans+rightmax-height[r]
                r-=1
                rightmax=max(rightmax,height[r])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def trap(self, height: List[int]) -> int:
        ans=0
        st=[]
        for i,h in enumerate(height):
            while st and h>height[st[-1]]:
                bottom_h=height[st.pop()]
                if len(st)==0:
                    break
                dh=min(h,height[st[-1]])-bottom_h
                ans+=dh*(i-st[-1]-1)
            st.append(i)
        return ans

无重复字符的最长子串

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

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

遍历左指针，固定，调整右指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans=0
        right=0
        map=set()
        for left in range(len(s)):
            if left>0:
                map.remove(s[left-1])
            while right< len(s) and s[right] not in map:
                map.add(s[right])
                right+=1
            ans=max(ans,right-left)
        return ans

遍历右指针，固定，调整左指针
当遍历右指针时，发现元素在集合中，左指针右移，集合内并消除左指针对应元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans=0
        left=0
        map=set()
        for right,x in enumerate(s):
            while x in map:
                map.remove(s[left])
                left+=1
            map.add(x)
            ans=max(ans,right-left+1)
        return ans

遍历右指针，固定，调整左指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans=0
        left=0
        map=defaultdict(int)
        for right,x in enumerate(s):
            map[x]+=1
            while map[x]>1:
                map[s[left]]-=1
                left+=1
            ans=max(ans,right-left+1)
        return ans

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt_p=Counter(p)
        cnt_s=Counter()
        left=0
        ans=[]
        for right,x in enumerate(s):
            cnt_s[x]+=1
            if right < len(p)-1:
                continue
            if cnt_p==cnt_s:
                ans.append(left)
            cnt_s[s[left]]-=1
            left+=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt=Counter(p)
        ans=[]
        left=0
        for right,x in enumerate(s):
            cnt[x]-=1
            while cnt[x]<0:
                cnt[s[left]]+=1
                left+=1
            if right-left+1==len(p):
                ans.append(left)
        return ans

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 计算前缀和，第一个为0，保证如果前缀和-k=0时计数
        sum=[0]*(len(nums)+1)
        ans=0
        for i ,x in enumerate(nums):
            sum[i+1] =sum[i]+x
        cnt=defaultdict(int)
        for x in sum:
            ans+=cnt[x-k]
            cnt[x]+=1
        return ans

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

用双端队列做单调栈，保存窗口滑动时的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
   def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
       ans=[]
       q=deque()
       for i,x in enumerate(nums):
           # 保证索引对应值的单调性
           while q and nums[q[-1]]<=x:
               q.pop()
           q.append(i)
           if q[0]<i-k+1:
               q.popleft()
           if i>=k-1:
               ans.append(nums[q[0]])
       return ans

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。
测试用例保证答案唯一。
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’

用双指针扫描，遍历右指针，左指针右移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt_s=Counter()
        cnt_t=Counter(t)
        ans_left=-1
        ans_right=len(s)-1
        left=0
        for right ,x in enumerate(s):
            cnt_s[x]+=1
            while cnt_s>=cnt_t:
                if right-left<ans_right-ans_left:
                    ans_left,ans_right=left,right
                cnt_s[s[left]]-=1
                left+=1
        return ""if ans_left<0 else s[ans_left:ans_right+1]

最大子数组和

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

前缀和相减s[i]-s[j]，s[j]应该是j~i中最小的，且i一定是小于j

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        min_s=0
        ans=float('-inf')
        s=[0]*(len(nums)+1)
        for i ,x in enumerate(nums):
            s[i+1]=x+s[i]
            ans=max(ans,s[i+1]-min_s)
            min_s=min(min_s,s[i+1])
        return ans

如果前面的最大前缀和为负数，直接不要了

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f=0
        ans=float('-inf')
        for x in nums:
            f=max(f,0)+x
            ans=max(ans,f)
        return ans

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

先对区间左端点进行排序，遍历时，前一区间右端点大于等于后一区间左端点才合并

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

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(i:int,j:int)->None:
            while i<j:
                nums[i],nums[j]=nums[j],nums[i]
                i+=1
                j-=1
        n=len(nums)
        k%=n
        reverse(0,n-1)
        reverse(0,k-1)
        reverse(k,n-1)
1
2
3
4
5
6
7
8
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        nums[:] = nums[n-k:] + nums[:n-k]

除了自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

计算前缀乘积，后缀乘积，用zip组合调取

1
2
3
4
5
6
7
8
9
10
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        pre=[1]*n
        for i in range(1,n):
            pre[i]=pre[i-1]*nums[i-1]
        surf=[1]*n
        for j in range(n-2,-1,-1):
            surf[j]=surf[j+1]*nums[j+1]
        return [p*s for p,s in zip(pre,surf)]

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

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

用nums[i]==nums[nums[i]-1]
理论第a个座位应该是a+1，不是就换

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        for i in range(n):
            while 1<=nums[i]<=n and nums[nums[i]-1]!=nums[i]:
                j=nums[i]-1#应该坐的位置
                nums[i],nums[j]=nums[j],nums[i]
        for i in range(n):
            if nums[i]!=i+1:
                return i+1
        return n+1

矩阵置零

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

空间复杂度$O(1)$

第一行，第一列单独拿出来看有没有0
扫描子矩阵的行，列看有没有0，记录在第一行的该行，该列对应位置
即使子矩阵的行，列没有0，原本第一行如果有0，修改对应列
再将一开始扫的第一行如果有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
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m=len(matrix)
        n=len(matrix[0])
        x=0 in matrix[0]
        y=any(row[0]==0 for row in matrix)
        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
        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
        if x:
            for j in range(n):
                matrix[0][j]=0
        if y:
            for row in matrix:
                row[0]=0

螺旋矩阵

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

遇到边界，右转，遵循右（行不变，列加1，右转到）下（行加1，列不变，右转到）左（右转到）上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
   def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
       direction=(0,1),(1,0),(0,-1),(-1,0)#右，下，左，上
       ans=[]
       i=j=di=0
       row=len(matrix)
       col=len(matrix[0])
       for _ in range(row*col):
           ans.append(matrix[i][j])
           matrix[i][j]=None
           x=i+direction[di][0]
           y=j+direction[di][1]
           if x<0 or x>=row or y<0 or y>=col or matrix[x][y]==None:
               di=(di+1)%4
           i+=direction[di][0]
           j+=direction[di][1]
       return ans

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

先沿主对角线反转，再每行翻转

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n=len(matrix)
        for i in range(n):
            for j in range(i+1,n):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
        for row in matrix:
            row.reverse()

搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

找上升和下降的边界，比一次，知道一行或一列的信息，进行调整

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m=len(matrix)
        n=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:
                i+=1
            else:
                j-=1
        return False

相交链表

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

链表的最后一个指针一定指向None

1
2
3
4
5
6
7
8
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p=headA
        q=headB
        while p is not q:
            p=p.next if p else headB
            q=q.next if q else headA
        return p

反转链表

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

建立一个新列表，从末尾None往上排

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current=head
        pre=None
        while current:
            nxt=current.next
            current.next=pre
            pre=current
            current=nxt
        return pre