A:3740. 三个相等元素之间的最小距离 I
见B。
B:3741. 三个相等元素之间的最小距离 II
给定数组nums，要求值相同的三元组的下标最小距离，距离定义为abs(i - j) + abs(j - k) + abs(k - i)，数据范围为1e5.
我们我们可以按[值，下标]升序排序，然后遍历值相同的三个元素，来更新答案。
1 class Solution: 2 def minimumDistance(self, nums: List[int]) -> int: 3 p=[] 4 for i,x in enumerate(nums): 5 p.append([x,i]) 6 p.sort(key=lambda x:[x[0],x[1]]) 7 ans=inf 8 for i in range(2,len(p)): 9 if p[i][0]==p[i-1][0] and p[i][0]==p[i-2][0]: 10 a=p[i][1] 11 b=p[i-1][1] 12 c=p[i-2][1] 13 ans=min(ans,abs(a-b)+abs(a-c)+abs(c-b)) 14 return ans if ans!=inf else -1
C:3742. 网格中得分最大的路径
上来题读错了，看成四个方向了，其实是右和下的递推。
f[i][j][k]表示走到i,j但是花费不超过k的最大分数，则有f[ i ][ j ][ k ]=max(f[ i-1 ][ j ][ u ], f[ i ][ j-1 ][ u ])，其中u=k-1 if g[i][j]>0 else k.
起始条件为f[i][j][cost]=0,其余为-inf，其中cost=0 if g[0][0]==0 else 1
1 class Solution: 2 def maxPathScore(self, g: List[List[int]], k: int) -> int: 3 n,m=len(g),len(g[0]) 4 k=min(k,m+n-1) 5 f=[[[-inf]*(k+1) for i in range(m)] for j in range(n)] 6 # print(f) 7 cost=0 if g[0][0]==0 else 1 8 if cost>k: 9 return -1 10 f[0][0][cost]=g[0][0] 11 for i in range(n): 12 for j in range(m): 13 if i==0 and j==0: 14 continue 15 for u in range(k+1): 16 maxx=-inf 17 if i>0: 18 preu=u-(1 if g[i][j] else 0) 19 if preu>=0: 20 maxx=max(maxx,f[i-1][j][preu]+g[i][j]) 21 if j>0: 22 preu=u-(1 if g[i][j] else 0) 23 if preu>=0: 24 maxx=max(maxx,f[i][j-1][preu]+g[i][j]) 25 if maxx!=-inf: 26 f[i][j][u]=maxx 27 ans=-1 28 for i in range(k+1): 29 ans=max(ans,f[n-1][m-1][i]) 30 return ans if ans!=-inf else -1