企业官网建设流程全解析

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

8/17 1563. 石子游戏 V

Alice 每次把区间 [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 n=len(stoneValue)s=[0]*(n+1)fori,xinenumerate(stoneValue):s[i+1]=s[i]+x@lru_cache(None)defdfs(i,j):ifi>=j:return0ans=0left=0right=s[j+1]-s[i]forkinrange(i,j):left+=stoneValue[k]right-=stoneValue[k]ifleft<right:ifans>=left*2:continuet=left+dfs(i,k)ift>ans:ans=telifleft>right:ifans>=right*2:breakt=right+dfs(k+1,j)ift>ans:ans=telse:t1=left+dfs(i,k)t2=right+dfs(k+1,j)t=t1ift1>t2elset2ift>ans:ans=treturnansreturndfs(0,n-1)

8/18 3471. 找出最大的几近缺失整数

几近缺失整数是恰好出现在一个长度为 k 的子数组中的数。
k=1 时，每个元素单独成段，答案是数组中只出现一次的最大值。
k=n 时，只有整个数组一个子数组，答案是数组最大值。
1<k<n 时，中间位置的数一定落在多个长度为 k 的窗口里，只有两端 nums[0] 和 nums[-1] 才可能只出现在一个窗口中；再检查它们是否在数组中只出现一次，取较大者。
都不存在则返回 -1。

deflargestInteger(nums,k):""" :type nums: List[int] :type k: int :rtype: int """fromcollectionsimportCounter n=len(nums)ifk==n:returnmax(nums)cnt=Counter(nums)ifk==1:ans=-1forx,cincnt.items():ifc==1andx>ans:ans=xreturnans ans=-1ifcnt[nums[0]]==1:ans=nums[0]ifcnt[nums[-1]]==1andnums[-1]>ans:ans=nums[-1]returnans

8/19 1386. 安排电影院座位

每排最多安排两个四人组，可选座位块为 2-5、4-7、6-9；1 和 10 不影响安排。
n 很大，只处理有预订的行，其余空行每行直接贡献 2。
用哈希表把每行预订座位压成状态。对有预订的行优先尝试互不重叠的左右两块，若都不能坐再尝试中间块。

defmaxNumberOfFamilies(n,reservedSeats):""" :type n: int :type reservedSeats: List[List[int]] :rtype: int """fromcollectionsimportdefaultdict d=defaultdict(int)forrow,seatinreservedSeats:d[row]|=1<<seat left=(1<<2)|(1<<3)|(1<<4)|(1<<5)mid=(1<<4)|(1<<5)|(1<<6)|(1<<7)right=(1<<6)|(1<<7)|(1<<8)|(1<<9)ans=(n-len(d))*2formaskind.values():l=(mask&left)==0r=(mask&right)==0ifl:ans+=1ifr:ans+=1ifnotlandnotrand(mask&mid)==0:ans+=1returnans

8/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)returnarr1

8/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 n=len(coins)deflcm(a,b):returna//gcd(a,b)*bdefcount(x):cnt=0formaskinrange(1,1<<n):v=1bits=0overflow=Falsefori,cinenumerate(coins):ifmask>>i&1:bits+=1v=lcm(v,c)ifv>x:overflow=Truebreakifoverflow:continueifbits&1:cnt+=x//velse:cnt-=x//vreturncnt lo=1hi=k*min(coins)whilelo<hi:mid=(lo+hi)//2ifcount(mid)>=k:hi=midelse:lo=mid+1returnlo

8/22 3622. 判断整除性

按需求判断 s记录各位数字总和 m记录各位数字之积

defcheckDivisibility(self,n):""" :type n: int :rtype: bool """tmp=n s,m=0,1whiletmp:s+=tmp%10m*=tmp%10tmp//=10returnn%(s+m)==0

8/23 1927. 求和游戏

Alice 要使左右两半数字和不相等，Bob 要使它们相等，双方最优。
问号个数为奇数时 Alice 走最后一步，总能改成不相等，必胜。
问号个数为偶数时，最优下每个问号对“可调差额”的贡献相当于 4.5。
设左半已填数字和为 s1、问号数为 c1，右半为 s2、c2，Bob 能扳平当且仅当 s1 - s2 == 9 * (c2 - c1) / 2。
否则 Alice 必胜。

defsumGame(num):""" :type num: str :rtype: bool """n=len(num)mid=n//2s1=s2=0c1=c2=0fori,chinenumerate(num):ifi<mid:ifch=="?":c1+=1else:s1+=ord(ch)-48else:ifch=="?":c2+=1else:s2+=ord(ch)-48return(c1+c2)%2==1ors1-s2!=9*(c2-c1)//2