奉贤区网站建设,天津二十四格制作公司,南山的网站建设公司,1688跨境专供海外代发记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 1/29 514. 自由之路1/30 2808. 使循环数组所有元素相等的最少秒数1/31 2670. 找出不同元素数目差数组2/1 LCP 24. 数字游戏2/2 1686. 石子游戏 VI2/3 1690. 石子游戏 VII2/…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 1/29 514. 自由之路1/30 2808. 使循环数组所有元素相等的最少秒数1/31 2670. 找出不同元素数目差数组2/1 LCP 24. 数字游戏2/2 1686. 石子游戏 VI2/3 1690. 石子游戏 VII2/4 292. Nim 游戏 1/29 514. 自由之路 key中每一个字符都需要按一次 即mlen(key) 该值固定可以 最后加上即可 假设状态(i,j)为当前ring[i],key[j] 当两值相等时可以变换到(i,j1) 否则左移 ((i-1n)%n,j) 右移((i1)%n,j) 从(0,0) 到(i,m)最短路径即为答案 def findRotateSteps(ring, key)::type ring: str:type key: str:rtype: intn,mlen(ring),len(key)mem [[False]*(m1) for _ in range(n)]mem[0][0]Truel [(0,0)]step 0while True:tmp []for i,j in l:if jm:return stepif ring[i]key[j]:if not mem[i][j1]:mem[i][j1]Truetmp.append((i,j1))continuefor nxt in [(i-1)%n,(i1)%n]:if not mem[nxt][j]:mem[nxt][j]Truetmp.append((nxt,j))step1 1/30 2808. 使循环数组所有元素相等的最少秒数 可以选择将每一位置的数变为左右两侧的数 对每一个数值x记录其依次出现的位置 如果要将所有数变为x 需要的最少次数为两个x的最远距离除以二 def minimumSeconds(nums)::type nums: List[int]:rtype: intfrom 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 heapqnlen(nums)ans [0]*nlow,up[],[]lows,ups0,0mod 10**97for i in range(n):x nums[i]-iif len(low)0 or -low[0]x:lowsxheapq.heappush(low,-x)if len(low)len(up)1:ups -low[0]heapq.heappush(up,-low[0])lows heapq.heappop(low)else:upsxheapq.heappush(up,x)if len(low)len(up):lows up[0]heapq.heappush(low,-up[0])ups - heapq.heappop(up)if (i1)%20: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) iaib -(jajb) 如果大于0则alice先选i 优先选 iaib大的石头 将石头两个人的价值相加后倒序排列 两人依次选取 def stoneGameVI(aliceValues, bobValues)::type aliceValues: List[int]:type bobValues: List[int]:rtype: intv [[ab,a,b] for a,b in zip(aliceValues,bobValues)]v.sort(reverseTrue)asum sum(value[1] for value in v[::2])bsum sum(value[2] for value in v[1::2])if asumbsum:return 1elif asumbsum:return 0else:return -1 2/3 1690. 石子游戏 VII 动态规划 先求出区间[i,i]的最大的得分差值 向外扩展 直至扩展到区间[0,n-1] def stoneGameVII(stones)::type stones: List[int]:rtype: intnlen(stones)s [0]*(n1)dp[[0]*n for _ in range(n)]for i in range(n):s[i1] s[i]stones[i]for i in range(n-2,-1,-1):for j in range(i1,n):dp[i][j] max(s[j1]-s[i1]-dp[i1][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: boolreturn n%4!0
