Leetcode 第 138 场双周赛题解
Leetcode 第 138 场双周赛题解
- Leetcode 第 138 场双周赛题解
- 题目1：3270. 求出数字答案
- 思路
- 代码
- 复杂度分析
- 题目2：3271. 哈希分割字符串
- 思路
- 代码
- 复杂度分析
- 题目3：3272. 统计好整数的数目
- 思路
- 代码
- 复杂度分析
- 题目4：3273. 对 Bob 造成的最少伤害
- 思路
- 代码
- 复杂度分析
Leetcode 第 138 场双周赛题解
题目1：3270. 求出数字答案
思路
按题意模拟。
代码
/*
* @lc app=leetcode.cn id=3270 lang=cpp
*
* [3270] 求出数字答案
*/
// @lc code=start
class Solution
{
public:
int generateKey(int num1, int num2, int num3)
{
string s1 = trans(num1);
string s2 = trans(num2);
string s3 = trans(num3);
string s = "";
for (int i = 0; i < 4; i++)
s += min(s1[i], min(s2[i], s3[i]));
return stoi(s);
}
// 辅函数
string trans(int x)
{
string s = to_string(x);
int n = s.length();
for (int i = 0; i < 4 - n; i++)
s.insert(s.begin(), '0');
return s;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。
题目2：3271. 哈希分割字符串
思路
按题意模拟。
代码
/*
* @lc app=leetcode.cn id=3271 lang=cpp
*
* [3271] 哈希分割字符串
*/
// @lc code=start
class Solution
{
public:
string stringHash(string s, int k)
{
int n = s.length();
string result;
for (int i = 0; i < n / k; i++)
{
int sum = 0;
for (int j = 0; j < k; j++)
sum += s[i * k + j] - 'a';
int hashedChar = sum % 26;
result.push_back(hashedChar + 'a');
}
return result;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)，返回值不计入。
题目3：3272. 统计好整数的数目
思路
枚举所有长为 n 的回文数的左半边。
如果回文数 x 能被 k 整除，那么接下来需要解决的问题有两个：
- 计算 x 有多少个不同的排列。
- 不能重复统计。
统计 s 中的每个数字的出现次数 cnt。
先填最高位。由于不能有前导零，最高位可以填的数有 n−cnt0 个。其余 n−1 个数随便排，有 (n−1)! 种方案。
当然，这里面有重复的，例如 x=34543，其中两个 3 和两个 4 的排列就是重复的，由于这两个 3 无法区分，两个 4 无法区分，方案数要除以 2!2!。
代码
/*
* @lc app=leetcode.cn id=3272 lang=cpp
*
* [3272] 统计好整数的数目
*/
// @lc code=start
class Solution
{
private:
vector<int> factorial;
void init(int n)
{
factorial.assign(n + 1, 0);
factorial[0] = 1;
for (int i = 1; i <= n; i++)
{
factorial[i] = factorial[i - 1] * i;
}
}
public:
long long countGoodIntegers(int n, int k)
{
init(n);
long long ans = 0;
unordered_set<string> vis;
int base = pow(10, (n - 1) / 2);
for (int i = base; i < base * 10; i++)
{ // 枚举回文数左半边
string s = to_string(i);
s += string(s.rbegin() + (n % 2), s.rend());
if (stoll(s) % k)
{ // 回文数不能被 k 整除
continue;
}
ranges::sort(s);
if (!vis.insert(s).second)
{ // 不能重复统计
continue;
}
int cnt[10]{};
for (char c : s)
{
cnt[c - '0']++;
}
int res = (n - cnt[0]) * factorial[n - 1];
for (int c : cnt)
{
res /= factorial[c];
}
ans += res;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(10m * nlogn)，其中 m = (n-1)/2。
空间复杂度：O(10m * n)，其中 m = (n-1)/2。
题目4：3273. 对 Bob 造成的最少伤害
思路
贪心。
首先，一直攻击同一个敌人，相比来回攻击多个敌人（雨露均沾）更好，因为这样我们被敌人攻击的次数更少。
从特殊到一般，想一想，如果只有两个敌人 A 和 B，我们应该先攻击谁？
消灭 A 需要攻击的次数为 kA = ceil(healthA / power)，同理可得消灭 B 需要的攻击次数，记作 kB。
如果先消灭 A，再消灭 B，那么受到的伤害总和为 kA * damageA + (kA + kB) * damageB；如果先消灭 B，再消灭 A，那么受到的伤害总和为 kB * damageB + (kA + kB) * damageA。
如果先消灭 A，再消灭 B 更好，那么有 kA * damageA + (kA + kB) * damageB < kB * damageB + (kA + kB) * damageA，化简得 kA * damageB < kB * damageA。
推广到更多的敌人，可以按照上式对 damage 和 health 排序，理由如下。
先假定按照输入的顺序消灭敌人。如果发现相邻两个敌人不满足上面的不等式，就交换这两个敌人的位置，这可以让受到的总伤害变小。
不断交换敌人，直到所有相邻敌人都满足上面的不等式。
本质上来说，这个不断交换相邻敌人的过程，和冒泡排序是一样的。那么按照不等式对数组排序即可。
排序后，按照顺序消灭敌人。用一个变量 s 维护从一开始到击败当前敌人，所经过的秒数。把 s * damage[i] 加入答案。
代码
/*
* @lc app=leetcode.cn id=3273 lang=cpp
*
* [3273] 对 Bob 造成的最少伤害
*/
// @lc code=start
class Solution
{
public:
long long minDamage(int power, vector<int> &damage, vector<int> &health)
{
int n = damage.size();
vector<pair<int, int>> comb(n);
for (int i = 0; i < n; i++)
{
int k = ceil(1.0 * health[i] / power);
comb[i] = make_pair(k, damage[i]);
}
sort(comb.begin(), comb.end(),
[&](const pair<int, int> &p1, const pair<int, int> &p2)
{ return p1.first * p2.second < p2.first * p1.second; });
long long ans = 0LL;
long long s = 0LL;
for (auto &[k, d] : comb)
{
s += k;
ans += s * d;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 damage 的长度。
空间复杂度：O(n)，其中 n 是数组 damage 的长度。