力扣第 138 场双周赛-爱代码爱编程
给你三个 正 整数 num1 ，num2 和 num3 。
数字 num1 ，num2 和 num3 的数字答案 key 是一个四位数，定义如下：
- 一开始，如果有数字 少于 四位数，给它补 前导 0 。
- 答案
key的第i个数位（1 <= i <= 4）为num1，num2和num3第i个数位中的 最小 值。
请你返回三个数字 没有 前导 0 的数字答案。
示例 1：
输入：num1 = 1, num2 = 10, num3 = 1000
输出：0
解释：
补前导 0 后，num1 变为 "0001" ，num2 变为 "0010" ，num3 保持不变，为 "1000" 。
- 数字答案
key的第1个数位为min(0, 0, 1)。 - 数字答案
key的第2个数位为min(0, 0, 0)。 - 数字答案
key的第3个数位为min(0, 1, 0)。 - 数字答案
key的第4个数位为min(1, 0, 0)。
所以数字答案为 "0000" ，也就是 0 。
示例 2：
输入： num1 = 987, num2 = 879, num3 = 798
输出：777
示例 3：
输入：num1 = 1, num2 = 2, num3 = 3
输出：1
提示：
1 <= num1, num2, num3 <= 9999
思路：看代码即可
class Solution {
public int generateKey(int num1, int num2, int num3) {
// 将数字转换为字符串并补齐为4位数
String str1 = String.format("%04d", num1);
String str2 = String.format("%04d", num2);
String str3 = String.format("%04d", num3);
// 创建结果的StringBuilder
StringBuilder minKey = new StringBuilder();
// 逐位比较最小值
for (int i = 0; i < 4; i++) {
char minDigit = (char) Math.min(str1.charAt(i), Math.min(str2.charAt(i), str3.charAt(i)));
minKey.append(minDigit);
}
// 将结果转换为整数去掉前导零
return Integer.parseInt(minKey.toString());
}
}给你一个长度为 n 的字符串 s 和一个整数 k ，n 是 k 的 倍数 。你的任务是将字符串 s 哈希为一个长度为 n / k 的新字符串 result 。
首先，将 s 分割成 n / k 个 子字符串，每个子字符串的长度都为 k 。然后，将 result 初始化为一个 空 字符串。
我们依次从前往后处理每一个 子字符串 ：
- 一个字符的 哈希值 是它在 字母表 中的下标（也就是
'a' → 0，'b' → 1，... ，'z' → 25）。 - 将子字符串中字幕的 哈希值 求和。
- 将和对 26 取余，将结果记为
hashedChar。 - 找到小写字母表中
hashedChar对应的字符。 - 将该字符添加到
result的末尾。
返回 result 。
示例 1：
输入：s = "abcd", k = 2
输出："bf"
解释：
第一个字符串为 "ab" ，0 + 1 = 1 ，1 % 26 = 1 ，result[0] = 'b' 。
第二个字符串为： "cd" ，2 + 3 = 5 ，5 % 26 = 5 ，result[1] = 'f' 。
示例 2：
输入：s = "mxz", k = 3
输出："i"
解释：
唯一的子字符串为 "mxz" ，12 + 23 + 25 = 60 ，60 % 26 = 8 ，result[0] = 'i' 。
提示：
1 <= k <= 100k <= s.length <= 1000s.length能被k整除。s只含有小写英文字母。
思路：简单遍历，看代码即可
class Solution {
public String stringHash(String s, int k) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i += k) {
String sub = s.substring(i, i + k);
int sum = 0;
for (char c : sub.toCharArray()) {
sum += c - 'a';
}
int hashedChar = sum % 26;
char newChar = (char) (hashedChar + 'a');
result.append(newChar);
}
return result.toString();
}
}给你两个 正 整数 n 和 k 。
如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。
x是一个 回文整数 。x能被k整除。
如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。
请你返回 n 个数位的整数中，有多少个 好 整数。
注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。
示例 1：
输入：n = 3, k = 5
输出：27
解释：
部分好整数如下：
- 551 ，因为它可以重排列得到 515 。
- 525 ，因为它已经是一个 k 回文整数。
示例 2：
输入：n = 1, k = 4
输出：2
解释：
两个好整数分别是 4 和 8 。
示例 3：
输入：n = 5, k = 6
输出：2468
提示：
1 <= n <= 101 <= k <= 9
思路：考虑枚举所有长为 n 的回文数。
首先，知道了回文数的左半边，就知道了回文数的右半边，所以可以枚举回文数的左半边。
设 ，设 base=10^m。
在 [base,10*base) 范围内枚举所有长为 n 的回文数的左半边。
如果回文数 x 能被 k 整除，那么接下来需要解决的问题有两个：
1.计算x有多少个不同的排列。
2.不能重复统计。
为了保证不重复统计，把 x 的十进制字符串 s 排序，如果之前遇到过同样的字符串 t，那么 s 生成的所有排列，t 也能生成。用哈希表记录排序后的字符串，如果 s 排序后在哈希表中，那么就跳过。
下面是组合数学时间。
本质上计算的是「有重复元素的排列个数」。
统计 s 中的每个数字的出现次数 cnt。
先填最高位。由于不能有前导零，最高位可以填的数有 n−cnt0个。其余 n−1 个数随便排，有 (n−1)!种方案。
当然，这里面有重复的，例如 x=34543，其中两个3 和两个4 的排列就是重复的，由于这两个3无法区分，两个4无法区分，方案数要除以 2!2!。
综上，排列个数为
加入答案。
class Solution {
public long countGoodIntegers(int n, int k) {
int[] fac = new int[n + 1];
fac[0] = 1;
//求取各位数的阶乘
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i;
}
long ans = 0;
//去重
Set<String> vis = new HashSet<>();
int base = (int) Math.pow(10, (n - 1) / 2);
for (int i = base; i < base * 10; i++) { // 枚举回文数左半边
String s = Integer.toString(i);
StringBuilder rev = new StringBuilder(s).reverse();
s += rev.substring(n % 2);
if (Long.parseLong(s) % k > 0) { // 回文数不能被 k 整除
continue;
}
char[] sortedS = s.toCharArray();
Arrays.sort(sortedS);
if (!vis.add(new String(sortedS))) { // 不能重复统计
continue;
}
int[] cnt = new int[10];
for (char c : sortedS) {
cnt[c - '0']++;
}
int res = (n - cnt[0]) * fac[n - 1];
for (int c : cnt) {
res /= fac[c];
}
ans += res;
}
return ans;
}
}
给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。
Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。
每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。
请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会收到多少伤害。
示例 1：
输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]
输出：39
解释：
- 最开始 2 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间内对 Bob 的总伤害是
10 + 10 = 20点。 - 接下来 2 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间内对 Bob 的总伤害是
6 + 6 = 12点。 - 接下来 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间内对 Bob 的总伤害是
3点。 - 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间内对 Bob 的总伤害是
2 + 2 = 4点。
示例 2：
输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]
输出：20
解释：
- 最开始 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间对 Bob 的总伤害是
4点。 - 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间对 Bob 的总伤害是
3 + 3 = 6点。 - 接下来 3 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间对 Bob 的总伤害是
2 + 2 + 2 = 6点。 - 接下来 4 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间对 Bob 的总伤害是
1 + 1 + 1 + 1 = 4点。
示例 3：
输入：power = 8, damage = [40], health = [59]
输出：320
提示：
1 <= power <= 10^41 <= n == damage.length == health.length <= 10^51 <= damage[i], health[i] <= 10^4
思路：首先，一直攻击同一个敌人，相比来回攻击多个敌人（雨露均沾）更好，因为这样我们被敌人攻击的次数更少。
从特殊到一般，想一想，如果只有两个敌人 A 和 B，我们应该先攻击谁？
消灭 A 需要攻击的次数为
讨论 被 power 整除，和不被 power 整除两种情况，可以证明上式的正确性。
同理可得消灭 B 需要的攻击次数，记作 .
如果先消灭 A，再消灭 B，那么受到的伤害总和为
如果先消灭 B，再消灭 A，那么受到的伤害总和为
如果先消灭 A，再消灭 B 更好，那么有
化简得
推广到更多的敌人，可以按照上式对 damage 和 health 排序，理由如下。
先假定按照输入的顺序消灭敌人。如果发现相邻两个敌人不满足上面的不等式，就交换这两个敌人的位置，这可以让受到的总伤害变小。
不断交换敌人，直到所有相邻敌人都满足上面的不等式。
本质上来说，这个不断交换相邻敌人的过程，和冒泡排序是一样的。那么按照不等式对数组排序即可。
排序后，按照顺序消灭敌人。用一个变量 s 维护从一开始到击败当前敌人，所经过的秒数。把 s*damage[i] 加入答案。(参考灵神的解法)
class Solution {
public long minDamage(int power, int[] damage, int[] health) {
int n = health.length;
int[][] a = new int[n][2];
for (int i = 0; i < n; i++) {
a[i][0] = (health[i] - 1) / power + 1;
a[i][1] = damage[i];
}
Arrays.sort(a, (p, q) -> p[0] * q[1] - q[0] * p[1]);
long ans = 0;
long s = 0;
for (int[] p : a) {
s += p[0];
ans += s * p[1];
}
return ans;
}
}