网站备案通过什么可以备案,四川网站建设 lkcms,wix怎么做网站教程,抖音seo排名文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览
题目
1371.每个元音包含偶数次的最长子字符串
1371.每个元音包含偶数次的最长子字符串
参考博主的讲解 思路分析#xff1a;就是得使用前缀和记录情况#xff0c;dp[i][j]表示s[0] 到s[i] 中就是得使用前缀和记录情况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):# 注意这里其实没有对i0进行处理因为-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]这个时候就得判断l0的情况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-leftkwhile 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
