前缀和算法

算法总览

题目

1371.每个元音包含偶数次的最长子字符串

1371.每个元音包含偶数次的最长子字符串

参考博主的讲解

思路分析：就是得使用前缀和记录情况，dp[i][j]表示s[0] 到s[i] 中，j出现的次数

前缀和+剪枝

class Solution:def findTheLongestSubstring(self, s: str) -> int:# 使用字典将元音映射为数字，方便后续的记录i_mapper = {"a": 0,"e": 1,"i": 2,"o": 3,"u": 4}n = len(s)# pre[i][j]表示s[0] 到 s[i] 之间字符j所出现的次数pre = [[0] * 5 for _ in range(n)]# prefor i in range(n):for j in range(5):# 注意这里其实没有对i=0进行处理，因为-1在python中表示最后一个元素，所以不会越界报错if s[i] in i_mapper and i_mapper[s[i]] == j:pre[i][j] = pre[i - 1][j] + 1else:pre[i][j] = pre[i - 1][j]# check(l,r)表示查询s[l]到s[r]中的情况def check(l, r):for i in range(5):# 特别处理s[l]的情况，不然就是 pre[r][i] - pre[l-1][i]，这个时候就得判断l==0的情况if s[l] in i_mapper and i == i_mapper[s[l]]: cnt = 1else: cnt = 0if (pre[r][i] - pre[l][i] + cnt) % 2 != 0: return Falsereturn True# 由于是剪枝，i从最长的子序列的长度对应的末尾的下标开始计算for i in range(n - 1, -1, -1):# j表示长度为i的子序列的开始的下标for j in range(n - i):if check(j, i + j):return i + 1return 0

前缀和+状态压缩

class Solution:def findTheLongestSubstring(self, s: str) -> int:mapper = {"a": 1,"e": 2,"i": 4,"o": 8,"u": 16}# seen使用哈希表存储每一个状态组合所第一次出现的下标，最多就是2^5就是32种情况seen = {0: -1}# res 用于记录更新答案，cur用于计算当前的奇偶组合的值res = cur = 0for i in range(len(s)):if s[i] in mapper:cur ^= mapper.get(s[i])# 全部奇偶性都相同，相减一定都是偶数if cur in seen:res = max(res, i - seen.get(cur))else:seen[cur] = ireturn res

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:continue#cur_s 记录当前0,1,2,3,4出现的次数，pre_s则是先前的情况# cur_s是维护0-i的情况，pre_s是维护0-left的情况cur_s = [0] * 5pre_s = [0] * 5# min_s = [[inf, inf], [inf, inf]]left = 0for i, v in enumerate(s):cur_s[v] += 1r = i + 1# 一直在维护左边界的情况，r-left>=kwhile r - left >= k and cur_s[x] > pre_s[x] and cur_s[y] > pre_s[y]:# 检验是奇数还是偶数，奇数&1为1,偶数&1为0p, 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:# cur_s[x] & 1 ^ 1 和 cur_s[y] & 1 奇偶不同ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1])return ans