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

---

1/29 514. 自由之路

key中每一个字符都需要按一次 即m=len(key)
该值固定可以 最后加上即可
假设状态(i,j)为当前ring[i],key[j]
当两值相等时可以变换到(i,j+1)
否则左移 ((i-1+n)%n,j)
右移((i+1)%n,j)
从(0,0) 到(i,m)最短路径即为答案

def findRotateSteps(ring, key):""":type ring: str:type key: str:rtype: int"""n,m=len(ring),len(key)mem = [[False]*(m+1) for _ in range(n)]mem[0][0]=Truel = [(0,0)]step = 0while True:tmp = []for i,j in l:if j==m:return stepif ring[i]==key[j]:if not mem[i][j+1]:mem[i][j+1]=Truetmp.append((i,j+1))continuefor nxt in [(i-1)%n,(i+1)%n]:if not mem[nxt][j]:mem[nxt][j]=Truetmp.append((nxt,j))step+=1

---

1/30 2808. 使循环数组所有元素相等的最少秒数

可以选择将每一位置的数变为左右两侧的数
对每一个数值x记录其依次出现的位置
如果要将所有数变为x
需要的最少次数为两个x的最远距离除以二

def minimumSeconds(nums):""":type nums: List[int]:rtype: int"""from collections import defaultdictm = defaultdict(list)n = len(nums)ans = nfor i,v in enumerate(nums):m[v].append(i)for pos in m.values():mx = pos[0]+n-pos[-1]for i in range(len(pos)):mx = max(mx,pos[i]-pos[i-1])ans = min(ans,mx//2)return ans

---

1/31 2670. 找出不同元素数目差数组

从前到后判断有多少不同数目
从后往前同样判断一次

def distinctDifferenceArray(nums):""":type nums: List[int]:rtype: List[int]"""n = len(nums)ans = [0]*nm = {}for i,v in enumerate(nums):m[v]=1ans[i]=len(m)m={}for i in range(n-1,-1,-1):ans[i]-=len(m)m[nums[i]]=1return ans

---

2/1 LCP 24. 数字游戏

可以看做将nums[j]-j变成相同的数字
使用两个堆来存放数值
low用来存放小的 up用来存放大的
lows,ups分别为数值和
考虑每一个数 保持up中的数个数不多于low

def numsGame(nums):""":type nums: List[int]:rtype: List[int]"""import heapqn=len(nums)ans = [0]*nlow,up=[],[]lows,ups=0,0mod = 10**9+7for i in range(n):x = nums[i]-iif len(low)==0 or -low[0]>=x:lows+=xheapq.heappush(low,-x)if len(low)>len(up)+1:ups -=low[0]heapq.heappush(up,-low[0])lows += heapq.heappop(low)else:ups+=xheapq.heappush(up,x)if len(low)<len(up):lows += up[0]heapq.heappush(low,-up[0])ups -= heapq.heappop(up)if (i+1)%2==0:ans[i] = (ups-lows)%modelse:ans[i]=(ups-lows-low[0])%modreturn ans

---

2/2 1686. 石子游戏 VI

如果有两个石子i,j
alice价值 ia,ja
bob价值 ib,jb
两种情况 alice取i 或取j
差值为 ia-jb-(ja-ib) = ia+ib -(ja+jb)
如果大于0则alice先选i 优先选 ia+ib大的石头
将石头两个人的价值相加后倒序排列 两人依次选取

def stoneGameVI(aliceValues, bobValues):""":type aliceValues: List[int]:type bobValues: List[int]:rtype: int"""v = [[a+b,a,b] for a,b in zip(aliceValues,bobValues)]v.sort(reverse=True)asum = sum(value[1] for value in v[::2])bsum = sum(value[2] for value in v[1::2])if asum>bsum:return 1elif asum==bsum:return 0else:return -1

---

2/3 1690. 石子游戏 VII

动态规划
先求出区间[i,i]的最大的得分差值
向外扩展 直至扩展到区间[0,n-1]

def stoneGameVII(stones):""":type stones: List[int]:rtype: int"""n=len(stones)s = [0]*(n+1)dp=[[0]*n for _ in range(n)]for i in range(n):s[i+1] = s[i]+stones[i]for i in range(n-2,-1,-1):for j in range(i+1,n):dp[i][j] = max(s[j+1]-s[i+1]-dp[i+1][j],s[j]-s[i]-dp[i][j-1])return dp[0][n-1]

---

2/4 292. Nim 游戏

如果是4的倍数 先手必输 先手拿x个 后手拿4-x个 最后必定是后手拿到
否则 先手取若干个将其变成4的倍数 那么对手就变成了先手4的倍数

def canWinNim(n):""":type n: int:rtype: bool"""return n%4!=0

---