1、题干
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1需满足：i + 1 < arr.lengthi - 1需满足：i - 1 >= 0j需满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：
输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
提示：
1 <= arr.length <= 5 * 104-108 <= arr[i] <= 108
DFS解法写自闭了，简单写下BFS和动态规划的思路和代码
2、解法1-BFS
BFS解法需要注意各种边界条件以及剪枝优化，不然很可能超时、内存溢出。剪枝的方法有这些：
- 跳过相邻且值相同的节点，只留头尾，中间部分没有意义
- 跳过已访问过的节点
- BFS的当前层级超过到达该节点的最小步数
3、代码
var minJumps = function (arr) {
const n = arr.length;
// 记录数字对应的索引以及最小步数
const map = new Map();
for (let i = 0; i < n; i++) {
if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
}
const visited = new Set();
let queue = [0], level = 0, res = Infinity;
while (queue.length) {
const set = new Set();
if (level >= res) break;
for (const i of queue) {
if (visited.has(i)) continue;
visited.add(i);
if (i === n - 1) res = Math.min(res, level);
if (i >= 1) set.add(i - 1);
if (i <= n - 2) set.add(i + 1);
const [idxs, min] = map.get(arr[i]);
if (level + 1 > min) continue;
map.get(arr[i])[1] = Math.min(min, level + 1);
for (const x of idxs) {
if (x !== i) set.add(x);
}
}
queue = [...set];
level++;
}
return res;
};
4、执行结果
- 执行用时: 180 ms
- 内存消耗: 62.3 MB
5、解法2-动态规划
实际上这道题不能用动态规划，因为违反了无后效性，其实带来的问题就是不能一次性规划出结果，这个问题没啥好办法，多规几次就出来了（两次动态规划结果一致则认为已经是最优解）。
6、代码
var minJumps = function (arr) {
const n = arr.length;
// 记录数字对应的索引
const map = new Map();
for (let i = 0; i < n; i++) {
map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
}
// DP处理
const dp = new Array(n).fill(Infinity);
dp[0] = 0;
function updateSame(i) {
const [idxs, min] = map.get(arr[i]);
if (idxs.length < 2 || dp[i] >= min) return;
map.get(arr[i])[1] = dp[i];
for (let j = 0; j < idxs.length; j++) {
dp[idxs[j]] = Math.min(dp[i] + 1, dp[idxs[j]]);
}
}
function runDp() {
for (let i = 0; i < n; i++) {
if (i > 0) dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]), updateSame(i - 1);
if (i < n - 1) dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]), updateSame(i + 1);
updateSame(i);
}
}
while (1) {
runDp();
const r1 = dp.toString();
runDp();
const r2 = dp.toString();
if (r1 === r2) return dp[n - 1];
}
};
7、执行结果
- 执行用时: 380 ms
- 内存消耗: 65.1 MB
8、解法3-DFS
各种处理和优化，最终还是没能AC，直接贴代码吧，如果有大神看到希望指点下🙏
var minJumps = function (arr) {
const n = arr.length;
// 记录数字对应的索引以及最小步数
const map = new Map();
for (let i = 0; i < n; i++) {
if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [
[i], Infinity
]);
}
let res = Infinity;
function dfs(i, path) {
if (i === n - 1) return res = Math.min(res, path.size);
if (i < 0 || i > n - 1 || path.has(i)) return;
const [idxs, min] = map.get(arr[i]);
if (path.size >= min || path.size + 1 >= res) return;
path.add(i);
for (let j = 0; idxs.length > 1 && j < idxs.length; j++) {
if (i !== idxs[j]) dfs(idxs[j], path);
}
dfs(i - 1, path);
dfs(i + 1, path);
map.get(arr[i])[1] = Math.min(map.get(arr[i])[1], path.size);
path.delete(i);
}
return dfs(0, new Set()), res;
};
