LeetCode 每日一题 2024/7/1-2024/7/7

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

---

7/1 2065. 最大化一张图中的路径价值

递归回溯 枚举每种情况
每次回到0更新答案

def maximalPathQuality(values, edges, maxTime):""":type values: List[int]:type edges: List[List[int]]:type maxTime: int:rtype: int"""from collections import defaultdictg = defaultdict(list)for x,y,t in edges:g[x].append((y,t))g[y].append((x,t))visited = {0}global ansans = 0def dfs(u,t,va):global ansif u==0:ans = max(ans,va)for v,d in g[u]:if t+d <=maxTime:if v not in visited:visited.add(v)dfs(v,t+d,va+values[v])visited.discard(v)else:dfs(v,t+d,va)dfs(0,0,values[0])return ans

---

7/2 3115. 质数的最大距离

每个数值不大于100 可以得到所有质数
从前往后 从后往前依次寻找第一个遇到的质数
即可得到最小坐标和最大坐标

def maximumPrimeDifference(self, nums):""":type nums: List[int]:rtype: int"""primes = {2, 3, 5, 7, 11,13, 17, 19, 23, 29,31, 37, 41, 43, 47,53, 59, 61, 67, 71,73, 79, 83, 89, 97}n = len(nums)left,right=-1,-1for i in range(n):if nums[i] in primes:left = ibreakfor i in range(n-1,-1,-1):if nums[i] in primes:right = ibreakreturn right-left

---

7/3 3099. 哈沙德数

按定义求和 取余

def sumOfTheDigitsOfHarshadNumber(x):""":type x: int:rtype: int"""num = xv = 0while x>0:v += x%10x //=10return v if num%v==0 else -1

---

7/4 3086. 拾起 K 个 1 需要的最少行动次数

当前位置为i 有两种情况可以捡起1
1.不变换数字：
如果有一个位置x nums[x]=1
x在i两侧 i-1<=x<=i+1只需要一步可以得到一个1
否则需要|x-i|步才可以得到一个1 至少需要2步
2.变换数字：
将邻近数字变为1 交换 2步得到一个1
–
设f(i)为左右1位邻居内的1个数
如果f(i)+maxChanges>=k 那么先将左右两边的先拾起
再使用变换数字的方法得到1
如果f(i)+maxChanges<k 那么先拾取左右两边 使用变换数字方法
最后剩下k-maxChanges个需要不变换数字移动拾取
使用leftc,rightc维护[left,i),(i,right]区间内1的个数
lefts,rights维护区间内值为1的下标和
如果[left,i)区间内的leftc个1要拾取需要每一个都到i
步数为 i*leftc-lefts 右侧同理
从小到大枚举i
根据左右端点离i的远近 去掉较远的

def minimumMoves(nums, k, maxChanges):""":type nums: List[int]:type k: int:type maxChanges: int:rtype: int"""n = len(nums)def f(i):return sum(nums[max(i-1,0):min(i+2,n)])left,right=0,-1lefts,rights=0,0leftc,rightc=0,0ans = float("inf")for i in range(n):if f(i)+maxChanges>=k:if k<=f(i):ans = min(ans,k-nums[i])else:ans = min(ans,2*k-f(i)-nums[i])if k<=maxChanges:continuewhile right+1<n and (right-i<i-left or leftc+rightc+maxChanges<k):if nums[right+1]==1:rightc+=1rights+=right+1right+=1while leftc+rightc+maxChanges>k:if right-i<i-left or right-i==i-left and nums[left]==1:if nums[left]==1:leftc-=1lefts-=leftleft+=1else:if nums[right]==1:rightc-=1rights-=rightright-=1ans = min(ans,leftc*i-lefts+rights-rightc*i+2*maxChanges)if nums[i]==1:leftc+=1lefts+=irightc-=1rights-=ireturn ans

---

7/5 3033. 修改矩阵

遍历 遇到-1寻找当前列最大值替换

def modifiedMatrix(matrix):""":type matrix: List[List[int]]:rtype: List[List[int]]"""m,n=len(matrix),len(matrix[0])for j in range(n):maxv=-1for i in range(m):if matrix[i][j]==-1:if maxv==-1:maxv=max([matrix[x][j] for x in range(m)])matrix[i][j]=maxvreturn matrix

---

7/6 3101. 交替子数组计数

遍历数组记录上一个数数值和当前最长交替子数组长度
如果数值不一致 则交替子数组长度+1
否则子数组长度为1
最长长度即为当前元素结尾的子数组个数 累加

def countAlternatingSubarrays(nums):""":type nums: List[int]:rtype: int"""ans = 0cur = 0pre =-1for num in nums:if pre!=num:cur+=1else:cur=1pre=numans+=curreturn ans

---

7/7 1958. 检查操作是否合法

遍历八个方向 检查是否存在好线段

def checkMove(board, rMove, cMove, color):""":type board: List[List[str]]:type rMove: int:type cMove: int:type color: str:rtype: bool"""def check(dx,dy):x,y = rMove+dx,cMove+dystep = 1while 0<=x<8 and 0<=y<8:if board[x][y]=='.':return Falseif step==1:if board[x][y]==color:return Falseelse:if board[x][y]==color:return Truestep+=1x+=dxy+=dyreturn Falsedx = [1,1,0,-1,-1,-1,0,1]dy = [0,1,1,1,0,-1,-1,-1]for i in range(8):if check(dx[i],dy[i]):return Truereturn False

---