記錄了初步解題思路 以及本地實現代碼；并不一定為最優 也希望大家能一起探討 一起進步

---

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

---