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

---

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 defaultdict
    g = defaultdict(list)
    for x,y,t in edges:
        g[x].append((y,t))
        g[y].append((x,t))
    visited = {0}
    global ans
    ans = 0
    
    def dfs(u,t,va):
        global ans
        if 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,-1
    for i in range(n):
        if nums[i] in primes:
            left = i
            break
    for i in range(n-1,-1,-1):
        if nums[i] in primes:
            right = i
            break
    return right-left

---

7/3 3099. 哈沙德数

按定义求和 取余

def sumOfTheDigitsOfHarshadNumber(x):
    """
    :type x: int
    :rtype: int
    """
    num = x
    v = 0
    while x>0:
        v += x%10
        x //=10
    return 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,-1
    lefts,rights=0,0
    leftc,rightc=0,0
    ans = 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:
            continue
        while right+1<n and (right-i<i-left or leftc+rightc+maxChanges<k):
            if nums[right+1]==1:
                rightc+=1
                rights+=right+1
            right+=1
        while leftc+rightc+maxChanges>k:
            if right-i<i-left or right-i==i-left and nums[left]==1:
                if nums[left]==1:
                    leftc-=1
                    lefts-=left
                left+=1
            else:
                if nums[right]==1:
                    rightc-=1
                    rights-=right
                right-=1
        ans = min(ans,leftc*i-lefts+rights-rightc*i+2*maxChanges)
        if nums[i]==1:
            leftc+=1
            lefts+=i
            rightc-=1
            rights-=i
    return 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=-1
        for 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]=maxv
    return matrix

---

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

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

def countAlternatingSubarrays(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    ans = 0
    cur = 0
    pre =-1
    for num in nums:
        if pre!=num:
            cur+=1
        else:
            cur=1
        pre=num
        ans+=cur
    return 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+dy
        step = 1
        while 0<=x<8 and 0<=y<8:
            if board[x][y]=='.':
                return False
            if step==1:
                if board[x][y]==color:
                    return False
            else:
                if board[x][y]==color:
                    return True
            step+=1
            x+=dx
            y+=dy
        return False
    
    dx = [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 True
    return False

---