力扣第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 = -inffor 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 defaultdictclass Solution:def maxDistance(self, s: str, k: int) -> int:sc = defaultdict(int)ans = 0for i in s:sc[i]+=1left = k# 计算k的使用情况def change(a,b):nonlocal leftd = min(a,b,left)left-=d  return abs(a-b)+2*dans = max(ans,change(sc["W"],sc["E"])+change(sc["N"],sc["S"]))return ans

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

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

灵神题目

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

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

from collections import defaultdictclass Solution:def maxDifference(self, s: str, k: int) -> int:# 使用一个滑动窗口，逐渐记录！# 只需记录在窗口中的最大的奇数-最大的偶数次，注意这个偶数不能为0ct = defaultdict(int)n = len(s)ans = -10 ** 5maxji, maxou = 0, 0for i in range(n):ct[s[i]] += 1# 注意这里还只是够了k-1if i < k-2:continue# 此时 i =2# 满足k的时候进行判断for j in range(i, n - 1):ct[s[j + 1]] += 1if  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]] += 1for j in range(i,n-1):ct[s[j+1]] -= 1if ct[s[j+1]] == 0:del ct[s[j+1]]# 回退,注意由于本来元素只有k-1个，所以这里对应的窗口的下标是i-k+2if k == 1:ct[s[i]] -= 1if ct[s[i]] == 0:del ct[s[i]]continuect[s[i-k+2]] -=1if 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 = -inffor x in range(5):for y in range(5):if y == x:continuecur_s = [0] * 5pre_s = [0] * 5min_s = [[inf, inf], [inf, inf]]left = 0for i, b in enumerate(s):cur_s[b] += 1r = i + 1while 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] & 1min_s[p][q] = min(min_s[p][q], pre_s[x] - pre_s[y])pre_s[s[left]] += 1left += 1if r >= k:ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1])return ans