首页 > 编程语言 >力扣面试经典算法150题:跳跃游戏

力扣面试经典算法150题:跳跃游戏

时间:2024-08-21 19:51:42浏览次数:12  
标签:150 下标 nums maxReach 力扣 面试 数组 题目 false

跳跃游戏

今天的题目是力扣面试经典150题中的数组的中等难度题:跳跃游戏。

题目链接:https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

给定一个非负整数数组 nums,你最初位于数组的 第一个下标,即 nums[0] 。数组中的每个元素代表一个障碍的高度。

你想要到达最后一个下标,但是除了从下标 i 跳到下标 i + nums[i] 之外,你不能跳过任何下标。

确定你是否能够到达最后一个下标。

  • 示例 1:

    • 输入: [2,3,1,1,4]
    • 输出: true
  • 示例 2:

    • 输入: [3,2,1,0,4]
    • 输出: false

题目分析

题目要求我们判断在一个障碍高度数组中,从起点能否跳到最后一个位置。

题目的意思就是给定一个数组,我们从数组的第一个下标位置开始,根据下标元素的值x,我们可以向前移动下标,移动区间为(1,x]。如果当下下标的值是0,那么将无法向前移动,这个时候跳跃游戏结束,结束时所在下标如果不是最后一个下标,就返回false。

解题思路

这种情况我们可以直接考虑贪心算法,就是每次都走最大步,看看能不能出去游戏。

首先我们定义一个最大移动距离,初始值时0,因为还没有开始移动。

开始进行循环,从第一个元素开始。

当第一个值时0且长度大于1时,可以直接返回,因为无法移动。

定义结束条件,当你最大移动的距离小于当前下标的值,说明你已经无法移动了,可以直接返回false。

下面我们需要更新最大距离。在每次都走最大步长的情况下,最大距离就等于下标的值加上元素的值,这个时候与当前的距离取大即可。

最后看看如果当前最大距离已经超过了数组长度,说明已经到了终点,返回true。

实际算法代码
以下是使用上述思路的 Java 实现:

public class JumpGame {

	public static void main(String[] args) {
        JumpGame solution = new JumpGame();
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println(solution.canJump(nums1)); // 输出: true
        System.out.println(solution.canJump(nums2)); // 输出: false
    }

    public boolean canJump(int[] nums) {
        int maxReach = 0;
        if (nums.length == 1) {
			return true;
		}
        for (int i = 0; i < nums.length; i++) {
        	if (nums.length > 1 && num[i] == 0) {
				return false;
			}
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return maxReach >= nums.length - 1;
    }
}

结果

执行程序,测试通过:
在这里插入图片描述

提交到力扣,也通过,并且表现不错。

在这里插入图片描述

总结

又是使用贪心算法的一天。这个题目和股票买卖的有一个共同点,也是常见使用贪心算法的场景。那就是通过局部的最优解进而实现整体的最优解。

在股票买卖中,我们通过每次都能获取利润从而获取最大的利润,在今天的跳跃游戏中,我们每次都走最远从而跳出数组。学会从题目归纳场景,在用场景归纳出解题思路,这是刷算法要得到的收获,不是做完题目就行,归纳总结,这是才是正经学习!

加油!!!

标签:150,下标,nums,maxReach,力扣,面试,数组,题目,false
From: https://blog.csdn.net/weixin_48668564/article/details/141376243

相关文章

  • 高级java每日一道面试题-2024年8月21日-框架篇[Spring篇]-使用IOC容器应该注意哪些?
    如果有遗漏,评论区告诉我进行补充面试官:使用IOC容器应该注意哪些?我回答:1.理解IOC的基本概念控制反转:在传统的编程模式中,程序会主动控制依赖关系的创建和管理。而在IoC容器中,这种控制权被反转给了容器本身。程序员只需要声明依赖关系,而由容器负责实例化和注入这些依......
  • Java笔试面试题AI答之集合(1)
    文章目录1.Java集合类框架的基本接口有哪些?2.为什么Java集合类没有实现Cloneable和Serializable接口?关于Cloneable接口关于Serializable接口为什么不默认实现这些接口?3.Java中的HashMap的工作原理是什么?1.数据结构2.哈希函数3.处理哈希冲突4.动态扩容5.Java8......
  • leetcode面试经典150题- 3. 无重复字符的最长子串
    https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150  packageleetcode150import"testing"funcTestLengthOfLongestSubstring(t*testing.T){s:=&qu......
  • 面试+算法之动态规划(Java):斐波那契、背包问题、走棋盘、分苹果、连续子数组最大和、
    概述Dynamicprogramming,简称DP,动态规划,基础算法之一,维基百科的解释:是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时......
  • 面试+算法之回文(Java):验证回文串、回文数、最长回文子串、回文链表、分割成回文串、
    概述算法是一个程序员的核心竞争力,也是面试最重要的考查环节。本文整理一些与回文相关的基础算法题。注:本文语言为Java。验证回文串如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。给定一个字符......
  • 面试必备之线程池
    概述在Java中要想实现线程,有四种手段:继承Thread类实现java.lang.Runnable接口实现java.util.concurrent.Callable泛型接口,利用线程池线程池通过线程复用机制,并对线程进行统一管理,优点:降低系统资源消耗。通过复用已存在的线程,降低线程创建和销毁造成的消耗;提高响应速度......
  • 前端高频面试题整理
    1.在React中,如何检验props?为什么要验证props?在React中,你可以使用PropTypes库来检查组件的props。这可以确保组件收到的props类型正确,避免在应用运行过程中出现意外错误。具体的做法是导入PropTypes库,并为每个prop定义相应的类型和是否必需。首先,你需要安装prop......
  • Java面试八股文 非常详细了!!!
    准备篇Java程序员的面试过程——总分结构凡事预则立,不预则废应届生该如何找到合适的练手项目Redis篇面试考点——一、缓存面试官:什么是缓存穿透 ?怎么解决?候选人:(穿透无中生有Key,布隆过滤NULL隔离)嗯~~,我想一下缓存穿透是指查询一个一定不存在的数据,如果从存储......
  • 面试题:求[2, n)之间的素数个数
    题目:求[2,n)之间的素数个数素数的定义:素数是指大于1的自然数,除了1和它本身之外没有其他因数的数。也就是说,素数只能被1和它本身整除,不能被其他自然数整除。解法1最简单的实现思路是,实现素数判断函数,然后从2~n逐个判断,然后统计素数个数publicstaticintcountP......
  • go 面试资料整理
    go语言基础熟悉语法,撸个百十道基础面试题就差不多了。go语言进阶go中有哪些锁?sync.Mutex互斥锁sync.RWMutex读写锁CSP并发模型?CSP并发模型它并不关注发送消息的实体,而关注的是发送消息时使用的channel,go语言借用了proce......