记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录8/10 1510. 石子游戏 IV8/11 2996. 大于等于顺序前缀和的最小缺失整数8/12 2958. 最多 K 个重复元素的最长子数组8/13 2213. 由单个字符重复的最长子字符串8/14 3090. 每个字符最多出现两次的最长子字符串8/158/168/10 1510. 石子游戏 IV双方轮流从 n 个石子中拿走平方数个Alice 先手不能行动者输。用 dp[i] 表示还剩 i 个石子时当前选手是否必胜。转移若存在某个平方数 x使得 dp[i-x] 为败则当前选手必胜。最终返回 dp[n]。defwinnerSquareGame(n): :type n: int :rtype: bool dp[False]*(n1)foriinrange(1,n1):k1whilek*ki:ifnotdp[i-k*k]:dp[i]Truebreakk1returndp[n]8/11 2996. 大于等于顺序前缀和的最小缺失整数从头遍历 找到顺序前缀并记录和顺序前缀结束后判断和是否出现过 若出现1defmissingInteger(nums): :type nums: List[int] :rtype: int ansnums[0]foriinrange(1,len(nums)):ifnums[i]-nums[i-1]1:ansnums[i]else:breaksset(nums)whileansins:ans1returnans8/12 2958. 最多 K 个重复元素的最长子数组滑动窗口[l,r] cnt[num]记录 num出现的次数r一直往右移动 将nums[r]加入cnt 如果cnt[nums[r]] k 则将nums[l]从cnt中移除 并左移l如果cnt[nums[r]] k 则更新max_lengthdefmaxSubarrayLength(nums,k): :type nums: List[int] :type k: int :rtype: int fromcollectionsimportdefaultdict left0right0max_length0cntdefaultdict(int)whilerightlen(nums):cnt[nums[right]]1whilecnt[nums[right]]k:cnt[nums[left]]-1left1max_lengthmax(max_length,right-left1)right1returnmax_length8/13 2213. 由单个字符重复的最长子字符串每次单点改字符后要求整串中最长连续相同字符的长度。用线段树维护每个区间的左端连续长度 lmx、右端连续长度 rmx、区间内最长连续长度 mx。合并左右子区间时若左区间右端字符等于右区间左端字符则可把左后缀和右前缀拼起来更新 mx若左区间整段相同lmx 还要加上右前缀若右区间整段相同rmx 还要加上左后缀。每次修改叶子后自底向上 pushup根节点的 mx 就是当前答案。deflongestRepeating(s,queryCharacters,queryIndices): :type s: str :type queryCharacters: str :type queryIndices: List[int] :rtype: List[int] nlen(s)charslist(s)lmx[0]*(n*4)rmx[0]*(n*4)mx[0]*(n*4)left[0]*(n*4)right[0]*(n*4)defpushup(u):ls,rsu1,u1|1aright[ls]-left[ls]1bright[rs]-left[rs]1lmx[u]lmx[ls]rmx[u]rmx[rs]mx[u]mx[ls]ifmx[ls]mx[rs]elsemx[rs]ifchars[right[ls]-1]chars[left[rs]-1]:iflmx[ls]a:lmx[u]lmx[rs]ifrmx[rs]b:rmx[u]rmx[ls]crossrmx[ls]lmx[rs]ifcrossmx[u]:mx[u]crossdefbuild(u,l,r):left[u]l right[u]riflr:lmx[u]rmx[u]mx[u]1returnmid(lr)1build(u1,l,mid)build(u1|1,mid1,r)pushup(u)defmodify(u,x,v):ifleft[u]right[u]:chars[x-1]vreturnmid(left[u]right[u])1ifxmid:modify(u1,x,v)else:modify(u1|1,x,v)pushup(u)build(1,1,n)ans[]forx,vinzip(queryIndices,queryCharacters):modify(1,x1,v)ans.append(mx[1])returnans8/14 3090. 每个字符最多出现两次的最长子字符串滑动窗口 cnt记录每个字符出现的次数如果当前字符出现的次数大于2则移动左指针直到当前字符出现的次数小于等于2defmaximumLengthSubstring(s): :type s: str :rtype: int l,r0,0res0cntdefaultdict(int)whilerlen(s):cnt[s[r]]1whilecnt[s[r]]2:cnt[s[l]]-1l1resmax(res,r-l1)r1returnres8/158/16