Leetcode 第 138 场双周赛题解

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 整除，那么接下来需要解决的问题有两个：

1. 计算 x 有多少个不同的排列。
2. 不能重复统计。

统计 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(10^m * nlogn)，其中 m = (n-1)/2。

空间复杂度：O(10^m * n)，其中 m = (n-1)/2。

题目4：3273. 对 Bob 造成的最少伤害

思路

贪心。

首先，一直攻击同一个敌人，相比来回攻击多个敌人（雨露均沾）更好，因为这样我们被敌人攻击的次数更少。

从特殊到一般，想一想，如果只有两个敌人 A 和 B，我们应该先攻击谁？

消灭 A 需要攻击的次数为 k_A = ceil(health_A / power)，同理可得消灭 B 需要的攻击次数，记作 k_B。

如果先消灭 A，再消灭 B，那么受到的伤害总和为 k_A * damage_A + (k_A + k_B) * damage_B；如果先消灭 B，再消灭 A，那么受到的伤害总和为 k_B * damage_B + (k_A + k_B) * damage_A。

如果先消灭 A，再消灭 B 更好，那么有 k_A * damage_A + (k_A + k_B) * damage_B < k_B * damage_B + (k_A + k_B) * damage_A，化简得 k_A * damage_B < k_B * damage_A。

推广到更多的敌人，可以按照上式对 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 的长度。