VP 周赛 第 389 场周赛

第三题3085. 成为 K 特殊字符串需要删除的最少字符数

双指针优化$O(n)$

第三题做出来了但做法不优并且错的次数太多了。

  • 题目大意：给定一个字符串word和一个整数k，定义特殊字符串为满足|freq(word[i]) - freq(word[j])| <= k对于字符串中所有下标i和j都成立的字符串。其中，freq(x)表示字符x在word中的出现频率，|y|表示y的绝对值。要求计算使word成为k特殊字符串所需删除的字符的最小数量。

  • 实现思路：首先统计word中每个字符的出现频率，然后对频率进行排序。接着遍历频率列表，从最大的频率开始，逐步减少频率，直到满足特殊字符串的条件。在减少频率的过程中，利用一个指针指向频率列表中的当前位置，不断向前移动，更新需要删除的字符数量。最终得到使word成为k特殊字符串所需删除的最小字符数量。

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        ans = 2e9
        cnt = sorted(Counter(word).values())

        numFre = len(cnt)-1
        delCnt = len(word)
        right = numFre
        for cur in range(numFre, -1, -1):
            delCnt-=cnt[cur]
            maxFre = cnt[cur]+k
            while right>cur and cnt[right]>maxFre:
                delCnt+=cnt[right]
                right-=1
            ans = min(ans, delCnt-(numFre-right)*maxFre)
        return ans

第四题3086. 拾起 K 个 1 需要的最少行动次数

题目大意：给定一个二进制数组nums，长度为n，以及一个正整数k和非负整数maxChanges。Alice在一个游戏中需要从nums中拾起k个1，游戏开始时，Alice可以选择任意位置站立。Alice可以执行两种行动：一是将一个0改为1，次数不超过maxChanges；二是交换相邻位置的1和0。返回Alice拾取k个1所需的最少行动次数。

实现思路：首先，统计nums中1的位置，同时记录每个1的前缀和。然后确定最多可以拾取的1的个数，即为maxChanges和当前1的个数的最小值。如果最大变化次数maxChanges足够多，那么不需要交换1的位置，直接计算需要变化的次数即可；否则，利用二分搜索确定需要交换的1的位置，计算交换和变化的次数。最终返回行动次数。

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        pos = []
        n=len(nums)
        c=0
        for i, v in enumerate(nums):
            if not v:
                continue
            pos.append(i)
            if c==3:
                continue
            c=max(c, 1)
            if i>0 and nums[i]==nums[i-1]:
                c = max(2, c)
            if i>1 and nums[i]==nums[i-1] and nums[i]==nums[i-2]:
                c = max(3, c)

        c = min(c, k)

        if maxChanges>=k-c:
            return max(0, (k-c)*2)+max(0, c-1)
        
        n = len(pos)
        preSum = list(accumulate(pos, initial = 0))
        ret = inf

        rest = k-maxChanges

        for right in range(rest, n+1):
            left = right-rest
            i=left+right>>1

            s1 = pos[i]*(i-left) - (preSum[i]-preSum[left])
            s2 = preSum[right]-preSum[i]-pos[i]*(right-i)

            ret = min(ret, s1+s2)
        return ret+maxChanges*2