共计 5987 个字符,预计需要花费 15 分钟才能阅读完成。
⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 BaguTree Pro 常识星球发问。
学习数据结构与算法的关键在于把握问题背地的算法思维框架,你的思考越形象,它能笼罩的问题域就越广,了解难度也更简单。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起领会上分之旅。
本文是 LeetCode 上分之旅系列的第 43 篇文章,往期回顾请移步到文章开端 \~
LeetCode 双周赛 112
T1. 判断通过操作是否让字符串相等 I(Easy)
- 标签:模仿
T2. 判断通过操作是否让字符串相等 II(Medium)
- 标签:模仿、计数、排序
T3. 简直惟一子数组的最大和(Medium)
- 标签:滑动窗口、计数
T4. 统计一个字符串的 k 子序列漂亮值最大的数目(Hard)
- 标签:枚举、贪婪、排序、乘法原理、组合数
T1. 判断通过操作是否让字符串相等 I(Easy)
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-i/
题解(模仿)
因为只能替换间隔偶数倍的地位,因而相当于比拟两个字符串雷同奇偶性下标上的元素是否相等。
- 写法 1:基于散列表
class Solution {fun canBeEqual(s1: String, s2: String): Boolean {return setOf(s1[0], s1[2]) == setOf(s2[0], s2[2]) && setOf(s1[1], s1[3]) == setOf(s2[1], s2[3])
}
}
- 写法 2:基于字符串
class Solution:
def checkStrings(self, s1: str, s2: str) -> bool:
return sorted(s1[0::2]) == sorted(s2[0::2]) and sorted(s1[1::2]) == sorted(s2[1::2])
复杂度剖析:
- 工夫复杂度:$O(1)$
- 空间复杂度:$O(1)$
T2. 判断通过操作是否让字符串相等 II(Medium)
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-ii/
题解(模仿)
同上,别离统计奇偶下标上的元素个数是否相等。
写法 1:基于计数;
class Solution {fun checkStrings(s1: String, s2: String): Boolean {
val U = 26
val cnts = Array(2) {IntArray(U) }
for ((i, e) in s1.withIndex()) {cnts[i % 2][e - 'a']++
}
for ((i, e) in s2.withIndex()) {cnts[i % 2][e - 'a']--
}
return cnts[0].all {it == 0} && cnts[1].all {it == 0}
}
}
复杂度剖析:
- 工夫复杂度:$O(n + U)$ 线性遍历工夫与计数工夫;
- 空间复杂度:$O(U)$ 计数数组空间。
写法 2:基于字符串:
class Solution:
def checkStrings(self, s: str, t: str) -> bool:
return all(sorted(s[p::2]) == sorted(t[p::2]) for p in range(2))
复杂度剖析:
- 工夫复杂度:$O(nlgn)$ 排序工夫;
- 空间复杂度:$O(n)$ 结构字符串空间。
T3. 简直惟一子数组的最大和(Medium)
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/
题解(滑动窗口 + 计数)
滑动窗口模板题,保护窗口中不同元素的品种数和总和:
class Solution {fun maxSum(nums: List<Int>, m: Int, k: Int): Long {var cnts = HashMap<Int, Int>()
var type = 0
var sum = 0L
var ret = 0L
for (j in nums.indices) {
// 滑入
cnts[nums[j]] = cnts.getOrDefault(nums[j], 0) + 1
if (1 == cnts[nums[j]]!!) type++
sum += nums[j]
// 滑出
if (j >= k) {
val i = j - k
cnts[nums[i]] = cnts[nums[i]]!! - 1
if (0 == cnts[nums[i]]) type --
sum -= nums[i]
}
// 记录
if (j >= k - 1 && type >= m) {ret = max(ret, sum)
}
}
return ret
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$ 线性遍历工夫;
- 空间复杂度:$O(n)$ 散列表空间。
T4. 统计一个字符串的 k 子序列漂亮值最大的数目(Hard)
https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/
问题剖析
- 问题指标: 求所有长为 $k$ 的子序列中漂亮值是最大值的子序列数目;
- 问题要件: 先计算长为 $k$ 的子序列的最大漂亮值,再计算满足漂亮值是最大值的子序列计划数;
- 要害信息 1: 子序列要抉择不反复的字母;
- 要害信息 2: 同一个字符在原字符串中的不同地位能够结构不同子序列;
- 外围变量: $f(c)$ 是 字符 $c$ 的呈现次数,漂亮值是子序列中字符的 $f(c)$ 之和;
- 边界状况: 既然子序列要抉择不反复的字母,那么存在边界状况,当 $k$ > 字符串的字符品种数:那么肯定不能结构 $k$ 子序列,返回 $0$。
题解一(暴力枚举 + 乘法原理)
最简略的做法,咱们能够枚举所有可能的 $k$ 子序列,并记录呈现最大漂亮值的计划数,怎么实现呢?
- 办法 1 – 思考到子序列须要保留原字符串的程序,间接的想法是枚举字符串中的每个下标 $s[i]$ 选和不选,然而工夫复杂度是 $O(2^n)$ 显然不成立;
- 办法 2 – 事实上咱们不须要从原字符串的角度枚举,而是能够从字符集的角度枚举,那样工夫复杂度就能够用乘法原理来优化。比如说
a
的呈现次数是 $2$,而b
的呈现次数是 $3$,那么所有a
与b
能够结构的子序列计划数就是2 * 3 = 6
。
那么,办法会不会超时呢,咱们来简略剖析下:
因为字符集的大小 $U$ 最多只有 $26$ 个,那么子序列的计划数最多有 $C_{26}^k$ 个,而因为 $k$ 大于 $U$ 的计划是不存在的,因而非法的计划数最多只有 $C_{U}^{\frac{U}{2}} = C_{26}^{13} = 10400600$ 约等于 $10^7$。只有咱们保障求解每个子问题的工夫复杂度是 $O(1)$ 的话是能够通过的。
枚举实现:
class Solution {fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
val MOD = 1000000007
// 计数
val cnts = HashMap<Char, Int>()
for (e in s) {cnts[e] = cnts.getOrDefault(e, 0) + 1
}
val m = cnts.size
if (m < k) return 0 // 特判
// 枚举子序列
val keys = cnts.toList()
var maxCount = 0L
var maxF = 0
// 回溯
fun count(index: Int, size: Int, curF: Int, curCount: Long) {
// 终止条件
if (size == k) {if (curF > maxF) {
maxF = curF
maxCount = curCount // 更新最大漂亮值计划数
} else if (curF == maxF) {maxCount = (maxCount + curCount) % MOD // 减少计划数
}
return
}
if (size + m - index < k) return // 剪枝(长度不够)for (i in index until m) {val (c, cnt) = keys[i]
count(i + 1, size + 1, curF + cnt, curCount * cnt % MOD /* 乘法原理 */)
}
}
count(0, 0, 0, 1)
return maxCount.toInt()}
}
复杂度剖析:
- 工夫复杂度:$O(C_m^k)$ 其中 $m$ 为字符品种;
- 空间复杂度:$O(m)$ 散列表空间与递归栈空间。
题解二(排序 + 贪婪 + 乘法原理)
思考 $k = 1$ 的边界状况:
显然须要抉择 $f(c)$ 值最大的 $1$ 个字母,如果存在 $m$ 个字母的 $f(c)$ 等于最大值,那么存在 $C_m^1 = m$ 种计划。这阐明咱们没必要枚举所有字母的子序列: 因为子序列中的字符是不反复的,因而 $k$ 子序列必然要抉择 $f(c)$ 值最大的 $k$ 个字母,咱们能够将字母依照 $f(c)$ 倒序排序,优先取 $f(c)$ 更大的字母。
具体实现上:
咱们将字母依照 $f(c)$ 分桶排序,如果桶内字母数量 $K$ 小于等于 $k$,那么桶内元素都须要抉择,否则还要计算桶内元素抉择 $k$ 个的计划数:
- 抉择桶内所有元素,计划数为 $cnt^K$
- 抉择桶内局部元素,计划数为 $C_K^k · cnt^k$
其中波及到幂运算,实质是倍增思维:
// 疾速幂 x^n
private fun powM(a: Int, b: Int, mod: Int) : Long {var x = a.toLong()
var n = b.toLong()
var ret = 1L
while (n > 0L) {if (n % 2 == 1L) ret = ret * x % mod
x = x * x % mod
n /= 2
}
return ret
}
其中波及到 组合数:
- 计算式:
// 组合数计算公式 O(k)
private fun comb(n: Int, k: Int, mod: Int) : Int {
var ret = 1L
for (i in 1 .. k) {ret = ret * (n - i + 1) / i % mod
}
return ret.toInt()}
- 递推式(杨辉三角):
// 递归 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {if (n == k) {return 1} else if (k == 1) {return n} else {return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
}
}
// 迭代 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {val c = Array(n + 1) {IntArray(n + 1) }
for (i in 1 .. n) {c[i][0] = 1
c[i][i] = 1
for (j in 1 until i) {c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
}
}
return c[n][k]
}
- 卢卡斯定理:当问题规模很大,且模不太大时应用 Lucas 定理。
// 组合数计算公式
private fun comb(n: Long, k: Long, mod: Int) : Int {
var n = n
var ret = 1L
for (i in 1 .. k) {ret = ret * n-- / i % mod}
return ret.toInt()}
// 卢卡斯定理
fun Lucas(n: Long, k: Long, mod: Int) : Long {if (k == 0L) return 1L;
return (comb(n % mod, k % mod, mod) * Lucas(n / mod, k / mod, mod)) % mod;
}
残缺代码:
class Solution {fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
val MOD = 1000000007
// 计数
val cnts = HashMap<Char, Int>()
var maxCnt = 0
for (e in s) {cnts[e] = cnts.getOrDefault(e, 0) + 1
maxCnt = max(maxCnt, cnts[e]!!)
}
val m = cnts.size
if (m < k) return 0 // 特判
// 有序汇合
val map = TreeMap<Int, Int>() { c1, c2 ->
c2 - c1
}
// 二次频率
for ((_, c) in cnts) {map = map.getOrDefault(c, 0) + 1
}
val cntCnts = map.toList()
// println(cntCnts.joinToString())
// 结构计划
var ret = 1L
var leftK = k
for ((cnt, K) in cntCnts) {if (K > leftK) {ret = ret * powM(cnt, leftK, MOD) * comb(K, leftK, MOD) % MOD
} else {ret = ret * powM(cnt, K, MOD) % MOD
}
leftK -= K
if (leftK <= 0) break
}
return ret.toInt()}
// 组合数计算公式 C_n^k
private fun comb(n: Int, k: Int, mod: Int) : Int {if (n == k) {return 1} else if (k == 1) {return n} else {return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
}
}
// 疾速幂 x^n
private fun powM(x_: Int, n_: Int, mod: Int) : Long {var x = x_.toLong()
var n = n_.toLong()
var ret = 1L
while (n > 0L) {if (n % 2 == 1L) ret = ret * x % mod
x = x * x % mod
n /= 2
}
return ret
}
}
Python 中组合数和幂运算能够很不便地应用库函数:
class Solution:
def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
MOD = 10 ** 9 + 7
ans = 1
cnt = Counter(Counter(s).values())
for c, num in sorted(cnt.items(), reverse=True): # 二次计数
if num >= k:
return ans * pow(c, k, MOD) * comb(num, k) % MOD
ans *= pow(c, num, MOD)
k -= num
return 0
复杂度剖析:
- 工夫复杂度:$O(n + m)$ 次要工夫在枚举字符串的环节;
- 空间复杂度:$O(m)$ 散列表空间。
举荐浏览
LeetCode 上分之旅系列往期回顾:
- LeetCode 单周赛第 360 场 · 当 LeetCode 考树上倍增,出题的趋势在变动吗
- LeetCode 单周赛第 359 场 · 联合离散化的线性 DP 问题
- LeetCode 双周赛第 111 场 · 循序渐进地解决动静布局问题
- LeetCode 双周赛第 110 场 · 联合排序不等式的动静布局
⭐️ 永远置信美妙的事件行将产生,欢送退出小彭的 Android 交换社群 \~