本文共 2956 字，大约阅读时间需要 9 分钟。

为了解决这个问题，我们需要找到从数组的第一个元素到最后一个元素的最少跳跃次数。每一步可以从当前位置跳到下一个位置（i+1），前一个位置（i-1），或者跳到与当前值相同的任一其他位置。

方法思路

我们可以使用双指针法来解决这个问题。双指针法通过记录每个数值的出现位置，来找到最少的跳跃次数。具体步骤如下：

这种方法确保了在最坏情况下也能高效处理，时间复杂度为O(n^2)，但由于优化，实际效率较高。

解决代码

import java.util.*;
public class Solution {
    public int MinJumps(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        // 创建字典，键是数值，值是该数值出现的位置列表
        Dictionary
   
    > dict = new Dictionary
    
     >();
        for (int i = arr.length - 1; i >= 0; i--) {
            if (!dict.containsKey(arr[i])) {
                dict.Add(arr[i], new List
     
      ());
            }
            dict[arr[i]].Add(i);
        }
        // 初始化数组r来记录访问状态，初始时只有位置0被访问
        boolean[] r = new boolean[arr.length];
        r[0] = true;
        // 初始化队列，并将起点加入队列
        Queue
      
        q = new LinkedList<>();
        q.add(0);
        int count = 0;
        int len = arr.length - 1;
        // 记录当前层的出队数和入队数
        int outCount = 0;
        int inCount = 1; // 初始时，出队数为0，入队数为1（起点）
        while (!q.isEmpty()) {
            // 处理当前层的出队数
            outCount = inCount;
            inCount = 0;
            while (outCount > 0) {
                int idx = q.Dequeue();
                outCount--;
                // 检查i+1位置
                if (idx + 1 < arr.length && !r[idx + 1]) {
                    r[idx + 1] = true;
                    q.add(idx + 1);
                    inCount++;
                    if (idx + 1 == len) {
                        return count + 1;
                    }
                }
                // 检查i-1位置
                if (idx - 1 >= 0 && !r[idx - 1]) {
                    r[idx - 1] = true;
                    q.add(idx - 1);
                    inCount++;
                    if (idx - 1 == len) {
                        return count + 1;
                    }
                }
                // 检查所有j位置，满足arr[idx] == arr[j]且j != idx
                List
       
         positions = dict.get(arr[idx]);
                for (int j : positions) {
                    if (j == idx) {
                        continue;
                    }
                    if (!r[j]) {
                        r[j] = true;
                        q.add(j);
                        inCount++;
                        if (j == len) {
                            return count + 1;
                        }
                    }
                }
            }
            // 处理下一个层次
            count++;
        }
        return count;
    }
}
       
      
     
    
   

代码解释

• 字典记录位置：字典dict记录了每个数值出现的位置，以便快速找到跳跃目标。
• 队列处理节点：队列q处理当前层的节点，确保每个节点只被处理一次。
• 跳跃处理：处理i+1、i-1和所有满足条件的j位置，确保所有可能的跳跃都被考虑。
• 优化处理：在处理j位置时，优先处理后面的位置，减少重复处理。

这种方法确保了在最少跳跃次数内到达数组的最后一个元素。