目录
100284. 有效单词
原题链接
思路分析
AC代码
100275. K 周期字符串需要的最少操作次数
原题链接
思路分析
AC代码
100283. 同位字符串连接的最小长度
原题链接
思路分析
AC代码
100288. 使数组中所有元素相等的最小开销
原题链接
思路分析
AC代码
100284. 有效单词
原题链接
100284. 有效单词
思路分析
直接模拟即可
时间复杂度O(n)
AC代码
class Solution:def isValid(self, word: str) -> bool:n = len(word)if n < 3:return Falsef1, f2 = False, Falsest1 = ['a', 'e', 'i', 'o', 'u']for x in word:if not (str.isdigit(x) or str.isalpha(x)):return Falseif str.lower(x) in st1:f1 = Trueif str.isalpha(x) and (not str.lower(x) in st1):f2 = Truereturn f1 and f2100275. K 周期字符串需要的最少操作次数
原题链接
100275. K 周期字符串需要的最少操作次数
思路分析
我们所有整除k下标开始的长度为k的字符串中的最大出现次数ma
那么答案就是n / k - ma
时间复杂度O(n)
AC代码
class Solution:def minimumOperationsToMakeKPeriodic(self, word: str, k: int) -> int:n = len(word)cnt = Counter([word[i:i+k] for i in range(n) if i % k == 0])return n // k - cnt.most_common(1)[0][1]100283. 同位字符串连接的最小长度
原题链接
100283. 同位字符串连接的最小长度
思路分析
比赛的时候用gcd，三行代码直接过了，赛后发现一堆人说不对，然后发现中文题目翻译错了真无语了，赛后复测的话这次要掉大分了
由于同位字符串长度整除s的长度，我们枚举s长度的因子，然后滑窗判断是否成立，成立就返回
时间复杂度：O(n^(3/2))
AC代码
class Solution:def minAnagramLength(self, s: str) -> int:i = 1n = len(s)while i <= n:if n % i:i += 1continuecnt = Counter(s[:i])f = 1for j in range(i, n, i):if Counter(s[j:j+i]) != cnt:f = 0breakif f:return ii += 1100288. 使数组中所有元素相等的最小开销
原题链接
100288. 使数组中所有元素相等的最小开销
思路分析
对于n种物品，每种物品有若干个，我们可以一次拿一个物品也可以一次拿两个不同的物品，如果我们两个两个拿，我们最多拿多少次？
建议先看这道题：
贪心，LeetCode 1953. 你可以工作的最大周数
通过上面这道题，我们可以得到结论，对于上面的物品，我们可以得到的最长两两不同的物品序列长度为min(s + ma, s * 2 + 1)，其中ma为最大物品数，s为除去最多的那种物品的物品数的和
那么我们每次拿两个不同的物品可以拿的最大次数就是上面的结果除以2向下取余即可
然后看本题
如果n = 1，2我们进行特判
如果cost1 * 2 <= cost2，那么两个两个加没有优势，我们把每个数字加到序列中最大的数的代价就是答案
cost1 * 2 > cost2 时，显然两个两个加比单独加要更优，我们这样考虑
把所有数字加到某个相同的数字ma，等价于在[ma - nums[i]]这样一个新数组中，每次拿两个不同的物品或者每次拿一个物品，把所有物品拿完的最小代价
我们已知两个两个拿比单独拿更优，那么尽可能多的两个两个拿，然后剩下的单独拿就是最优解
我们发现最终结果取决于ma，ma最小是我们构造出的新数组的最大值
我们ma增加1，s会增加n，故：
ma < s - 1时，ma增加会导致两个两个拿和单独拿的次数都增加，不会得到更优解
ma > s + 1时，ma增加，两个两个拿次数增加，单独拿次数可能减小，可能得到更优解
而ma增长速度小于s，所以最多增加ma初始值次，所以我们枚举初始ma到ma * 2过程中的结果即可
时间复杂度O(n + U)，U为值域上限
更快的做法是三分，因为我们把上面分析更进一步会发现答案为一个单峰函数，而求解单峰函数的经典做法就是三分，比赛还是求稳直接枚举得了
AC代码
mod = 10**9 + 7
class Solution:def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:ma = max(nums)nums = [ma - x for x in nums]if cost2 > cost1 * 2:return sum([x * cost1 for x in nums]) % mods = sum(nums)ma = max(nums)op2 = min(s // 2, s - ma)op1 = s - op2 * 2ret = op1 * cost1 + op2 * cost2n = len(nums)if n == 1:return 0if n == 2:return ret % modt = mafor _ in range(t):ma += 1s += nop2 = min(s // 2, s - ma)op1 = s - op2 * 2ret = min(ret, op1 * cost1 + op2 * cost2)return ret % mod
