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

news/2024/11/8 1:29:34/

/*

题目出处: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.ppmy.cn/news/1545220.html

相关文章

苍穹外卖Day3test报错javax.websocket.server.ServerContainer not available

苍穹外卖Day3test报错javax.websocket.server.ServerContainer not available springboot 中集成websocket出的问题 测试会报错&#xff0c;启动程序不会报错 除了test的时候运行会报错&#xff0c;正常时候编写不会出错&#xff0c;不用管这个问题&#xff0c;继续往下进行…

简单又便宜的实现电脑远程开机唤醒方法

现有的远程开机方案 1&#xff09;使用向日葵开机棒 缺点是比较贵一点&#xff0c;开机棒要一百多&#xff0c;而且查了评论发现挺多差评说不稳定&#xff0c;会有断联和无法唤醒的情况&#xff0c;而且设置也麻烦&#xff0c;还需要网卡支持WOL 2&#xff09;使用远程开机卡 …

go实现并发安全hashtable 拉链法

在这个实现中&#xff0c;HashTable包含多个bucket&#xff0c;每个bucket都有一个互斥锁来保证并发安全。Put方法用于插入键值对&#xff0c;Get方法用于获取值&#xff0c;Delete方法用于删除键值对。通过哈希函数确定键应该存储在哪个bucket中&#xff0c;然后在对应的bucke…

微信小程序uniapp+vue飞机订票航空售票系统

文章目录 项目介绍具体实现截图技术介绍mvc设计模式小程序框架以及目录结构介绍错误处理和异常处理java类核心代码部分展示详细视频演示源码获取 项目介绍 对于小程序飞机订票信息管理所牵扯的信息管理及数据保存都是非常多的&#xff0c;举例像所有的管理员&#xff1b;管理员…

centos查看硬盘资源使用情况命令大全

在 CentOS 系统中&#xff0c;你可以使用几个命令来查看硬盘的资源和使用情况。以下是一些常用的命令&#xff1a; 1. df 命令 df (disk free) 用于显示文件系统的磁盘空间占用情况。 df -h-h 参数表示以人类可读的格式&#xff08;如 GB, MB&#xff09;显示。输出会显示每…

一:时序数据库-Influx应用

目录 0、版本号 1、登录页面 2、账号基本信息 3、数据库案例 4、可视化 5、java案例 0、版本号 InfluxDB v2.4.0 1、登录页面 http://127.0.0.1:8086/signin 账号&#xff1a;自己账号 密码&#xff1a;自己密码 2、账号基本信息 查看用户id和组织id&#xff01;&…

渗透测试-Linux基础(1)

声明 学习视频来自 B 站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 这里写目录标题 文件管理创建空文件删除…

(微服务)服务治理:几种开源限流算法库/应用软件介绍和使用

一、Go time/rate 限流器 1.1 简介 Go 在 x 标准库&#xff0c;即 golang.org/x/time/rate 里自带了一个限流器&#xff0c;这个限流器是基于令牌桶算法&#xff08;token bucket&#xff09;实现的。 在上一篇文章讲了几种限流算法&#xff0c;里面就有令牌桶算法&#xff…