力扣第435场周赛讲解

题目总览

奇偶频次间的最大差值I
K次修改后的最大曼哈顿距离
使数组包含目标值倍数的最少增量
奇偶频次间的最大差值II

题目详解

3442.奇偶频次间的最大差值I

思路分析：注意题目求解的是，奇数次字符的次数减去偶数次字符的次数，要求的是最大的！！！

我的思路：开始的时候，我没注意到实际上，我们只用让最大的奇数次减去最小的偶数次即可，而是冗余使用了两两之间进行比较

# 不成熟的代码
from collections import Counter
class Solution:
    def maxDifference(self, s: str) -> int:
        st = list(s)
        sst = list(set(st))
        newstr = Counter(st)
        ans = -inf
        for i in range(len(sst) - 1):
            for j in range(i + 1, len(sst)):
                if (newstr[sst[i]] + newstr[sst[j]]) % 2 == 1:
                    if newstr[sst[i]]%2==1:
                        ans = max(ans, (newstr[sst[i]] - newstr[sst[j]]))
                    else:
                        ans = max(ans, (newstr[sst[j]] - newstr[sst[i]]))
                    
        return ans

灵神的代码

class Solution:
    def maxDifference(self, s: str) -> int:
        cnt = Counter(s)
        max1 = max(c for c in cnt.values() if c % 2 == 1)
        min0 = min(c for c in cnt.values() if c % 2 == 0)
        return max1 - min0

3443.K次修改后的最大曼哈顿距离

思路分析：注意这题，我们应该考虑到，东西，南北各自进行处理，是相互同理的，总的处理的操作是使用贪心+逐一处理的！！因为要考虑到记录过程中的状态值

本人错误的思路：容易陷入，知道是使用贪心，但是对于贪心如何表达，表达不清楚，以及忘了考虑过程量

灵神思路：对于东西一对方向，我们只需对数量较少进行翻转，

如果 东a = 2,西b = 5
那么我们肯定会翻转 a,
如果翻转量为 d ,那么翻转之后的横坐标的绝对值就是 
b+d - (a-d) = b-a +2d,
当a>b的时候就是，a-b+2d,
总的来说就是  abs(a-b)+2d
并且 d = min(a,b,k)

from collections import defaultdict

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        sc = defaultdict(int)
        ans = 0
        for i in s:
            sc[i]+=1
            left = k
            # 计算k的使用情况
            def change(a,b):
                nonlocal left
                d = min(a,b,left)
                left-=d  
                return abs(a-b)+2*d
            ans = max(ans,change(sc["W"],sc["E"])+change(sc["N"],sc["S"]))
        return ans

3444. 使数组包含目标值倍数的最少增量

思路分析：题目较难，后续再来分析

灵神题目

3445.奇偶频次间的最大差值

思路分析：
开始只想用一个滑动窗口+枚举，发现只能过670/689测试用例

from collections import defaultdict

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        # 使用一个滑动窗口，逐渐记录！
        # 只需记录在窗口中的最大的奇数-最大的偶数次，注意这个偶数不能为0
        ct = defaultdict(int)
        n = len(s)
        ans = -10 ** 5
        maxji, maxou = 0, 0
        for i in range(n):
            ct[s[i]] += 1
            # 注意这里还只是够了k-1
            if i < k-2:
                continue
            # 此时 i =2
            # 满足k的时候进行判断
            for j in range(i, n - 1):
                ct[s[j + 1]] += 1
                if  any(c for c in ct.values() if c % 2 == 1) and  any(c for c in ct.values() if c % 2 == 0):
                    maxji = max(c for c in ct.values() if c % 2 == 1)
                    minou = min(c for c in ct.values() if c % 2 == 0)
                    ans = max(ans, maxji - minou)
                # ct[s[j + 1]] += 1
            for j in range(i,n-1):
                ct[s[j+1]] -= 1
                if ct[s[j+1]] == 0:
                    del ct[s[j+1]]
            # 回退,注意由于本来元素只有k-1个，所以这里对应的窗口的下标是i-k+2
            if k == 1:
                ct[s[i]] -= 1
                if ct[s[i]] == 0:
                    del ct[s[i]]
                continue
            ct[s[i-k+2]] -=1
            if ct[s[i-k+2]] == 0:
                del ct[s[i-k+2]]
        return ans

应该加上前缀和

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        s = list(map(int, s))
        ans = -inf
        for x in range(5):
            for y in range(5):
                if y == x:
                    continue
                cur_s = [0] * 5
                pre_s = [0] * 5
                min_s = [[inf, inf], [inf, inf]]
                left = 0
                for i, b in enumerate(s):
                    cur_s[b] += 1
                    r = i + 1
                    while r - left >= k and cur_s[x] > pre_s[x] and cur_s[y] > pre_s[y]:
                        p, q = pre_s[x] & 1, pre_s[y] & 1
                        min_s[p][q] = min(min_s[p][q], pre_s[x] - pre_s[y])
                        pre_s[s[left]] += 1
                        left += 1
                    if r >= k:
                        ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1])
        return ans