这周本质上就2题，我就放两个题解了。
100192. Minimum Number of Pushes to Type Word II
给你一个字符串 word，由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。
现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。
返回重新映射按键后输入 word 所需的 最少 按键次数。
下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。
测试样例：
输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释："a" -> 在按键 2 上按一次
- "b" -> 在按键 3 上按一次
- "c" -> 在按键 4 上按一次
- "d" -> 在按键 5 上按一次
- "e" -> 在按键 6 上按一次
- "f" -> 在按键 7 上按一次
- "g" -> 在按键 8 上按一次
- "h" -> 在按键 9 上按两次
- "i" -> 在按键 9 上按一次
总成本为 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + 1 2 + 2 2 + 6 * 1 = 24 。可以证明不存在其他成本更低的映射方案。
解答：计算一下每个数字的出现次数，然后出现次数多的数字尽量少按（贪婪）。
class Solution {
public int minimumPushes(String word) {
int[] count = new int[26];
for (int i = 0; i < word.length(); ++i) {
count[word.charAt(i) - 'a'] += 1;
}
Arrays.sort(count);
int res = 0, mul = 1, remain = 8;
for (int i = 25; i >= 0; --i) {
--remain;
if (remain < 0) {
remain = 7;
++mul;
}
res += mul * count[i];
}
return res;
}
}100213. Count the Number of Houses at a Certain Distance II
给你三个 正整数 n 、x 和 y 。
在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。
对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 k 。
返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。
注意，x 与 y 可以 相等 。
测试样例：
输入：n = 3, x = 1, y = 3
输出：[6,0,0]
解释：让我们检视每个房屋对
- 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
- 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
- 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
- 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
- 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。
- 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。
解答：这道题目主要是细心。题目本身考察区间更新。我们可以按照x和y，把数组切分成三块。第一块和第三块因为x和y短接，必然能够减少路程。第一块和第二块，第三块和第二块，以及第二块内部需要通过不等式计算获取哪些范围会发生更新。发生更新的区域，它的diff必然一致（有兴趣可以自己手动推导一下）。
class Solution {
public long[] countOfPairs(int n, int x, int y) {
long[] res = new long[n];
for (int i = 0; i < res.length; ++i) {
res[i] = (n - i - 1L) * 2;
}
if (Math.abs(x - y) > 1) {
int l = Math.min(x, y) - 1, r = Math.max(x, y) - 1;
long[] lazyUpdate = new long[n];
for (int i = 0; i < l; ++i) {
int min = r + 1 - i - 1, max = n - 1 - i - 1;
update(lazyUpdate, min, -2);
update(lazyUpdate, max + 1, +2);
update(lazyUpdate, min - (r - l - 1), 2);
update(lazyUpdate, max - (r - l - 1) + 1, -2);
}
for (int i = l; i <= r; ++i) {
if (2 * i > r + l + 1) {
int diff = 2 * i - l - r - 1;
int min = i - (l - 1) - 1, max = i - 1;
update(lazyUpdate, min, -2);
update(lazyUpdate, max + 1, +2);
update(lazyUpdate, min - diff, 2);
update(lazyUpdate, max - diff + 1, -2);
}
if (2 * i < l + r - 1) {
int diff = l + r - 1 - 2 * i;
int min = r + 1 - i - 1, max = n - 1 - i - 1;
update(lazyUpdate, min, -2);
update(lazyUpdate, max + 1, +2);
update(lazyUpdate, min - diff, 2);
update(lazyUpdate, max - diff + 1, -2);
}
}
for (int i = r - l; i > 0; --i) {
if (2 * i <= r - l + 1) {
break;
}
int count = r - l - i + 1;
res[i - 1] -= 2L * count;
res[r - l - i] += 2L * count;
}
long add = 0;
for (int i = 0; i < lazyUpdate.length; ++i) {
add += lazyUpdate[i];
res[i] += add;
}
}
return res;
}
private void update(long[] arr, int pos, int val) {
if (pos >= 0 && pos < arr.length) {
arr[pos] += val;
}
}
}