记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录8/17 1563. 石子游戏 V8/18 3471. 找出最大的几近缺失整数8/19 1386. 安排电影院座位8/20 3069. 将元素分配到两个数组中 I8/21 3116. 单面值组合的第 K 小金额8/22 3622. 判断整除性8/23 1927. 求和游戏8/17 1563. 石子游戏 VAlice 每次把区间 [i,j] 从 k 处分成左右两段Bob 丢掉总和更大的那一段Alice 得到留下那段的总和并继续在留下的区间上游戏。用 dfs(i,j) 表示 Alice 在区间 [i,j] 能得到的最大分数。只剩一块石子时无法分割返回 0。预处理前缀和后枚举分割点左和小则只能留左边得分为 左和 dfs(i,k)右和小则只能留右边两段相等时取两边的更优结果。defstoneGameV(stoneValue): :type stoneValue: List[int] :rtype: int fromfunctoolsimportlru_cache nlen(stoneValue)s[0]*(n1)fori,xinenumerate(stoneValue):s[i1]s[i]xlru_cache(None)defdfs(i,j):ifij:return0ans0left0rights[j1]-s[i]forkinrange(i,j):leftstoneValue[k]right-stoneValue[k]ifleftright:ifansleft*2:continuetleftdfs(i,k)iftans:anstelifleftright:ifansright*2:breaktrightdfs(k1,j)iftans:anstelse:t1leftdfs(i,k)t2rightdfs(k1,j)tt1ift1t2elset2iftans:anstreturnansreturndfs(0,n-1)8/18 3471. 找出最大的几近缺失整数几近缺失整数是恰好出现在一个长度为 k 的子数组中的数。k1 时每个元素单独成段答案是数组中只出现一次的最大值。kn 时只有整个数组一个子数组答案是数组最大值。1kn 时中间位置的数一定落在多个长度为 k 的窗口里只有两端 nums[0] 和 nums[-1] 才可能只出现在一个窗口中再检查它们是否在数组中只出现一次取较大者。都不存在则返回 -1。deflargestInteger(nums,k): :type nums: List[int] :type k: int :rtype: int fromcollectionsimportCounter nlen(nums)ifkn:returnmax(nums)cntCounter(nums)ifk1:ans-1forx,cincnt.items():ifc1andxans:ansxreturnans ans-1ifcnt[nums[0]]1:ansnums[0]ifcnt[nums[-1]]1andnums[-1]ans:ansnums[-1]returnans8/19 1386. 安排电影院座位每排最多安排两个四人组可选座位块为 2-5、4-7、6-91 和 10 不影响安排。n 很大只处理有预订的行其余空行每行直接贡献 2。用哈希表把每行预订座位压成状态。对有预订的行优先尝试互不重叠的左右两块若都不能坐再尝试中间块。defmaxNumberOfFamilies(n,reservedSeats): :type n: int :type reservedSeats: List[List[int]] :rtype: int fromcollectionsimportdefaultdict ddefaultdict(int)forrow,seatinreservedSeats:d[row]|1seat left(12)|(13)|(14)|(15)mid(14)|(15)|(16)|(17)right(16)|(17)|(18)|(19)ans(n-len(d))*2formaskind.values():l(maskleft)0r(maskright)0ifl:ans1ifr:ans1ifnotlandnotrand(maskmid)0:ans1returnans8/20 3069. 将元素分配到两个数组中 I按照规则分配defresultArray(nums): :type nums: List[int] :rtype: List[int] arr1,arr2[nums[0]],[nums[1]]fornuminnums[2:]:ifarr1[-1]arr2[-1]:arr1.append(num)else:arr2.append(num)arr1.extend(arr2)returnarr18/21 3116. 单面值组合的第 K 小金额每种面值可以无限使用但不能混用不同面值能组成的金额就是各 coins[i] 的倍数。答案单调小于等于 x 的合法金额个数随 x 增大不减二分最小的 x 使个数 k。个数用容斥计算枚举 coins 的非空子集奇数个面值加上 x/lcm偶数个减去 x/lcm避免公共倍数被重复统计。deffindKthSmallest(coins,k): :type coins: List[int] :type k: int :rtype: int frommathimportgcd nlen(coins)deflcm(a,b):returna//gcd(a,b)*bdefcount(x):cnt0formaskinrange(1,1n):v1bits0overflowFalsefori,cinenumerate(coins):ifmaski1:bits1vlcm(v,c)ifvx:overflowTruebreakifoverflow:continueifbits1:cntx//velse:cnt-x//vreturncnt lo1hik*min(coins)whilelohi:mid(lohi)//2ifcount(mid)k:himidelse:lomid1returnlo8/22 3622. 判断整除性按需求判断 s记录各位数字总和 m记录各位数字之积defcheckDivisibility(self,n): :type n: int :rtype: bool tmpn s,m0,1whiletmp:stmp%10m*tmp%10tmp//10returnn%(sm)08/23 1927. 求和游戏Alice 要使左右两半数字和不相等Bob 要使它们相等双方最优。问号个数为奇数时 Alice 走最后一步总能改成不相等必胜。问号个数为偶数时最优下每个问号对“可调差额”的贡献相当于 4.5。设左半已填数字和为 s1、问号数为 c1右半为 s2、c2Bob 能扳平当且仅当 s1 - s2 9 * (c2 - c1) / 2。否则 Alice 必胜。defsumGame(num): :type num: str :rtype: bool nlen(num)midn//2s1s20c1c20fori,chinenumerate(num):ifimid:ifch?:c11else:s1ord(ch)-48else:ifch?:c21else:s2ord(ch)-48return(c1c2)%21ors1-s2!9*(c2-c1)//2