6341. Determine the Winner of a Bowling Game
给你两个下标从 0 开始的整数数组 player1 和 player2 ，分别表示玩家 1 和玩家 2 击中的瓶数。
保龄球比赛由 n 轮组成，每轮的瓶数恰好为 10 。
假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：
- 如果玩家在前两轮中击中了 10 个瓶子，则为 2xi 。
- 否则，为 xi 。
玩家的得分是其 n 轮价值的总和。
返回
- 如果玩家 1 的得分高于玩家 2 的得分，则为 1 ；
- 如果玩家 2 的得分高于玩家 1 的得分，则为 2 ；
- 如果平局，则为 0 。
测试样例：
输入：player1 = [4,10,7,9], player2 = [6,5,2,3]
输出：1
解释：player1 的得分是 4 + 10 + 27 + 29 = 46 。player2 的得分是 6 + 5 + 2 + 3 = 16 。player1 的得分高于 player2 的得分，所以 play1 在比赛中获胜，答案为 1 。
解答：按题意计算每个玩家的成绩，然后比较大小
class Solution {
public int isWinner(int[] player1, int[] player2) {
int s1 = score(player1), s2 = score(player2);
if (s1 > s2) {
return 1;
} else if (s2 > s1) {
return 2;
}
return 0;
}
private int score(int[] player) {
int res = 0;
for (int i = 0; i < player.length; ++i) {
if (i - 1 >= 0 && player[i - 1] == 10) {
res += 2 * player[i];
} else if (i - 2 >= 0 && player[i - 2] == 10) {
res += 2 * player[i];
} else {
res += player[i];
}
}
return res;
}
}6342. First Completely Painted Row or Column
给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。
从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。
请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。
测试样例：
输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：arr[2] 在矩阵中的第一行或第二列上都被涂色。
解答：首先只做一个Map，知道每个数所对应的位置。然后遍历arr，同时更新行列的涂色情况。如果发现某一列或者某一行完成着色，则返回当前位置。
class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] cr = new int[m], cc = new int[n];
int[][] map = new int[m * n][2];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
map[mat[i][j] - 1][0] = i;
map[mat[i][j] - 1][1] = j;
}
}
for (int i = 0; i < arr.length; ++i) {
cr[map[arr[i] - 1][0]] += 1;
cc[map[arr[i] - 1][1]] += 1;
if (cr[map[arr[i] - 1][0]] == n || cc[map[arr[i] - 1][1]] == m) {
return i;
}
}
return -1;
}
}6343. Minimum Cost of a Path With Special Roads
给你一个数组 start ，其中 start = [startX, startY] 表示你的初始位置位于二维空间上的 (startX, startY) 。另给你一个数组 target ，其中 target = [targetX, targetY] 表示你的目标位置 (targetX, targetY) 。
从位置 (x1, y1) 到空间中任一其他位置 (x2, y2) 的代价是 |x2 - x1| + |y2 - y1| 。
给你一个二维数组 specialRoads ，表示空间中存在的一些特殊路径。其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi] 表示第 i 条特殊路径可以从 (x1i, y1i) 到 (x2i, y2i) ，但成本等于 costi 。你可以使用每条特殊路径任意次数。
返回从 (startX, startY) 到 (targetX, targetY) 所需的最小代价。
测试样例
输入：start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
输出：5
解释：
从 (1,1) 到 (4,5) 的最优路径如下：
- (1,1) -> (1,2) ，移动的代价是 |1 - 1| + |2 - 1| = 1 。
- (1,2) -> (3,3) ，移动使用第一条特殊路径，代价是 2 。
- (3,3) -> (3,4) ，移动的代价是 |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5) ，移动使用第二条特殊路径，代价是 1 。
总代价是 1 + 2 + 1 + 1 = 5 。可以证明无法以小于 5 的代价完成从 (1,1) 到 (4,5) 。
解答：最近是真的很喜欢考Dijkstra。
这道题目是一道需要一点点脑筋急转弯的题目。如果一个点不是特殊路径的起点或者终点，那这个点本质上对计算不会产生影响（cost一定是|x2 - x1| + |y2 - y1|）。我们需要做的是，利用起点，然后用Dijkstra查看利用特殊路径会对特殊路径的起点和终点产生什么影响。不断更新最小代价，直到所有点都是最优情况为止。
这个时候，我们查看所有特殊点到终点的代价，并记录最少代价即可。
class Solution {
private static final long mul = 1_000_01;
public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
Map<Long, Long> pos = new HashMap<>();
pos.put(serialize(start), 0L);
TreeSet<Long> queue = new TreeSet<>(new Comparator<Long>() {
@Override
public int compare(Long o1, Long o2) {
Long v1 = pos.getOrDefault(o1, Long.MAX_VALUE), v2 = pos.getOrDefault(o2, Long.MAX_VALUE);
if (v1.compareTo(v2) != 0) {
return v1.compareTo(v2);
} else {
return o1.compareTo(o2);
}
}
});
queue.add(serialize(start));
while (!queue.isEmpty()) {
long key = queue.first(), cost = pos.get(key);
queue.remove(key);
int[] p = deserialize(key);
for (int[] r : specialRoads) {
long k1 = serialize(r[0], r[1]), k2 = serialize(r[2], r[3]);
if (p[0] != r[0] || p[1] != r[1]) {
int c = Math.abs(p[0] - r[0]) + Math.abs(p[1] - r[1]);
long curCost = c + cost;
if (!pos.containsKey(k1) || pos.get(k1) > curCost) {
queue.remove(k1);
pos.put(k1, curCost);
queue.add(k1);
}
} else {
int c = r[4];
long curCost = c + cost;
if (!pos.containsKey(k2) || pos.get(k2) > curCost) {
queue.remove(k2);
pos.put(k2, curCost);
queue.add(k2);
}
}
if (p[0] != r[2] || p[1] != r[3]) {
int c = Math.abs(p[0] - r[2]) + Math.abs(p[1] - r[3]);
long curCost = c + cost;
if (!pos.containsKey(k2) || pos.get(k2) > curCost) {
queue.remove(k2);
pos.put(k2, curCost);
queue.add(k2);
}
}
}
}
long res = Math.abs(target[0] - start[0]) + Math.abs(target[1] - start[1]);
for (int[] r : specialRoads) {
long k1 = serialize(r[0], r[1]), k2 = serialize(r[2], r[3]);
if (pos.containsKey(k1)) {
res = Math.min(res, pos.get(k1) + Math.abs(target[0] - r[0]) + Math.abs(target[1] - r[1]));
}
if (pos.containsKey(k2)) {
res = Math.min(res, pos.get(k2) + Math.abs(target[0] - r[2]) + Math.abs(target[1] - r[3]));
}
}
return (int)res;
}
private long serialize(int[] p) {
return p[0] * mul + p[1];
}
private long serialize(int p1, int p2) {
return p1 * mul + p2;
}
private int[] deserialize(long key) {
int l1 = (int)(key / mul), l2 = (int)(key % mul);
return new int[]{l1, l2};
}
}6344. Lexicographically Smallest Beautiful String
如果一个字符串满足以下条件，则称其为 美丽字符串 ：
- 它由英语小写字母表的前 k 个字母组成。
- 它不包含任何长度为 2 或更长的回文子字符串。
给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。
对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。
例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。
测试样例
输入：s = "abcz", k = 26
输出："abda"
解释：
字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。
解答：这道题目其实也是有点脑经急转弯。需要满足不包含任何长度为 2 或更长的回文子字符串，翻译一下就是对于字符串str来说:
- str.charAt(i) != str.charAt(i + 1)
- str.charAt(i) != str.charAt(i + 2)
增加这个条件之后，我们就可以用类似寻找下一个字典序的算法来计算结果
class Solution {
public String smallestBeautifulString(String s, int k) {
int len = s.length() - 1;
for (int i = len; i >= 0; --i) {
int cur = s.charAt(i) - 'a';
if (cur == k - 1) continue;
int[] t = before(s, i);
int isValid = -1;
for (int j = cur + 1; j < k; ++j) {
if (j != t[0] && j != t[1]) {
isValid = j;
break;
}
}
if (isValid != -1) {
StringBuilder res = new StringBuilder(s.substring(0, i));
res.append((char)(isValid + 'a'));
for (int j = i + 1; j <= len; ++j) {
int b1 = res.charAt(res.length() - 1) - 'a';
int b2 = res.length() - 2 >= 0 ? (res.charAt(res.length() - 2) - 'a') : -1;
res.append(findBest(k, b1, b2));
}
return res.toString();
}
}
return "";
}
private int[] before(String s, int p) {
int l1 = p - 1 >= 0 ? (s.charAt(p - 1) - 'a') : -1;
int l2 = p - 2 >= 0 ? (s.charAt(p - 2) - 'a') : -1;
return new int[]{l1, l2};
}
private char findBest(int k, int a, int b) {
for (int i = 0; i < k; ++i) {
if (i != a && i != b) {
return (char)(i + 'a');
}
}
return 0;
}
}