字节跳动游戏服务端研发工程师笔试第三题

和leetcode45题有点像，类似BFS,终点确定，根据那个改了一下,每次确定当前一轮BFS左右能到达的最远距离，一旦右边的最远距离能够到达终点，输出即可...测试用例倒是通过了，但是不知道是不是正确，希望有大佬能够指点一下...

/**

• 3.2.马里奥
• 给定一个长度为N一维数组代表的路径，每个数组值（>=0）代表从该位置向前或者向后弹跳的最大步数（即：可以弹跳1到最大步之间）。如果是0，则代表是悬崖。马里奥开始会出生在一个随机的位置P。一维数组最右端的位置是终点（例如：10 0 2 1 1 0 1 终点）。现在求马里奥从出生点到达重点需要的最少弹跳次数。如果终点不可达，那么返回-1。
• 输入第一行路径长度和马里奥出生位置：N P
• 输入第二行：N个位置上的最大弹跳长度
• 输入样例：
• 7 4
• 10 0 2 1 1 0 1
• 输入样例：
• 3
• /
  public class Main3 {
  public static void main(String[] args) {

    Scanner in = new Scanner(new BufferedInputStream(System.in));
    int n = in.nextInt();
    int start = in.nextInt() - 1;
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
        nums[i] = in.nextInt();
    }
    // 这里我们指定左边的起始位置和右边的起始位置
    int left = start, right = start;
    // 左边和右边能够到达的最远距离
    int leftMax = start;
    int rightMax = start;
    // 类似BFS，即我们需要跳几步（可以去看下leetcode45讨论区的一个解法https://leetcode.com/problems/jump-game-ii/discuss/18028/O(n)-BFS-solution）
    int level = 0;
    // 只要左边还有能够到达的位置或者右边还有能够到达的位置
    while ((left >= leftMax && leftMax >= 0) || (right <= rightMax && rightMax <= n - 1)) {
        int leftFarDistance = leftMax;
        int rightFarDistance = rightMax;
        // 这里要注意左边能够达到的最远位置可能是left - nums[left]或者是right - nums[right]，右边同理
        while (left >= leftMax) {
            leftFarDistance = Math.min(leftFarDistance, left - nums[left]);
            rightFarDistance = Math.max(rightFarDistance, left + nums[left]);
            left--;
        }
        while (right <= rightMax) {
            leftFarDistance = Math.min(leftFarDistance, right - nums[right]);
            rightFarDistance = Math.max(rightFarDistance, right + nums[right]);
            // 找到就输出
            if (rightFarDistance >= n - 1) {
                System.out.println(level + 1);
                return;
            }
            right++;
        }
        level++;
        leftMax = leftFarDistance;
        rightMax = rightFarDistance;
    }
    System.out.println(-1);

  }
  }