这个月开始刷 Leetcode 了,一个月差不多过去了,刷了 80 多道题,开这篇来总结下自己学到啥了吧
两数之和
这题太经典了,目前用了三种方法实现,分别是暴力、维护字典、维护一个新数组转化成顺序数组求,代码如下
# 暴力
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
三数之和
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 了
长度最小的子数组
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. 盛最多水的容器挺像的,不过思路不太一样,后者是个贪心,前者选前缀和后缀的最小再减去个自身高度.
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
