记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录8/3 1406. 石子游戏 III8/4 3731. 找出缺失的元素8/5 3310. 移除可疑的方法8/6 3345. 最小可整除数位乘积 I8/7 3348. 最小可整除数位乘积 II8/8 3302. 字典序最小的合法序列8/9 1140. 石子游戏 II8/3 1406. 石子游戏 III双方每次可从剩余石子堆前端取 1、2 或 3 堆都采取最优策略。用 dp[i] 表示从下标 i 开始当前选手相对对手能多得的最大分数差。转移为枚举取 k1…3 堆得分为这 k 堆之和减去对方从 ik 出发的最优差值。最终看 dp[0]大于 0 为 Alice小于 0 为 Bob等于 0 为 Tie。defstoneGameIII(stoneValue): :type stoneValue: List[int] :rtype: str nlen(stoneValue)dp0dp1dp20foriinrange(n-1,-1,-1):beststoneValue[i]-dp0ifi1n:bestmax(best,stoneValue[i]stoneValue[i1]-dp1)ifi2n:bestmax(best,stoneValue[i]stoneValue[i1]stoneValue[i2]-dp2)dp0,dp1,dp2best,dp0,dp1ifdp00:returnAliceifdp00:returnBobreturnTie8/4 3731. 找出缺失的元素找到最小值和最大值 便利所有元素 如果不在数组中就加入列表中deffindMissingElements(nums): :type nums: List[int] :rtype: List[int] minv,maxvmin(nums),max(nums)missing[]sset(nums)foriinrange(minv,maxv1):ifinotins:missing.append(i)returnmissing8/5 3310. 移除可疑的方法把调用关系建成有向图。从有 bug 的方法 k 出发做 BFS/DFS标记所有可达方法为可疑。若存在非可疑方法调用了可疑方法则整组不能删除返回全部方法。否则删除所有可疑方法返回剩余方法。defremainingMethods(n,k,invocations): :type n: int :type k: int :type invocations: List[List[int]] :rtype: List[int] fromcollectionsimportdeque g[[]for_inrange(n)]fora,bininvocations:g[a].append(b)suspicious[False]*n qdeque([k])suspicious[k]Truewhileq:uq.popleft()forving[u]:ifnotsuspicious[v]:suspicious[v]Trueq.append(v)ans[]foruinrange(n):ifsuspicious[u]:continueforving[u]:ifsuspicious[v]:returnlist(range(n))ans.append(u)returnans8/6 3345. 最小可整除数位乘积 I依次增加n 知道找到满足的数defsmallestNumber(n,t): :type n: int :type t: int :rtype: int defcheck(num):v1whilenum0:v*num%10num//10returnv%t0whilenotcheck(n):n1returnn8/7 3348. 最小可整除数位乘积 II答案要求无 0且数位乘积能被 t 整除因此 t 的质因子只能是 2、3、5、7否则无解。把 t 分解成这些质因子后用尽量少的数位 2…9 去覆盖优先拼成 8、9、6、4。若最短覆盖长度已超过 num直接返回该最短数。否则尽量保持与 num 同长度从右往左找第一个可增大的位置增大后用 1 填充多余空位再接上覆盖剩余质因子的最小后缀。若同长度无解则构造长度为 len(num)1 的数前面补 1后面接最短覆盖数位。defsmallestNumber(num,t): :type num: str :type t: int :rtype: str fromcollectionsimportCounter FACTOR{0:Counter(),1:Counter(),2:Counter([2]),3:Counter([3]),4:Counter([2,2]),5:Counter([5]),6:Counter([2,3]),7:Counter([7]),8:Counter([2,2,2]),9:Counter([3,3]),}defget_prime_count(x):cntCounter()forpin(2,3,5,7):whilex%p0:x//p cnt[p]1returncnt,x1defget_factor_count(cnt):c8,rem2divmod(cnt[2],3)c9,c3divmod(cnt[3],2)c4,c2divmod(rem2,2)c60ifc21andc31:c2c30c61ifc31andc41:c2,c6,c3,c41,1,0,0return{2:c2,3:c3,4:c4,5:cnt[5],6:c6,7:cnt[7],8:c8,9:c9,}defbuild(factors):return.join(d*factors[d]fordin23456789)need,okget_prime_count(t)ifnotok:return-1factorsget_factor_count(need)ifsum(factors.values())len(num):returnbuild(factors)prefixsum((FACTOR[int(c)]forcinnum),Counter())first_zeronext((ifori,cinenumerate(num)ifc0),len(num))iffirst_zerolen(num)andneedprefix:returnnumforiinrange(len(num)-1,-1,-1):dint(num[i])prefix-FACTOR[d]spacelen(num)-1-iififirst_zero:continueforbiggerinrange(d1,10):remainget_factor_count(need-prefix-FACTOR[bigger])ifsum(remain.values())space:onesspace-sum(remain.values())returnnum[:i]str(bigger)1*onesbuild(remain)factorsget_factor_count(need)return1*(len(num)1-sum(factors.values()))build(factors)8/8 3302. 字典序最小的合法序列要在 word1 中找一组严格递增下标使取出的字符与 word2 至多有一处不同并要求下标序列字典序最小。先从右往左预处理 last[j]匹配 word2[j…] 时能取到的最右起点位置。再从左往右贪心字符相同则立刻取当前下标若不同且还没用过那一次修改并保证后面仍能匹配完已是最后一位或当前位置早于 last[j1]就在这里使用修改。若最终匹配完 word2返回下标序列否则返回空数组。defvalidSequence(word1,word2): :type word1: str :type word2: str :rtype: List[int] n,mlen(word1),len(word2)last[-1]*m i,jn-1,m-1whilei0andj0:ifword1[i]word2[j]:last[j]i j-1i-1ans[]can_skipTruej0fori,cinenumerate(word1):ifjm:breakifcword2[j]:ans.append(i)j1elifcan_skipand(jm-1orilast[j1]):can_skipFalseans.append(i)j1returnansifjmelse[]8/9 1140. 石子游戏 IIs[i]记录后缀和sum(piles[i:])如果i2*mn 可以把后面的都拿了遍历所有可能的x 找到后一个步最少的可能性 得到此时最大值mem记忆(i,m)的结果defstoneGameII(piles): :type piles: List[int] :rtype: int spiles[:]nlen(piles)foriinrange(n-2,-1,-1):s[i]s[i1]mem{}defdfs(i,m):if(i,m)inmem:returnmem[(i,m)]ifi2*mn:mem[(i,m)]s[i]returns[i]anss[i]-min(dfs(ix,max(m,x))forxinrange(1,m*21))mem[(i,m)]ansreturnansreturndfs(0,1) 
长河君 · 2026/8/11 11:35:56 · 阅读 1.2k LeetCode 每日一题 2026/8/3-2026/8/9
记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录8/3 1406. 石子游戏 III8/4 3731. 找出缺失的元素8/5 3310. 移除可疑的方法8/6 3345. 最小可整除数位乘积 I8/7 3348. 最小可整除数位乘积 II8/8 3302. 字典序最小的合法序列8/9 1140. 石子游戏 II8/3 1406. 石子游戏 III双方每次可从剩余石子堆前端取 1、2 或 3 堆都采取最优策略。用 dp[i] 表示从下标 i 开始当前选手相对对手能多得的最大分数差。转移为枚举取 k1…3 堆得分为这 k 堆之和减去对方从 ik 出发的最优差值。最终看 dp[0]大于 0 为 Alice小于 0 为 Bob等于 0 为 Tie。defstoneGameIII(stoneValue): :type stoneValue: List[int] :rtype: str nlen(stoneValue)dp0dp1dp20foriinrange(n-1,-1,-1):beststoneValue[i]-dp0ifi1n:bestmax(best,stoneValue[i]stoneValue[i1]-dp1)ifi2n:bestmax(best,stoneValue[i]stoneValue[i1]stoneValue[i2]-dp2)dp0,dp1,dp2best,dp0,dp1ifdp00:returnAliceifdp00:returnBobreturnTie8/4 3731. 找出缺失的元素找到最小值和最大值 便利所有元素 如果不在数组中就加入列表中deffindMissingElements(nums): :type nums: List[int] :rtype: List[int] minv,maxvmin(nums),max(nums)missing[]sset(nums)foriinrange(minv,maxv1):ifinotins:missing.append(i)returnmissing8/5 3310. 移除可疑的方法把调用关系建成有向图。从有 bug 的方法 k 出发做 BFS/DFS标记所有可达方法为可疑。若存在非可疑方法调用了可疑方法则整组不能删除返回全部方法。否则删除所有可疑方法返回剩余方法。defremainingMethods(n,k,invocations): :type n: int :type k: int :type invocations: List[List[int]] :rtype: List[int] fromcollectionsimportdeque g[[]for_inrange(n)]fora,bininvocations:g[a].append(b)suspicious[False]*n qdeque([k])suspicious[k]Truewhileq:uq.popleft()forving[u]:ifnotsuspicious[v]:suspicious[v]Trueq.append(v)ans[]foruinrange(n):ifsuspicious[u]:continueforving[u]:ifsuspicious[v]:returnlist(range(n))ans.append(u)returnans8/6 3345. 最小可整除数位乘积 I依次增加n 知道找到满足的数defsmallestNumber(n,t): :type n: int :type t: int :rtype: int defcheck(num):v1whilenum0:v*num%10num//10returnv%t0whilenotcheck(n):n1returnn8/7 3348. 最小可整除数位乘积 II答案要求无 0且数位乘积能被 t 整除因此 t 的质因子只能是 2、3、5、7否则无解。把 t 分解成这些质因子后用尽量少的数位 2…9 去覆盖优先拼成 8、9、6、4。若最短覆盖长度已超过 num直接返回该最短数。否则尽量保持与 num 同长度从右往左找第一个可增大的位置增大后用 1 填充多余空位再接上覆盖剩余质因子的最小后缀。若同长度无解则构造长度为 len(num)1 的数前面补 1后面接最短覆盖数位。defsmallestNumber(num,t): :type num: str :type t: int :rtype: str fromcollectionsimportCounter FACTOR{0:Counter(),1:Counter(),2:Counter([2]),3:Counter([3]),4:Counter([2,2]),5:Counter([5]),6:Counter([2,3]),7:Counter([7]),8:Counter([2,2,2]),9:Counter([3,3]),}defget_prime_count(x):cntCounter()forpin(2,3,5,7):whilex%p0:x//p cnt[p]1returncnt,x1defget_factor_count(cnt):c8,rem2divmod(cnt[2],3)c9,c3divmod(cnt[3],2)c4,c2divmod(rem2,2)c60ifc21andc31:c2c30c61ifc31andc41:c2,c6,c3,c41,1,0,0return{2:c2,3:c3,4:c4,5:cnt[5],6:c6,7:cnt[7],8:c8,9:c9,}defbuild(factors):return.join(d*factors[d]fordin23456789)need,okget_prime_count(t)ifnotok:return-1factorsget_factor_count(need)ifsum(factors.values())len(num):returnbuild(factors)prefixsum((FACTOR[int(c)]forcinnum),Counter())first_zeronext((ifori,cinenumerate(num)ifc0),len(num))iffirst_zerolen(num)andneedprefix:returnnumforiinrange(len(num)-1,-1,-1):dint(num[i])prefix-FACTOR[d]spacelen(num)-1-iififirst_zero:continueforbiggerinrange(d1,10):remainget_factor_count(need-prefix-FACTOR[bigger])ifsum(remain.values())space:onesspace-sum(remain.values())returnnum[:i]str(bigger)1*onesbuild(remain)factorsget_factor_count(need)return1*(len(num)1-sum(factors.values()))build(factors)8/8 3302. 字典序最小的合法序列要在 word1 中找一组严格递增下标使取出的字符与 word2 至多有一处不同并要求下标序列字典序最小。先从右往左预处理 last[j]匹配 word2[j…] 时能取到的最右起点位置。再从左往右贪心字符相同则立刻取当前下标若不同且还没用过那一次修改并保证后面仍能匹配完已是最后一位或当前位置早于 last[j1]就在这里使用修改。若最终匹配完 word2返回下标序列否则返回空数组。defvalidSequence(word1,word2): :type word1: str :type word2: str :rtype: List[int] n,mlen(word1),len(word2)last[-1]*m i,jn-1,m-1whilei0andj0:ifword1[i]word2[j]:last[j]i j-1i-1ans[]can_skipTruej0fori,cinenumerate(word1):ifjm:breakifcword2[j]:ans.append(i)j1elifcan_skipand(jm-1orilast[j1]):can_skipFalseans.append(i)j1returnansifjmelse[]8/9 1140. 石子游戏 IIs[i]记录后缀和sum(piles[i:])如果i2*mn 可以把后面的都拿了遍历所有可能的x 找到后一个步最少的可能性 得到此时最大值mem记忆(i,m)的结果defstoneGameII(piles): :type piles: List[int] :rtype: int spiles[:]nlen(piles)foriinrange(n-2,-1,-1):s[i]s[i1]mem{}defdfs(i,m):if(i,m)inmem:returnmem[(i,m)]ifi2*mn:mem[(i,m)]s[i]returns[i]anss[i]-min(dfs(ix,max(m,x))forxinrange(1,m*21))mem[(i,m)]ansreturnansreturndfs(0,1)