LeetCode 每日一题 2024/11/18-2024/11/24

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

11/18 661. 图片平滑器

遍历每一个点 统计九个位置是否满足

def imageSmoother(img):""":type img: List[List[int]]:rtype: List[List[int]]"""pos = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(0,0),(1,-1),(1,0),(1,1)]m,n = len(img),len(img[0])ret = [[0]*n for _ in range(m)]for i in range(m):for j in range(n):num = 0v = 0for x,y in pos:newi,newj = i+x,j+yif 0<=newi<m and 0<=newj<n:num+=1v += img[newi][newj]ret[i][j] = v//numreturn ret

---

11/19 3243. 新增道路查询后的最短距离 I

dp[i]记录从0到i的最短距离
f[i]记录额外边终点是i的起点列表

def shortestDistanceAfterQueries(n, queries):""":type n: int:type queries: List[List[int]]:rtype: List[int]"""f=[[] for _ in range(n)]dp=list(range(n))ans = []for l,r in queries:f[r].append(l)if dp[l]+1<dp[r]:dp[r]=dp[l]+1for i in range(r+1,n):minv = float("inf")for j in f[i]:minv = min(minv,dp[j])dp[i]=min(dp[i],dp[i-1]+1,minv+1)ans.append(dp[-1])return ans

---

11/20 3244. 新增道路查询后的最短距离 II

不包含两条交叉的单向通道
新增一条单向通道
如果被已考虑的单向通道包含 则不会使路径变短
否则 去掉被包含的单向通道 将该通道加入最短路径
roads记录最短路径的单向通道 roads[i]=j 表示从i到j有一条单向通道
新增道路(i,j)
如果road[i]=-1 说明选择该道路不会减少路径忽略

def shortestDistanceAfterQueries(n, queries):""":type n: int:type queries: List[List[int]]:rtype: List[int]"""road=[i+1 for i in range(n)]ans = []dist = n-1for q in queries:k = road[q[0]]road[q[0]]=q[1]while k!=-1 and k<q[1]:road[k],k=-1,road[k]dist-=1ans.append(dist)return ans

---

11/21 3248. 矩阵中的蛇

题目已知在边界内活动
模拟每一个步骤
up -n
right +1
down +n
left -1

def finalPositionOfSnake(n, commands):""":type n: int:type commands: List[str]:rtype: int"""cur = 0for c in commands:if c=="UP":cur-=nelif c=="DOWN":cur+=nelif c=="RIGHT":cur+=1else:cur-=1return cur

---

11/22 3233. 统计不是特殊数字的数字数量

根据题意 质数的平方数是特殊数字
埃氏筛遍历所有质数的平方是否在区间内

def nonSpecialCount(l, r):""":type l: int:type r: int:rtype: int"""import mathn=int(math.sqrt(r))v = [0]*(n+1)ans = r-l+1for i in range(2,n+1):if v[i]==0:if l<=i*i<=r:ans-=1for j in range(i*2,n+1,i):v[j]=1return ans

---

11/23

---

11/24

---