mzoe666888

V1

2022/04/15阅读:24主题:兰青

内卷大厂系列《跳跃游戏三连击》

大厂高频算法面试题:《跳跃游戏系列》,您将学到如何定义变量,实现巧妙的解法,其核心是定义变量时,除了要符合题意外,其次能达到想要的目的就行,快来一起学习吧!

一、跳跃游戏 I

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

leetcode

1、分析

小人从0位置想跳到N-1位置,数组中的值代表能跳的最大步数

数组下标换算问题,设置一个变量max,代表能跳到右侧的最大位置

2、实现

public static boolean canJump(int[] nums) {
    if (nums == null || nums.length < 2) {
        return true;
    }
    // max代表能跳到右侧的最大位置
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (i > max) {
            return false;
        }
        max = Math.max(max, i + nums[i]);
    }
    return true;
}

二、跳跃游戏 II

给你一个非负整数数组 nums ,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

leetcode

1、分析

跳跃步数:不是跳跃一步的含义,比如1步内最远能跳到哪的意思。

设置三个变量,step跳跃步数,cur当前跳跃步数内最远能到哪,next下一步最远能跳到哪

几步跳跃(step)能到达最右位置(cur),再跳一次能到达最右位置(next)

step、cur、next的初始值如下:

0步跳跃step=0,能到达最右位置cur=0,在跳一步能到达最右位置next=arr[0]

  • step:当前最少跳跃步数能到i位置
  • cur:跳跃的步数不超过step,最右能到哪个位置
  • next:跳跃的步数不超过step+1,最右能到哪个位置

i > cur,说明step步不足以到i,step++,增加步数(跳跃次数),cur = next,说白了next就是提前准备好,为了下次step cover不住的时候,next给cur

i ≤ cur,说明step步内还能到i,能cover住,看能不能更新next(next = max(next, i+arr[i])),next得时刻注意能不能变的更远

2、实现

public static int jump(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int step = 0;
    int cur = 0;
    int next = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (cur < i) {
            step++;
            cur = next;
        }
        next = Math.max(next, i + arr[i]);
    }
    return step;
}

三、跳跃游戏 III

这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可 以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意,不管是什么情况下,你都无法跳到数组之外。

示例 1

输入:arr = [4,2,3,0,3,1,2], start = 5
输出:true
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

示例 2

输入:arr = [4,2,3,0,3,1,2], start = 0
输出:true 
解释:
到达值为 0 的下标 3 有以下可能方案: 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3

输入:arr = [3,0,2,1,2], start = 2
输出:false
解释:无法到达值为 0 的下标 1 处。 

leetcode

1、分析

当前来到i位置,只有两种选择,往左跳或往右跳,类似二叉树。

宽度优先遍历(队列)的作用:二叉树,两个分支,既可以往左边走(left),又可以往右边走(right)

  • key:数组下标,value:层数
  • 去重,记录走过的决策

2、实现

public static boolean canReach(int[] arr, int start) {
    if (arr == null || start < 0 || start > arr.length - 1) {
        return false;
    }
    // 通过队列实现宽度优先遍历
    Queue<Integer> queue = new LinkedList<>();
    // 按层遍历
    HashMap<Integer, Integer> levelMap = new HashMap<>();
    queue.add(start);
    levelMap.put(start, 0);
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        int level = levelMap.get(cur);
        if (cur + arr[cur] < arr.length && arr[cur + arr[cur]] == 0) {
            return true;
        } else {
            int left = cur - arr[cur];
            if (left >= 0 && !levelMap.containsKey(left)) {
                queue.add(left);
                levelMap.put(left, level + 1);
            }
            int right = cur + arr[cur];
            if (right < arr.length && !levelMap.containsKey(right)) {
                queue.add(right);
                levelMap.put(right, level + 1);
            }
        }
    }
    return false;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1