Leetcode 之第一个月学了什么

这个月开始刷 Leetcode 了,一个月差不多过去了,刷了 80 多道题,开这篇来总结下自己学到啥了吧（2023-04-27写的）

两数之和

链接

这题太经典了,目前用了三种方法实现,分别是暴力、维护字典、维护一个新数组转化成顺序数组求,代码如下

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
# 暴力
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]
                    
# 维护字典
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        tmp=dict()
        for i,val in enumerate(nums):
            if val in tmp.keys():
                return [i,tmp[val]] 
            tmp[target-val]=i
            
# 转为顺序数组求
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        i=0
        j=n-1
        tmp=list(range(n))
        tmp.sort(key=lambda x:nums[x])# tmp 存 nums 的索引,保证 nums[tmp[i]] 是按序的
        while True:
            s=nums[tmp[i]]+nums[tmp[j]]
            if s==target:
                return [tmp[i],tmp[j]]
            elif s>target:
                j-=1
            else:i+=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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        ans=[]
        nums.sort()

        for i in range(n-2):
            x=nums[i]
            if i>0 and nums[i-1]==x:
                continue
            l=i+1
            k=n-1
            while l<k:
                tmp=x+nums[l]+nums[k]
                if tmp==0:
                    ans.append([x,nums[l],nums[k]])
                    l+=1
                    k-=1   
                    while l<k and nums[l]==nums[l-1]:
                        l+=1
                    while l<k and nums[k]==nums[k+1]:
                        k-=1    
                elif tmp>0:
                    k-=1
                else:
                    l+=1
        return ans

核心就是不能重复,i l k 都要判断一次,另外还有两处优化没写,分别是 i 和它紧接着的两个如果都大于零就可以直接 break 出去了,还有一个是 i 和最后两个加起来小于 0 就可以 continue 了

长度最小的子数组

链接

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n=len(nums)
        ans=n+1
        l=0
        tmp=0
        for i in range(n):
            tmp+=nums[i]
            while tmp>=target:
                tmp-=nums[l]
                ans=min(ans,i-l+1)
                l+=1
        return ans if ans<=n else 0

同向双指针的套路题,713. 乘积小于 K 的子数组和3. 无重复字符的最长子串是一样的.

接雨水

链接

会的第一道困难题,和11. 盛最多水的容器挺像的,不过思路不太一样,后者是个贪心,前者选前缀和后缀的最小再减去个自身高度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        fi=[0]*n
        fi[0]=height[0]
        for i in range(1,n):
            fi[i]=max(height[i],fi[i-1])
        we=[0]*n
        we[-1]=height[-1]
        for i in range(n-2,-1,-1):
            we[i]=max(height[i],we[i+1])
        ans=0
        for i,j,k in zip(fi,we,height):
            ans+=min(j,i)-k
        return ans