欢迎大家加QQ群：623375442，可以方便群里面交流。
100296. Permutation Difference between Two Strings
给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。
排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。
返回 s 和 t 之间的 排列差 。
测试样例：
输入：s = "abc", t = "bac"
输出：2
解释：对于 s = "abc" 和 t = "bac"，排列差是：
- "a" 在 s 中的位置与在 t 中的位置之差的绝对值。
- "b" 在 s 中的位置与在 t 中的位置之差的绝对值。
- "c" 在 s 中的位置与在 t 中的位置之差的绝对值。
即，s 和 t 的排列差等于 |0 - 1| + |2 - 2| + |1 - 0| = 2。
解答：这个范围小的可怜，直接暴力遍历，枚举计算。
class Solution {
public int findPermutationDifference(String s, String t) {
int res = 0;
for (int i = 0; i < s.length(); ++i) {
for (int j = 0; j < t.length(); ++j) {
if (s.charAt(i) == t.charAt(j)) {
res += Math.abs(i - j);
}
}
}
return res;
}
}100274. Taking Maximum Energy From the Mystic Dungeon
在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。
你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。
换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。
给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。
测试样例：
输入：energy = [5,2,-10,-5,1], k = 3
输出：3
解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。
解答：有这个条件：你将被立即传送到魔法师 (i + k) 处，并且直到(i + k) 不存在位置。所以从队尾开始计算，遍历最后k的元素，然后滚动向前看看最大值是多少。
class Solution {
public int maximumEnergy(int[] energy, int k) {
int max = Integer.MIN_VALUE;
for (int i = energy.length - 1, j = 0; i >= 0 && j < k; --i, ++j) {
int tmp = 0, p = i;
while (p >= 0) {
tmp += energy[p];
p -= k;
max = Math.max(max, tmp);
}
}
return max;
}
}100281. Maximum Difference Score in a Grid
给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。
你可以从 任一 单元格开始，并且必须至少移动一次。
返回你能得到的 最大 总得分。
测试样例：
输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
输出：9
解释：从单元格 (0, 1) 开始，并执行以下移动：
- 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。
- 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。
总得分为 2 + 7 = 9 。
解答：这题重点是寻找一个数，右下角的最小值。c2 - c1这个遍历公式可以知道整个路径上，只有第一个和最后一个单元格的值有效。
class Solution {
public int maxScore(List<List<Integer>> _grid) {
int m = _grid.size(), n = _grid.get(0).size();
int[][] grid = buildMatrix(_grid);
int res = Integer.MIN_VALUE;
int[] mem = new int[n];
for (int i = m - 1; i >= 0; --i) {
int best = 0;
for (int j = n - 1; j >= 0; --j) {
best = Math.max(best, mem[j]);
// WA 一次，(m - 1, n - 1)这个比较特殊，它无法作为起始点，所以不能取一次极值。
if (i != m - 1 || j != n - 1) {
res = Math.max(res, best - grid[i][j]);
}
best = Math.max(best, grid[i][j]);
mem[j] = Math.max(mem[j], best);
}
}
return res;
}
private int[][] buildMatrix(List<List<Integer>> _grid) {
int m = _grid.size(), n = _grid.get(0).size();
int[][] grid = new int[m][n];
int p1 = 0;
for (List<Integer> r : _grid) {
int p2 = 0;
for (int num : r) {
grid[p1][p2++] = num;
}
++p1;
}
return grid;
}
}100312. Find the Minimum Cost Array Permutation
给你一个数组 nums ，它是 [0, 1, 2, ..., n - 1] 的一个排列 。对于任意一个 [0, 1, 2, ..., n - 1] 的排列 perm ，其 分数 定义为：
score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|
返回具有 最低 分数的排列 perm 。如果存在多个满足题意且分数相等的排列，则返回其中字典序最小的一个。
测试样例：
输入：nums = [1,0,2]
输出：[0,1,2]
解释：字典序最小且分数最低的排列是 [0,1,2]。这个排列的分数是 |0 - 0| + |1 - 2| + |2 - 1| = 2 。
解答：这题稍微有点难，一开始我想多了。开始的第一个数字必然是0（因为数字可以随便摆放，第一个放0可以确保字典序最小）。之后就是利用动态规划，计算最小值了。
class Solution {
private class Data {
int[] nums, res;
int len, max;
int bestResult;
public Data(int[] nums) {
this.nums = nums;
len = nums.length;
max = 1 << len;
bestResult = Integer.MAX_VALUE;
}
}
public int[] findPermutation(int[] nums) {
Data data = new Data(nums);
// 只需要计算0，否则会超时。
bestWithDedicateZero(data, 0);
return data.res;
}
private void bestWithDedicateZero(Data data, int start) {
Integer[][][] mem = new Integer[data.len][data.max][4];
mem[start][1 << start][0] = 0;
List<Integer> last = new ArrayList<>();
last.add(1 << start);
for (int i = data.len - 1; i >= 0; --i) {
Set<Integer> cur = new HashSet<>();
for (int n : last) {
if (i == 0) {
// 初始位置比较特殊，它一定是传入的第一个start数字
int[] best = {Integer.MAX_VALUE, -1, -1};
for (int k = 0; k < data.len; ++k) {
if (mem[k][n][0] == null) {
continue;
}
int curMin = Math.abs(start - data.nums[k]) + mem[k][n][0];
if (best[0] > curMin) {
best[0] = curMin;
best[1] = k;
best[2] = n;
} else if (best[0] == curMin && best[1] > k) {
best[1] = k;
}
}
// 如果best变小，那就对data上的res赋值。
// 一开始没想明白为啥0一定最优，所以留了start接口。
if (best[0] < data.bestResult) {
data.bestResult = best[0];
int[] res = new int[data.len];
res[0] = start;
Integer p1 = best[1], p2 = best[2];
for (int j = 1; j < data.len; ++j) {
res[j] = p1;
Integer tmp = mem[p1][p2][1];
p2 = mem[p1][p2][2];
p1 = tmp;
}
data.res = res;
}
} else {
// 动态规划，查询之前遍历过的位置，然后计算下一个位置最小值和转移过程。
for (int j = 0; j < data.len; ++j) {
if (j == start) {
continue;
}
if (!isUsed(n, j)) {
int next = (1 << j) + n;
for (int k = 0; k < data.len; ++k) {
if (mem[k][n][0] != null && isUsed(n, k)) {
int curMin = Math.abs(j - data.nums[k]) + mem[k][n][0];
if (mem[j][next][0] == null || mem[j][next][0] > curMin) {
mem[j][next][0] = curMin;
mem[j][next][1] = k;
mem[j][next][2] = n;
cur.add(next);
} else if (mem[j][next][0] == curMin && mem[j][next][1] > k) {
mem[j][next][1] = k;
}
}
}
}
}
}
}
last = new ArrayList<>(cur);
}
}
private boolean isUsed(int num, int offset) {
int tmp = (num >> offset) & 1;
return tmp == 1;
}
}