记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录10/12 2897. 对数组执行操作使平方和最大10/13 3727. 最大交替平方和10/14 3723. 数位平方和的最大值10/15 2913. 子数组不同元素数目的平方和 I10/16 2916. 子数组不同元素数目的平方和 II10/17 3551. 数位和排序需要的最小交换次数10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数10/12 2897. 对数组执行操作使平方和最大AND/OR 操作不会增加或减少某一位上 1 的总数只会把某个数的 1 挪到另一个数上。平方和要最大应该把 1 尽量集中到少数几个大数上因为把一位从小数挪到大数平方和会变大。先统计每一位上有多少个 1再贪心拼出 k 个数每次把还没用完的位都放进当前这个数让它尽量大然后把平方加进答案。defmaxSum(nums,k): :type nums: List[int] :type k: int :rtype: int mod10**97cnt[0]*31forxinnums:foriinrange(31):ifxi1:cnt[i]1ans0for_inrange(k):x0foriinrange(31):ifcnt[i]:x|1i cnt[i]-1ans(ansx*x)%modreturnans10/13 3727. 最大交替平方和偶数位取正、奇数位取负平方只和绝对值有关。将绝对值大的放到偶数位绝对值小的放到奇数位。先取绝对值排序较小的一半减去平方较大的一半加上平方。defmaxAlternatingSum(nums): :type nums: List[int] :rtype: int ans0nlen(nums)l[abs(x)forxinnums]l.sort()foriinrange(n):ifin//2:ans-l[i]**2else:ansl[i]**2returnans10/14 3723. 数位平方和的最大值要凑恰好 num 位、数位和恰好是 sum 的数让各位数字的平方和最大平方和一样时取数值最大的那个。平方和固定时数字越集中越大所以尽量多用 9剩下不足 9 的部分单独放一位。同分时要数值最大就把这些 9 放在最高位余数紧跟其后剩下的位补 0。如果 sum 比 9*num 还大凑不出来返回空串。defmaxSumOfSquares(num,sum): :type num: int :type sum: int :rtype: str ifnum*9sum:returnk,sdivmod(sum,9)ans9*kifs:ansstr(s)returnans0*(num-len(ans))10/15 2913. 子数组不同元素数目的平方和 I每个子数组都要算一次「里面有多少个不同的数」再把这个数平方后全部加起来。数组很短枚举左端点再从左往右把右端点一格一格延长。用集合记下当前这段出现过的数集合大小就是不同元素个数平方后加进答案。defsumCounts(nums): :type nums: List[int] :rtype: int nlen(nums)ans0foriinrange(n):seenset()forjinrange(i,n):seen.add(nums[j])anslen(seen)*len(seen)returnans10/16 2916. 子数组不同元素数目的平方和 II还是把每个子数组的不同元素个数平方后加起来但数组很长不能一段段枚举。固定右端点从左往右扫记下每个左端点到当前右端点这段里有多少个不同的数。新来的数只对「上次出现位置之后」的那些左端点是新元素这些段的不同个数都加 1。一段数每个都加 1 时平方和增加 2×原来的和 这段长度。用线段树做区间加 1 并维护平方和每扫完一个右端点就加进答案最后对 10^97 取模。defsumCounts(nums): :type nums: List[int] :rtype: int mod10**97nlen(nums)sm[0]*(4*n)sq[0]*(4*n)lz[0]*(4*n)defapply(p,l,r,v):lengthr-l1sq[p](sq[p]2*v*sm[p]v*v*length)%mod sm[p](sm[p]v*length)%mod lz[p]vdefpush(p,l,r):iflz[p]andlr:m(lr)//2apply(p*2,l,m,lz[p])apply(p*21,m1,r,lz[p])lz[p]0defupdate(p,l,r,ql,qr):ifqllandrqr:apply(p,l,r,1)returnpush(p,l,r)m(lr)//2ifqlm:update(p*2,l,m,ql,qr)ifqrm:update(p*21,m1,r,ql,qr)sm[p](sm[p*2]sm[p*21])%mod sq[p](sq[p*2]sq[p*21])%mod last{}ans0forr,xinenumerate(nums):update(1,0,n-1,last.get(x,-1)1,r)last[x]r ans(anssq[1])%modreturnans10/17 3551. 数位和排序需要的最小交换次数数位和更小的排前面数位和相同则数字更小的排前面。先按这个规则排出目标顺序再看每个数现在在哪、应该去哪。这些「当前位置指向目标位置」会连成若干个圈。一个圈里有 k 个数最少交换 k-1 次就能各归其位总次数就是 n 减去圈的个数。defminSwaps(nums): :type nums: List[int] :rtype: int defdigit_sum(x):s0whilex:sx%10x//10returns nlen(nums)ordersorted((digit_sum(x),x)forxinnums)pos{x:ifori,(_,x)inenumerate(order)}vis[False]*n ansnforiinrange(n):ifvis[i]:continueans-1jiwhilenotvis[j]:vis[j]Truejpos[nums[j]]returnans10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数按数组顺序依次插入空的二叉搜索树第一个数一定是根根一换树就变了所以根不能动。比根小的都进左子树比根大的都进右子树。左右两边各自的先后顺序决定子树长什么样两边之间可以任意穿插。左边 m 个数、右边 n 个数穿插方式是从 mn 个位置里选 m 个给左边。左右再各自按同样规则计算乘起来就是总方案。题目不要原数组本身最后减 1并对 10^97 取模。defnumOfWays(nums): :type nums: List[int] :rtype: int importsys sys.setrecursionlimit(10000)mod10**97nlen(nums)c[[0]*nfor_inrange(n)]c[0][0]1foriinrange(1,n):c[i][0]1forjinrange(1,i1):c[i][j](c[i-1][j]c[i-1][j-1])%moddefdfs(a):iflen(a)2:return1left[xforxinaifxa[0]]right[xforxinaifxa[0]]returnc[len(left)len(right)][len(left)]*dfs(left)%mod*dfs(right)%modreturn(dfs(nums)-1)%mod