力扣 第473场周赛(A~D)

A:3726. 移除十进制表示中的所有零
简单题，转str后去掉所有0。

class Solution:
    def removeZeros(self, n: int) -> int:
        s=str(n)
        res=""
        for c in s:
            if c!='0':
                res+=c
        return int(res)

B:100855. 最大交替平方和

简单题，按照平方排序，前n//2个为负，后面的为正。

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        n=len(nums)
        for i in range(n):
            nums[i]*=nums[i]
        nums.sort()
        print(nums)
        res=-sum(nums[0:n//2])+sum(nums[(n//2):])
        return res

 

C:3728. 边界与内部和相等的稳定子数组

 第一个条件即为r-l+1>=3。

第二个条件即为c[l]==c[r]==s[l+1~r-1]，落实到代码即为c[l]==c[r] && c[l]+pre[l+1]==pre[r].

那么我们枚举右边，同时维护左边(c[l], c[l]+pre[l+1])的出现次数，即可在O(n)的时间复杂度内完成统计。

class Solution:
    def countStableSubarrays(self, c: List[int]) -> int:
        n=len(c)
        pre=[0]*(n+1)
        for i in range(1,n+1):
            pre[i]=pre[i-1]+c[i-1]
        d=defaultdict(int)
        ans=0
        # r-l+1>=3
        # c[l]==c[r]
        # c[l]+pre[l+1]==pre[r]
        for r in range(2, n):
            l = r - 2
            d[(c[l], pre[l+1] + c[l])] += 1
            ans += d[(c[r], pre[r])]
        return ans

D:3729. 统计有序数组中可被 K 整除的子数组数量

如果可重复的话，就是一个前缀和+哈希就搞定了，我们先做这一步，然后来考虑去重。

因为原数组是非降序的，那么就只有段内可能会导致重复计数。因为跨段比如2 2 2 3这么一个子数组，只可能有一个。

所以问题就变成了问长为L的段x,x,x,x,x,...,x有多少重复计数。

段内长为1的子数组有L个，长为2的子数组有L-1个，长为3的子数组有L-2个=>长为t的子数组有L-t+1个，我们应该记一次，所以我们就多记了L-t次。

此外，我们还需要满足(t*x)%k==0，令g=gcd(x,k)，x=x' * g，k=k' * g，x'和k'互质 => t*x'*g 是 k'*g的倍数（因为x'和k'互质），t是k’的倍数，令base=k/gcd(x,k)。

我们枚举t从base到q=L//base.每个加上L-t，可以用等差数列公式计算得q*L-base*(q+1)*q//2为多算的，减去即可。

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        #可重复
        total=0
        d=defaultdict(int)
        s=0
        d[s]+=1
        for x in nums:
            s=(s+x)%k
            total+=d[s]
            d[s]+=1

        #去重
        cnt=Counter(nums)
        minus=0
        for [x,L] in cnt.items():
            g=gcd(k,x)
            base=k//g
            q=L//base
            minus+=q*L-base*(q+1)*q//2
        return total-minus