100148. Minimum Number Game
你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ，同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏，游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下：
- 每一轮，Alice 先从 nums 中移除一个 最小 元素，然后 Bob 执行同样的操作。
- 接着，Bob 会将移除的元素添加到数组 arr 中，然后 Alice 也执行同样的操作。
- 游戏持续进行，直到 nums 变为空。
返回结果数组 arr 。
测试样例：
输入：nums = [2,5]
输出：[5,2]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [5,2] 。
解答：排序之后，按照题目要求，奇偶位互换。
class Solution {
public int[] numberGame(int[] nums) {
int len = nums.length;
int[] res = new int[len];
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int n : nums) {
queue.add(n);
}
int pos = 0;
while (pos < res.length) {
int a = queue.poll(), b = queue.poll();
res[pos++] = b;
res[pos++] = a;
}
return res;
}
}100169. Maximum Square Area by Removing Fences From a Field
有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。
水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。
返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。
由于答案可能很大，所以请返回结果对 109 + 7 取余 后的值。
注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。
测试样例：
输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。
解答：因为1 <= hFences.length, vFences.length <= 600，可以暴力枚举一下所有隔板去除的可能性，存在一个HashSet中。这样就能快速判断哪些是共有边长。寻找最长共有边长就可以了。
class Solution {
private static final int mod = 1_000_000_007;
public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
Set<Integer> d1 = fencesDis(m, hFences), d2 = fencesDis(n, vFences);
long max = 0;
for (int t : d1) {
if (d2.contains(t)) {
max = Math.max(max, t);
}
}
if (max == 0) {
return -1;
}
return (int) ((max * max) % mod);
}
private Set<Integer> fencesDis(int max, int[] fences) {
Set<Integer> res = new HashSet<>();
res.add(max - 1);
for (int i = 0; i < fences.length; ++i) {
res.add(fences[i] - 1);
res.add(max - fences[i]);
for (int j = 0; j < i; ++j) {
res.add(Math.abs(fences[i] - fences[j]));
}
}
return res;
}
}100156. Minimum Cost to Convert String I
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
测试样例：
输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe" ：
- 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。
- 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。
- 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。
- 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。可以证明这是可能的最小成本。
解答：这题是最后一题的简化版本。本质上寻找两点之间最短距离，因为一共只有26个字符，可以直接暴力运算。
class Solution {
private class PackedInfo {
int[][] edges;
long[][] floyd;
public PackedInfo(char[] original, char[] changed, int[] cost) {
edges = new int[26][26];
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
edges[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < original.length; ++i) {
edges[original[i] - 'a'][changed[i] - 'a'] = Math.min(edges[original[i] - 'a'][changed[i] - 'a'], cost[i]);
}
floyd = initialFloyd(26);
}
private long[][] initialFloyd(int n) {
long[][] res = new long[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) res[i][j] = -1;
}
}
return res;
}
public long getBestDis(int st, int ed) {
if (floyd[st][ed] == -1) {
for (int i = 0; i < floyd.length; ++i) {
floyd[st][i] = Long.MAX_VALUE;
}
TreeSet<Integer> queue = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
Long s1 = floyd[st][o1], s2 = floyd[st][o2];
if (!s1.equals(s2)) {
return s1.compareTo(s2);
} else {
return o1.compareTo(o2);
}
}
});
floyd[st][st] = 0;
queue.add(st);
while (!queue.isEmpty()) {
int first = queue.first();
queue.remove(first);
for (int i = 0; i < 26; ++i) {
if (edges[first][i] != Integer.MAX_VALUE) {
if (floyd[st][i] > floyd[st][first] + edges[first][i]) {
queue.remove(i);
floyd[st][i] = floyd[st][first] + edges[first][i];
queue.add(i);
}
}
}
}
}
return floyd[st][ed];
}
}
public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
if (source.equals(target)) {
return 0;
}
int len = source.length();
PackedInfo info = new PackedInfo(original, changed, cost);
long[] dp = new long[len];
Arrays.fill(dp, -1);
for (int i = 0; i < len; ++i) {
if (source.charAt(i) == target.charAt(i)) {
if (i == 0) {
dp[i] = 0;
continue;
} else {
dp[i] = dp[i - 1];
}
}
int j = 1;
if (i - j + 1 == 0 || dp[i - j] != -1) {
long costChange = info.getBestDis(source.charAt(i) - 'a', target.charAt(i) - 'a');
if (costChange != Long.MAX_VALUE) {
if (dp[i] == -1) {
dp[i] = Long.MAX_VALUE;
}
dp[i] = Math.min(dp[i], costChange + (i - j + 1 == 0 ? 0 : dp[i - j]));
}
}
}
return dp[len - 1];
}
}100158. Minimum Cost to Convert String II
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。 你可以执行 任意数量 的操作，但是任两次操作必须满足 以下两个 条件 之一 ：
- 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 b < c 或 d < a 。换句话说，两次操作中选择的下标 不相交 。
- 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
测试样例：
输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe" ：
- 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。
- 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。
- 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。
- 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。可以证明这是可能的最小成本。
解答：操作需要满足2个条件，这两个条件暗示了可以使用动态规划。其他就和上一题比较类似了，寻找两点之间最短距离。
class Solution {
private class PackedInfo {
HashMap<String, Integer> wordOffset;
HashMap<Integer, List<int[]>> edges;
long[][] floyd;
Set<Integer> length;
String[] original, changed;
int[] cost;
public PackedInfo(String[] original, String[] changed, int[] cost) {
this.original = original;
this.changed = changed;
this.cost = cost;
length = new HashSet<>();
edges = new HashMap<>();
int offset = 0;
wordOffset = new HashMap<>();
for (int i = 0; i < original.length; ++i) {
if (!wordOffset.containsKey(original[i])) {
wordOffset.put(original[i], offset++);
}
if (!wordOffset.containsKey(changed[i])) {
wordOffset.put(changed[i], offset++);
}
length.add(original[i].length());
int p1 = wordOffset.get(original[i]), p2 = wordOffset.get(changed[i]);
if (!edges.containsKey(p1)) {
edges.put(p1, new ArrayList<>());
}
edges.get(p1).add(new int[]{wordOffset.get(changed[i]), cost[i]});
}
floyd = initialFloyd(offset);
}
private long[][] initialFloyd(int n) {
long[][] res = new long[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) res[i][j] = -1;
}
}
return res;
}
public long getBestDis(int st, int ed) {
if (floyd[st][ed] == -1) {
for (int i = 0; i < floyd.length; ++i) {
floyd[st][i] = Long.MAX_VALUE;
}
TreeSet<Integer> queue = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
Long s1 = floyd[st][o1], s2 = floyd[st][o2];
if (!s1.equals(s2)) {
return s1.compareTo(s2);
} else {
return o1.compareTo(o2);
}
}
});
floyd[st][st] = 0;
queue.add(st);
while (!queue.isEmpty()) {
int first = queue.first();
queue.remove(first);
if (edges.containsKey(first)) {
for (int[] next : edges.get(first)) {
if (floyd[st][next[0]] > floyd[st][first] + next[1]) {
queue.remove(next[0]);
floyd[st][next[0]] = floyd[st][first] + next[1];
queue.add(next[0]);
}
}
}
}
}
return floyd[st][ed];
}
}
public long minimumCost(String source, String target, String[] original, String[] changed, int[] cost) {
if (source.equals(target)) {
return 0;
}
int len = source.length();
PackedInfo info = new PackedInfo(original, changed, cost);
long[] dp = new long[len];
Arrays.fill(dp, -1);
for (int i = 0; i < len; ++i) {
if (source.charAt(i) == target.charAt(i)) {
if (i == 0) {
dp[i] = 0;
continue;
} else {
dp[i] = dp[i - 1];
}
}
for (int j : info.length) {
if (i + 1 - j >= 0) {
String key = source.substring(i - j + 1, i + 1);
String end = target.substring(i - j + 1, i + 1);
if (info.wordOffset.containsKey(key) && info.wordOffset.containsKey(end) &&
(i - j + 1 == 0 || dp[i - j] != -1)) {
long costChange = info.getBestDis(info.wordOffset.get(key), info.wordOffset.get(end));
if (costChange != Long.MAX_VALUE) {
if (dp[i] == -1) {
dp[i] = Long.MAX_VALUE;
}
dp[i] = Math.min(dp[i], costChange + (i - j + 1 == 0 ? 0 : dp[i - j]));
}
}
}
}
}
return dp[len - 1];
}
}