解法一:穷举法题目描述:给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
最后,如果队列为空了还没有跳到数组的最后一位,则返回false。
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class LeetCode_055 {
public static boolean canJump(int[] nums) {
if (nums.length == 1) {
return true;
}
if (nums[0] == 0) {
return false;
}
int length = nums.length - 1;
// 定义走到过的位置
Set<Integer> jumped = new HashSet<>();
jumped.add(0);
// 定义当前到的位置
Queue<Integer> toJump = new LinkedList<>();
toJump.add(0);
while (!toJump.isEmpty()) {
Integer cur = toJump.poll();
jumped.add(cur);
if (nums[cur] == 0) {
continue;
}
if (nums[cur] >= length - cur) {
return true;
} else {
for (int i = nums[cur]; i >= 1; i--) {
if (!jumped.contains(cur i) && !toJump.contains(cur i)) {
toJump.add(cur i);
}
}
}
}
return false;
}
public static void main(String[] args) {
int[] nums = new int[]{2, 3, 1, 1, 4};
System.out.println(canJump(nums));
}
}
【每日寄语】 好的运气从清晨开始,愿你晨起有微笑,笑里有幸福。
Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved