LeetCode 每日一题 2025/2/3-2025/2/9
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 2/3 680. 验证回文串 II
- 2/4 922. 按奇偶排序数组 II
- 2/5 90. 子集 II
- 2/6 47. 全排列 II
- 2/7 59. 螺旋矩阵 II
- 2/8 63. 不同路径 II
- 2/9 80. 删除有序数组中的重复项 II
2/3 680. 验证回文串 II
头尾比较 可以有一次误差 遇到不一致时
分两种情况 去掉left或者去掉right 其中一种满足就可
def validPalindrome(s):
"""
:type s: str
:rtype: bool
"""
def sub(s):
if len(s)==0 or len(s)==1:
return True
i,j=0,len(s)-1
while i<j:
if s[i]!=s[j]:
return False
else:
i+=1
j-=1
return True
i,j=0,len(s)-1
while i<j:
if s[i]!=s[j]:
return sub(s[i+1:j+1]) or sub(s[i:j])
else:
i+=1
j-=1
return True
def validPalindrome2(s):
"""
:type s: str
:rtype: bool
"""
if s==s[::-1]:
return True
i,j=0,len(s)-1
while i<j:
if s[i]==s[j]:
i+=1
j-=1
else:
tmp = s[:i]+s[i+1:]
if tmp==tmp[::-1]:
return True
tmp = s[:j]+s[j+1:]
if tmp==tmp[::-1]:
return True
return False
2/4 922. 按奇偶排序数组 II
- 分奇数偶数两个list 在偶数list中的奇数位 插入奇数
- 用ij记录偶数奇数位置 遍历list 如果是偶数放入i位置 奇数放入j位置
- 遍历一次数组
使用ji,ou两个数组记录不符合未知的数
遇到不符合位置的数时 从ji,ou数组中找到时候存在可交换的位置 有则交换 无则将该位置放入数组
def sortArrayByParityII(nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
odd = [x for x in nums if x%2==1]
ans = [x for x in nums if x%2==0]
p = 1
for i in odd:
ans.insert(p,i)
p+=2
return ans
def sortArrayByParityII2(nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
i,j=0,1
ans = [0]*len(nums)
for x in nums:
if x%2==0:
ans[i]=x
i+=2
else:
ans[j]=x
j+=2
def sortArrayByParityII3( nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ji=[]
ou=[]
for i in range(len(nums)):
if i%2!=nums[i]%2:
if i%2==0:
if len(ji)>0:
loc = ji.pop()
nums[loc],nums[i]=nums[i],nums[loc]
else:
ou.append(i)
else:
if len(ou)>0:
loc = ou.pop()
nums[loc],nums[i]=nums[i],nums[loc]
else:
ji.append(i)
return nums
2/5 90. 子集 II
set 记录重复
def subsetsWithDup(nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ret = []
ret.append([])
ck = set()
for num in nums:
l = []
for tmp in ret:
x = tmp[:]
x.append(num)
t = tuple(sorted(x))
if t not in ck:
l.append(x)
ck.add(t)
ret.extend(l)
return ret
2/6 47. 全排列 II
统计每个数字出现次数 回溯
def permuteUnique(nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
m={}
for i in nums:
m[i] = m.get(i,0)+1
n = len(nums)
ret = []
def back(m,l):
if len(l)==n:
ret.append(l)
return
for c in m:
if m[c]>0:
m[c]-=1
l.append(c)
back(m,l[:])
l.pop()
m[c]+=1
back(m,[])
return ret
2/7 59. 螺旋矩阵 II
顺指针可以 → ↓ ← ↑ 分别对应四种坐标变化(0,1),(1,0),(0,-1),(-1,0)
从→开始 如果遇到边界或者重复则改为下一种走法
def generateMatrix(n):
"""
:type n: int
:rtype: List[List[int]]
"""
matrix = [[0]*n for _ in range(n)]
steplist =[(0,1),(1,0),(0,-1),(-1,0)]
step = 0
num=2
i,j=0,0
matrix[0][0]=1
while num<=n*n:
x,y = steplist[step]
ti,tj = i+x,j+y
if ti<0 or tj<0 or ti>=n or tj>=n or matrix[ti][tj]>0:
step = (step+1)%4
continue
i,j = ti,tj
matrix[i][j] = num
num+=1
return matrix
2/8 63. 不同路径 II
抵达当前位置的路径数量为 左侧位置和上方位置数量之和
def uniquePathsWithObstacles(obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m,n=len(obstacleGrid),len(obstacleGrid[0])
ans = [[0]*n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0]==0:
ans[i][0]=1
else:
break
for j in range(n):
if obstacleGrid[0][j]==0:
ans[0][j]=1
else:
break
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j]==0:
ans[i][j]=ans[i-1][j]+ans[i][j-1]
return ans[-1][-1]
2/9 80. 删除有序数组中的重复项 II
1.使用map记录重复
2.查看与前两位的比较 是否重复两次以上
def removeDuplicates(nums):
"""
:type nums: List[int]
:rtype: int
"""
m={}
loc =0
for i in range(len(nums)):
if m.get(nums[i],0)>=2:
continue
m[nums[i]] = m.get(nums[i],0)+1
nums[loc] = nums[i]
loc+=1
return loc
def removeDuplicates2(nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)<3:
return len(nums)
loc =2
for i in range(2,len(nums)):
if nums[loc-2]==nums[i]:
continue
nums[loc] = nums[i]
loc+=1
return loc