欢迎大家加QQ群：623375442，可以方便群里面交流。
100423. Find the Key of the Numbers
给你三个 正 整数 num1 ，num2 和 num3 。
数字 num1 ，num2 和 num3 的数字答案 key 是一个四位数，定义如下：
- 一开始，如果有数字 少于 四位数，给它补 前导 0 。
- 答案 key 的第 i 个数位（1 <= i <= 4）为 num1 ，num2 和 num3 第 i 个数位中的 最小 值。
请你返回三个数字 没有 前导 0 的数字答案。
测试样例：
输入：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 。
解答：暴力枚举每一位的最小值。
class Solution {
public int generateKey(int num1, int num2, int num3) {
int mul = 1;
int res = 0;
for (int i = 0; i < 4; ++i) {
int t = Math.min(num1 % 10, Math.min(num2 % 10, num3 % 10));
num1 /= 10;
num2 /= 10;
num3 /= 10;
res += t * mul;
mul *= 10;
}
return res;
}
}100399. Hash Divided String
给你一个长度为 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 。
测试样例：
输入：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' 。
解答：按照提议计算每k位计算一下hash。
class Solution {
public String stringHash(String s, int k) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i = i + k) {
int sum = 0;
for (int j = 0; j < k; ++j) {
sum += s.charAt(i + j) - 'a';
}
sum %= 26;
sb.append((char) (sum + 'a'));
}
return sb.toString();
}
}100406. Find the Count of Good Integers
给你两个 正 整数 n 和 k 。
如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。
- x 是一个 回文整数 。
- x 能被 k 整除。
如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。
请你返回 n 个数位的整数中，有多少个 好 整数。
注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。
测试样例：
输入：n = 3, k = 5
输出：27
解释：部分好整数如下：
- 551 ，因为它可以重排列得到 515 。
- 525 ，因为它已经是一个 k 回文整数。
解答：这周最难的一道题目。分位2步，枚举所有可能的回文数，其次利用组合计算所有可能的数字。
class Solution {
public long countGoodIntegers(int n, int k) {
if (n == 1) {
int res = 0;
for (int i = 1; i < 10; ++i) {
if (i % k == 0) {
++res;
}
}
return res;
}
// 得到组合
int[][] c = combine(10);
int d = n / 2;
int max = (int) Math.pow(10, d);
HashSet<Integer> set = new HashSet<>();
long res = 0;
for (int i = max / 10; i < max; ++i) {
if (n % 2 == 0) {
// 第一步当前回位数是否能够被k整除
if (isDiv(i, -1, k, d)) {
int key = buildKey(i, -1);
if (!set.contains(key)) {
set.add(key);
int[] count = buildCount(i);
// 计算组合可能
// 注意函数，不能有0位首位
res += getAllPossible(count, c, n);
}
}
} else {
for (int j = 0; j < 10; ++j) {
if (isDiv(i, j, k, d)) {
int key = buildKey(i, j);
if (!set.contains(key)) {
set.add(key);
int[] count = buildCount(i);
count[j] += 1;
res += getAllPossible(count, c, n);
}
}
}
}
}
return res;
}
private int[][] combine(int x) {
int[][] res = new int[x + 1][x + 1];
res[0][1] = 1; res[1][1] = 1;
for (int i = 2; i <= x; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
res[j][i] = 1;
} else {
res[j][i] = res[j - 1][i - 1] + res[j][i - 1];
}
}
}
return res;
}
private boolean isDiv(int x, int y, int k, int d) {
int remain = x;
if (y != -1) {
remain = remain * 10 + y;
}
remain %= k;
for (int i = 0; i < d; ++i) {
remain = (remain * 10) % k;
}
int reverse = 0;
while (x > 0) {
reverse = reverse * 10 + x % 10;
x /= 10;
}
reverse %= k;
return (remain + reverse) % k == 0;
}
private int buildKey(int x, int y) {
int[] count = new int[10];
while (x > 0) {
count[x % 10] += 1;
x /= 10;
}
int res = 0;
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < count[i]; ++j) {
res = res * 10 + i;
}
}
if (y >= 0) {
res = res * 10 + y;
}
return res;
}
private int[] buildCount(int x) {
int[] count = new int[10];
while (x > 0) {
count[x % 10] += 2;
x /= 10;
}
return count;
}
private long getAllPossible(int[] count, int[][] combine, int n) {
long res = 1;
for (int i = 0; i < 10; ++i) {
if (count[i] == 0) continue;
if (i == 0) {
res *= combine[count[i]][n - 1];
} else {
res *= combine[count[i]][n];
}
n -= count[i];
}
return res;
}
}100391. Minimum Amount of Damage Dealt to Bob
给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。
Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。
每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。
请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会收到多少伤害。
测试样例：
输入：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个敌人。damage分别是da, db。杀死他们需要ta, tb。那么有2种可能da * ta + db * (ta + tb) or da * (ta + tb) + db * tb。计算之后，可以发现重点是db * ta和da * tb的大小只比。越小就越后处理。
class Solution {
public long minDamage(int power, int[] damage, int[] health) {
int len = damage.length;
Integer[] sort = new Integer[len];
int[] time = new int[len];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
time[i] = health[i] / power + (health[i] % power == 0 ? 0 : 1);
}
Arrays.sort(sort, (a, b) -> (Integer.compare(damage[b] * time[a], damage[a] * time[b])));
long res = 0, timeSum = 0;
for (int i : sort) {
timeSum += time[i];
res += damage[i] * timeSum;
}
return res;
}
}