网站注册哪个好,教育平台网站,erp教学零基础入门,ppt素材大全免费图片文章目录 题目总览题目详解3442.奇偶频次间的最大差值I3443.K次修改后的最大曼哈顿距离3444. 使数组包含目标值倍数的最少增量3445.奇偶频次间的最大差值 题目总览
奇偶频次间的最大差值I K次修改后的最大曼哈顿距离 使数组包含目标值倍数的最少增量 奇偶频次间的最大差值II
… 文章目录 题目总览题目详解3442.奇偶频次间的最大差值I3443.K次修改后的最大曼哈顿距离3444. 使数组包含目标值倍数的最少增量3445.奇偶频次间的最大差值 题目总览
奇偶频次间的最大差值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]]%21: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 - min03443.K次修改后的最大曼哈顿距离 思路分析注意这题我们应该考虑到东西南北各自进行处理是相互同理的总的处理的操作是使用贪心逐一处理的因为要考虑到记录过程中的状态值 本人错误的思路容易陷入知道是使用贪心但是对于贪心如何表达表达不清楚以及忘了考虑过程量 灵神思路对于东西一对方向我们只需对数量较少进行翻转 如果 东a 2,西b 5
那么我们肯定会翻转 a,
如果翻转量为 d ,那么翻转之后的横坐标的绝对值就是
bd - (a-d) b-a 2d,
当ab的时候就是a-b2d,
总的来说就是 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[j1]] - 1if ct[s[j1]] 0:del ct[s[j1]]# 回退,注意由于本来元素只有k-1个所以这里对应的窗口的下标是i-k2if k 1:ct[s[i]] - 1if ct[s[i]] 0:del ct[s[i]]continuect[s[i-k2]] -1if ct[s[i-k2]] 0:del ct[s[i-k2]]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
