[LeetCode-45] 基于贪心算法的跳跃游戏 II-最少跳跃次数的求解(C语言版)

/*

题目出处:LeetCode

题目序号:45. 跳跃游戏 II

题目叙述给定一个长度为 n 的整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处,返回到达 nums[n - 1] 最小跳跃次数

*/

贪心策略

每次跳跃从可选择的位置中选择跳到可以达到最远距离的位置。

思路:

1)每次 index 变动时,跳跃次数加 1

2)结束条件判定:当 jump[ index ] length 时,跳跃次数 1 结束

程序清单

#include<stdio.h>

#define OK 1
typedef int Status;

Status TestJumpTimes(int *nums, int length) {
    int i; 
    int count = 0;        // 跳跃次数 
    int index = 0;        // 起点位置
    int jump[length];    // 记录当前位置可达到的最远距离 
    for(i = 0; i < length; i++){
        jump[i] = i + nums[i];
    } 
    if (length == 1) {
        printf("您已在终点,无需跳跃,所需的最少跳跃次数为 0 次。");    // 如果起始位置就是终点,则可以到达 
        return OK;
    }
    while(jump[index] < length - 1){
        int left = index + 1;
        int right =  jump[index]; 
        int temp = left;                        // 保存最远位置对应的索引 
        while (left < right) {                    // 寻找可跳的位置 
            if(jump[temp] < jump[left + 1]) {    
                temp = left + 1;
            }
            left++;
        }
        printf("\n");
        index = temp;         // 跳跃 
        count++;            // 跳跃次数加 1 
    }
    count = count + 1;        // 最后一次跳跃 
    printf("所需的最少跳跃次数为 %d 次。", count);
    return OK;
}

int main() {
    int n,i;
    printf("请输入您想测试的数组的长度:\n");
    scanf("%d",&n);
    int a[n];
    printf("请输入数组元素:\n");
    for (i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    TestJumpTimes(a,n);
    return 0;
}

运行结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/5943.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

数据结构 —— 红黑树

目录 1. 初识红黑树 1.1 红黑树的概念 1.2 红⿊树的规则 1.3 红黑树如何确保最长路径不超过最短路径的2倍 1.4 红黑树的效率:O(logN) 2. 红黑树的实现 2.1 红黑树的基础结构框架 2.2 红黑树的插⼊ 2.2.1 情况1&#xff1a;变色 2.2.2 情况2&#xff1a;单旋变色 2.2…

第J9周:Inception v3算法实战与解析(pytorch版)

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营]中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊]** &#x1f4cc;本周任务&#xff1a;&#x1f4cc; 了解并学习InceptionV3相对与InceptionV1有哪些改进的地方 使用Inception完成天气…

什么是 AWS PrivateLink

您可以使用 Amazon VPC 定义虚拟私有云&#xff08;VPC&#xff09;&#xff0c;这是一个逻辑隔离虚拟网络。您可以在 VPC 中启动 AWS 资源。您可以允许 VPC 中的资源连接到该 VPC 外部的资源。例如&#xff0c;向 VPC 添加互联网网关以允许访问互联网&#xff0c;或添加 VPN 连…

vue2 -- el-form组件动态增减表单项及表单项验证

需求 在数据录入场景(如订单信息录入)中,可根据实际情况(如商品种类增加)动态添加表单项(如商品相关信息)。包含必填项验证和数据格式验证(如邮箱、电话格式),防止错误数据提交。 效果 代码一 <template><div>

旧衣回收小程序:提高回收效率,扩大服务范围

近年来&#xff0c;旧衣回收作为一种新兴回收模式&#xff0c;逐渐走入了大众的生活中&#xff0c;在回收市场中形成了新的商业模式&#xff0c;也为大众带来了新的创业选择。 随着社会生活的快速发展&#xff0c;人们的生活水平不断提高&#xff0c;为旧衣市场发展提供了基础…

电子电气架构 --- Trace 32(劳特巴赫)多核系统的调试

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…

使用C++和QT开发应用程序入门以及开发实例分享

目录 1、搭建开发环境&#xff08;VS2010和QT4.8.2&#xff09; 2、创建一个QT窗口 3、在QT窗口中添加子窗口 4、QT界面布局 5、QT信号&#xff08;SIGNAL&#xff09;和槽&#xff08;SLOT&#xff09; 6、最后 C软件异常排查从入门到精通系列教程&#xff08;专栏文章列…

1553B总线协议

参考地址 MIL-STD-1553B时分制指令/响应多路传输数据总线采用半双工传输方式。 1553B总线协议概述 1553B总线协议是一种军用标准&#xff0c;主要用于飞机上的设备间的信息传输。这种协议由美国军方制定&#xff0c;被广泛应用于航空、航天和军事领域的电子联网系统中。1553B…

LVI-GS:港大待开源、雷达-视觉-惯紧耦合,实时渲染

