⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 34 篇文章,往期回顾请移步到文章末尾~
双周赛 109
T1. 检查数组是否是好的(Easy)
- 标签:模拟、排序
T2. 将字符串中的元音字母排序(Medium)
- 标签:模拟、排序
T3. 访问数组中的位置使分数最大(Medium)
- 标签:动态规划
T4. 将一个数字表示成幂的和的方案数(Medium)
- 标签:动态规划、01 背包
T1. 检查数组是否是好的(Easy)
https://leetcode.cn/problems/check-if-array-is-good/
题解(模拟)
简单模拟题。
先排序后依次验证,最后验证尾数 N。
class Solution {
public:
bool isGood(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 1; i++) {
if (i + 1 != nums[i]) return false;
}
return nums[n - 1] == n - 1;
}
};
class Solution:
def isGood(self, nums: List[int]) -> bool:
return sorted(nums) == (list(range(1, len(nums))) + [len(nums) - 1])
复杂度分析:
- 时间复杂度:$O(nlgn)$ 瓶颈在排序;
- 空间复杂度:$O(lgn)$ 排序递归栈空间。
T2. 将字符串中的元音字母排序(Medium)
https://leetcode.cn/problems/sort-vowels-in-a-string/
题解(模拟 + 排序)
先抽取元音字母排序,再填充到结果数组中,如果使用桶排序,可以优化时间复杂度到 O(n)。
class Solution {
public:
string sortVowels(string s) {
unordered_set<char>st{
'a','e','i','o','u','A','E','I','O','U'};
string temp = "";
for(char c : s){
if(st.count(c)) temp += c;
}
// 排序
sort(temp.begin(), temp.end());
// 输出
int i = 0;
for(char &c : s){
// 原地修改
if(st.count(c)) c = temp[i++];
}
return s;
}
};
桶排序:
class Solution {
public:
string sortVowels(string s) {
unordered_set<char> st {
'a','e','i','o','u','A','E','I','O','U'};
// 桶排序(有序字典)
map<char, int> vowelCounts;
for (char c : s) {
if (st.count(c)) {
vowelCounts[c]++;
}
}
// 输出
for (char& c : s) {
// 原地修改
if (st.count(c)) {
c = vowelCounts.begin()->first;
if (--vowelCounts.begin()->second == 0) {
vowelCounts.erase(vowelCounts.begin());
}
}
}
return s;
}
};
复杂度分析:
- 时间复杂度:$O(nlgn)$ 瓶颈在排序,桶排序可以优化到 $O(n)$;
- 空间复杂度:$O(n)$ 临时字符串空间。
T3. 访问数组中的位置使分数最大(Medium)
https://leetcode.cn/problems/visit-array-positions-to-maximize-score/
题解(动态规划)
比较明显的动态规划问题,定义 dp[i][j] 表示到 [i] 为止的最大序列和,其中:
- dp[i][0] 表示尾数为偶数的序列
- dp[i][1] 表示尾数为奇数的序列
那么对于 nums[i] 来说:
- 如果 nums[i] 是偶数,那么它可以无成本地添加到尾数为偶数的序列 dp[i - 1][0] 中,也可以在消耗成本 x 的情况下添加到尾数为奇数的序列 dp[i - 1][1] 中;
- 如果 nums[i] 是奇数,那么它可以无成本地添加到尾数为奇数的序列 dp[i - 1][0] 中,也可以在消耗成本 x 的情况下添加到尾数为偶数的序列 dp[i - 1][1] 中。
于是有:
- dp[i][0] = Math.max(dp[i - 1][0] + nums[i], dp[i - 1][1] + nums[i] - x)
- dp[i][1] = Math.max(dp[i - 1][1] + nums[i], dp[i - 1][0] + nums[i] - x)
另外,由于题目要求起始点必须从 nums[0] 开始,于是我们区分两种初始状态:
- 如果 nums[0] 为偶数,初始状态 dp[0][0] = nums[i],dp[0][1] = -INF,此处 INF 表示无效,在首次选择奇数时一定会选择从 dp[i - 1][0] 转移的分支,确保从 nums[0] 开始;
- 如果 nums[0] 为奇数,初始状态 dp[0][0] = -INF,dp[0][1] = nums[0],此处 INF 表示无效,在首次选择偶数时一定会选择从 dp[i - 1][1] 转移的分支,确保从 nums[0] 开始;
最后,由于每次迭代只关心 i - 1 层子状态,可以使用滚动数组优化空间。
class Solution {
fun maxScore(nums: IntArray, x: Int): Long {
val INF = -0x3F3F3F3FL // 减少判断
val n = nums.size
var ret = nums[0].toLong()
// 初始状态
val dp = if (nums[0] % 2 == 0) {
longArrayOf(nums[0].toLong(), INF)
} else {
longArrayOf(INF, nums[0].toLong())
}
// dp[i] 表示到 [i] 为止的最大序列和
for (i in 1 until n) {
if (nums[i] % 2 == 0) {
// 偶数
dp[0] = Math.max(dp[0] + nums[i], dp[1] + nums[i] - x)
} else {
// 奇数
dp[1] = Math.max(dp[1] + nums[i], dp[0] + nums[i] - x)
}
}
return Math.max(dp[0], dp[1])
}
}
复杂度分析:
- 时间复杂度:$O(n)$ 线性遍历;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
T4. 将一个数字表示成幂的和的方案数(Medium)
https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/
题解一(01 背包)
原问题等价于:求在体积为 n 的背包中可以选择的方案数
由于题目要求方案中的数字不能存在重复数,例如 [1, 1, 1] 的方案是非法的,所以每个数最多只能选择一次,即只有选和不选两个状态,这容易联想到 01 背包模型。
- 物品:数字
- 物品体积:数字对 x 的幂
- 背包大小:n
令 dp[i][j] 表示枚举到 [i] 为止且选择体积为 j 的方案数,则对于 i 来说有 2 个选择:
- 不选:$dp[i][j] = dp[i - 1][j]$
- 选:$dp[i][j] = dp[i - 1][j - nums[i]^m]$
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
val MOD = 1000000007
// 预处理备选数
val nums = LinkedList<Int>()
var i = 1
while (true) {
val e = Math.pow(1.0 * i, 1.0 * x).toInt()
if (e > n) break
nums.add(e)
i++
}
val m = nums.size
// 01 背包 dp[i][j] 表示枚举到 [i] 为止且选择体积为 j 的方案数
val dp = Array(m + 1) { IntArray(n + 1) }
// 体积为 0 的方案数为 1
for (i in 0 .. m) dp[i][0] = 1
// 枚举物品
for (i in 1 .. m) {
for (j in 1 .. n) {
// 不选
dp[i][j] = dp[i - 1][j]
// 选
if (j >= nums[i - 1]) dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % MOD
}
}
return dp[m][n] // 枚举到末尾且选择体积为 n 的方案数
}
}
取消物品维度优化空间复杂度:
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
...
val m = nums.size
// 01 背包 dp[i][j] 表示枚举到 [i] 为止且选择体积为 j 的方案数
val dp = IntArray(n + 1)
// 体积为 0 的方案数为 1
dp[0] = 1
// 枚举物品
for (i in 1 .. m) {
for (j in n downTo nums[i - 1]) { // 逆序(会使用子问题)
dp[j] = (dp[j] + dp[j - nums[i - 1]]) % MOD
}
}
return dp[n] // 枚举到末尾且选择体积为 n 的方案数
}
}
在预处理的过程直接进行背包逻辑也可以:
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
val MOD = 1000000007
val dp = IntArray(n + 1)
dp[0] = 1
// 枚举物品
var i = 1
while (true) {
val e = Math.pow(1.0 * i, 1.0 * x).toInt()
if (e > n) break
for (j in n downTo e) { // 逆序(会使用子问题)
dp[j] = (dp[j] + dp[j - e]) % MOD
}
i++
}
return dp[n] // 枚举到末尾且选择体积为 n 的方案数
}
}
复杂度分析:
- 时间复杂度:$O(nm)$ 其中 m 为 $^x\sqrt{n}$,动态规划节点时间复杂度为 $O(nm)$;
- 空间复杂度:$O(n)$ DP 数组空间。
推荐阅读
LeetCode 上分之旅系列往期回顾:
- LeetCode 单周赛第 354 场 · 摩尔投票派上用场
- LeetCode 单周赛第 353 场 · 看似没考 LIS 最长递增子序列,好像又考了
- LeetCode 双周赛第 107 场 · 很有意思的 T2 题
- LeetCode 双周赛第 104 场 · 流水的动态规划,铁打的结构化思考
⭐️ 永远相信美好的事情即将发生,欢迎加入小彭的 Android 交流社群~