结果与总结
这里是式酱～(∠・ω< )⌒☆
手速场上大分，久违摸了把前十，总算把前阵子掉的大分补了一些回来，总体来说题目都比较典比较简单，T4又又又又是字符串比较题，感觉近期出现频率有点高了，这个技能点必须点上了。
100245. 每个字符最多出现两次的最长子字符串
数据范围很小，可以暴力枚举子串并统计其中元素个数。
复杂度更低的实现可以用滑动窗口，类似站内3. 无重复字符的最长子串，题目要求找到最长子串，因此每次尽量往最远处扩展右指针，当不满足限制条件时再缩小左端点。
时间复杂度 。
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
cnt = [0] * 26
n = len(s)
left = 0
ans = 0
for right in range(n):
cnt[ord(s[right]) - ord('a')] += 1
while cnt[ord(s[right]) - ord('a')] > 2:
cnt[ord(s[left]) - ord('a')] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans100228. 执行操作使数据元素之和大于等于 K
每次操作可以选择将某个元素加 ，也可以复制其中某个元素，当给你一系列这样的操作时，很明显先把加 全部应用在某个元素上，然后再对其进行复制，这样可以让数组和最大。
那么枚举一下要让一开始的 增长到多少再进行复制，取操作次数最小值即可。
时间复杂度 。
class Solution:
def minOperations(self, k: int) -> int:
ans = 10 ** 18
for i in range(1,k + 1):
ans = min(ans,(i - 1) + (k + i - 1) // i - 1)
return ans由均值不等式可以得知，最后一定在 的平方根的附近可以取得操作次数最小。
时间复杂度 。
class Solution:
def minOperations(self, k: int) -> int:
ans = 10 ** 18
sqrt = int(k ** 0.5)
for i in range(max(1,sqrt - 2),max(k + 1,sqrt + 3)):
ans = min(ans,(i - 1) + (k + i - 1) // i - 1)
return ans100258. 最高频率的 ID
比较典的最大频率计数题，可以用懒删除堆来解决，维护一个大根堆和一个频率计数的哈希表，每次操作时，我们把新修改的频率直接加入堆，不急着在堆中删除旧的频率，当统计答案时我们需要一个堆顶元素，此时再检查堆顶元素是否与哈希表中的频率相对应，不能匹配就将其弹出堆，实现旧频率的删除。
时间复杂度 。
class Solution:
def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
c = Counter()
import heapq
q = []
n = len(nums)
ans = []
for i in range(n):
c[nums[i]] += freq[i]
heapq.heappush(q, (-c[nums[i]], nums[i]))
while q and c[q[0][1]] != -q[0][0]:
heapq.heappop(q)
ans.append(-q[0][0])
return ans100268. 最长公共后缀查询
题目要求每个查询返回与查询字符串具有最长公共后缀的字符串下标，如果多个字符串具有相等的最长公共后缀，那么返回最短长度的，如果有多个字符串有相同最短长度，返回最小下标的那一个。
可以用字符串哈希预处理 中的所有后缀，做每次查询时，我们可以由大到小枚举当前查询的字符串的后缀，判断该后缀是否可以作为 的某个字符串的后缀，可以用 实现 级别的验证。
维护时在每个相同的后缀下注意记录一下总长度和下标信息，代码实现上下标从 开始是为了引入空字符串。
时间复杂度 ，其中 为 中所有字符串的长度之和， 为 所有字符串的长度之和。
class Hash:
def __init__(self, s, seed, mod):
self.n = len(s)
self.pw = [1]
self.mod = mod
self.table = [0] * (self.n + 1)
for i in range(1, self.n + 1):
self.pw.append(self.pw[-1] * seed % mod)
for i in range(self.n - 1, -1, -1):
self.table[i] = self.table[i + 1] * seed + ord(s[i])
self.table[i] %= mod
# 取闭区间[l,r] 可以 l == r + 1 返回0
def get(self, l, r):
return (self.table[l] - self.table[r + 1] * self.pw[r - l + 1] + self.mod) % self.mod
class Solution:
def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
mod = random.randint(10 ** 18, 2 * 10 ** 18)
d = dict()
for i in range(len(wordsContainer)):
w = wordsContainer[i]
suf = Hash(w[::-1], 31, mod)
for j in range(-1,len(w)):
key = suf.get(0, j)
if key not in d:
d[key] = [len(w),i]
else:
if len(w) < d[key][0]:
d[key] = [len(w),i]
ans = []
for q in wordsQuery:
su = Hash(q[::-1], 31, mod)
for j in range(len(q) - 1, -2, -1):
key = su.get(0, j)
if key in d:
ans.append(d[key][1])
break
return ans比较严格的做法是用字典树，维护每个后缀其实就是对倒序字符串维护每一个前缀，修改一下添加和查询的函数让其对沿途节点也生效即可，比较的规则同样是优先最长公共后缀，其次是最短长度，然后再是最小下标。
时间复杂度 。
class Trie:
def __init__(self):
self.child = {}
self.le = 10 ** 18
self.end = -1
class Solution:
def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
root = Trie()
def add(s, i):
cur = root
if len(s) < cur.le:
cur.le = len(s)
cur.end = i
for c in s:
if c not in cur.child:
cur.child[c] = Trie()
cur = cur.child[c]
if len(s) < cur.le:
cur.le = len(s)
cur.end = i
def search(s):
cur = root
ans = cur.end
for c in s:
if c not in cur.child:
return ans
cur = cur.child[c]
ans = cur.end
return ans
n = len(wordsContainer)
for i in range(n):
add(wordsContainer[i][::-1], i)
ans = []
for q in wordsQuery:
ans.append(search(q[::-1]))
return ans写在最后