文章目录 摘要一、 介绍二、相关工作A 基于NeRF的SLAMB 基于3DGS的SLAM 三、方法A 超原语B. 3D 高斯投影C. 关键帧管理D. 基于金字塔的训练E. 高斯映射 四、实验 摘要 文章&#xff1a;github 介绍&#xff1a;介绍 3D高斯溅射&#xff08;3DGS&#xff09;在快速渲染和高保真…

2024年中国AI大模型场景应用趋势蓝皮书【附47页PPT】

目录 01 AI大模型行业应用概况 02 AI大模型行业应用现状及案例 03 AI大模型行业应用痛点及解决方案 04 AI大模型行业应用前景趋势及投资机会分析 如何学习AI大模型 &#xff1f; “最先掌握AI的人&#xff0c;将会比较晚掌握AI的人有竞争优势”。 这句话&#xff0c;放在…

基于Zynq FPGA对雷龙SD NAND的测试

一、SD NAND 特征 1.1 SD 卡简介 雷龙的 SD NAND 有很多型号&#xff0c;在测试中使用的是 CSNP4GCR01-AMW 与 CSNP32GCR01-AOW。芯片是基于 NAND FLASH 和 SD 控制器实现的 SD 卡。具有强大的坏块管理和纠错功能&#xff0c;并且在意外掉电的情况下同样能保证数据的安全。 …

Spring Boot框架下的教育导师匹配系统

第一章 绪论 1.1 选题背景 如今的信息时代&#xff0c;对信息的共享性&#xff0c;信息的流通性有着较高要求&#xff0c;尽管身边每时每刻都在产生大量信息&#xff0c;这些信息也都会在短时间内得到处理&#xff0c;并迅速传播。因为很多时候&#xff0c;管理层决策需要大量信…

鉴源实验室·加密技术在汽车系统中的应用

随着汽车技术的快速发展&#xff0c;现代汽车已经不再是简单的交通工具&#xff0c;而是融合了多种智能功能的移动终端。无论是自动驾驶、车联网&#xff08;V2X&#xff09;&#xff0c;还是车内娱乐系统&#xff0c;数据传输和存储已经成为汽车生态系统中的关键环节。然而&am…

Oracle数据库是什么?

Oracle Database&#xff0c;又名 Oracle RDBMS&#xff0c;简称 Oracle。Oracle 数据库系统是美国 Oracle 公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是目前最流行的客户/服务器&#xff08;client/server&#xff09;或B/S体系…

利用Docker Compose构建微服务架构

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 利用Docker Compose构建微服务架构 引言 Docker Compose 简介 安装 Docker Compose 创建项目结构 编写 Dockerfile 前端 Dockerf…

macOS15.1及以上系统bug:开发者证书无法打开,钥匙串访问无法打开一直出现图标后立马闪退

团队紧跟苹果最新系统发现bug:今日设备信息如下,希望能带给遇到这个问题的开发者一点帮助。 错误图如下: 点击证书文件后,先出现钥匙串访问图标,后立马闪退消失 中间试过很多方法,都是一样的表现,最后好在解决了,看网上也没有相关的帖子,这里直接写解决办法和导致原因…

牵手APP引领交友新风尚,多元匹配助力寻找心仪伴侣

第54次《中国互联网络发展状况统计报告》数据显示&#xff0c;截至2024年6月&#xff0c;我国网民规模近11亿人&#xff0c;互联网普及率达78.0%。网络平台的普及&#xff0c;在便捷生活的同时&#xff0c;也衍生出一系列全新的领域与服务生态。如今&#xff0c;线上交友作为一…

C#WPF使用CommunityToolkit.Mvvm库

C#WPF之快速理解MVVM模式 接上篇介绍MVVM&#xff0c;这里使用相关库介绍MVVM。 CommunityToolkit.Mvvm CommunityToolkit.Mvvm介绍 CommunityToolkit.Mvvm是Microsoft Community Toolkit的一部分&#xff0c;它是一个轻量级但功能强大的MVVM&#xff08;Model-View-ViewMod…

Pr 视频效果:ASC CDL

视频效果/颜色校正/ASC CDL Color Correction/ASC CDL ASC CDL ASC CDL效果通过对红、绿、蓝三个原色通道的独立调整&#xff0c;实现对图像色彩的精确控制。在此基础上&#xff0c;还可用于调整处理后图像的整体饱和度。 ◆ ◆ ◆ 效果选项说明 斜率 Slope、偏移 Offset和功…

【Linux】网络编程:应用层协议—HTTP协议(超详细)

目录 一、HTTP协议概念 HTTP协议的基本概念 HTTP的工作流程 二、认识URL URL 的基本结构 URLencode与URLdecode 三、认识HTTP协议 四、HTTP请求格式 1. 请求行&#xff08;Request Line&#xff09; 2. 请求报头&#xff08;Request Headers&#xff09; 3. 空行&a…