python-----贪心

蔚落 2022-06-08 12:29 160阅读 0赞

给定一个非负整数数组，假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

请确认你是否能够跳跃到数组的最后一个下标。

例如：A = \[2,3,1,1,4\]*A*=\[2,3,1,1,4\] 能够跳跃到最后一个下标，输出`true`；

A = \[3,2,1,0,4\]*A*=\[3,2,1,0,4\] 不能跳跃到最后一个下标，输出`false`。

### 输入格式 ###

第一行输入一个正整数 n(1 \\leq n \\leq 500)*n*(1≤*n*≤500)，接下来的一行 n*n* 个整数，输入数组 A\_i*A**i*。

### 输出格式 ###

如果能跳到最后一个下标，输出`true`，否则输出`false`。

#### 样例输入 ####

5
    2 0 2 0 1

#### 样例输出 ####

true

python语言：

a=[0]*501
    i=maxx=ok=0
    n=int(input())
    a=input().split(' ')
    # print(a)
    for i in range(0,n):
        if i>maxx:
            print("false")
            ok=1
            break
        if i+int(a[i])>maxx:
            maxx=i+int(a[i])
    if ok==0:
        print("true")

java语言：

import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int count, i, max = 0;
    		Scanner stdin = new Scanner(System.in);
    		count = stdin.nextInt();
    		int[] a = new int[501];
    		for (i = 0; i < count; i++) {
    			a[i] = stdin.nextInt();
    		}
    		for (i = 0; i < count; i++) {
    			if (max<i) {
    				System.out.println("false");
    				return;
    			}
    			if (i + a[i] > max)
    				max = i + a[i];
    		}
    		System.out.println("true");
    	}
    
    }

思路：

如果存在某一点不能到达后面的点，那肯定不能到达最后的点,输出false，否则输出true

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 python算法技巧——贪心算法练习及掌握

目录 1. 设计findcontentchildren(greedy, size)来判断出饼干可以满足多少小孩： 2. 设计carpooling(trips, capaci

柔情只为你懂/ 2023年09月29日 12:57/ 0 赞/ 49 阅读

相关 python实现贪心算法

> 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。 1. 贪心算法思想贪心算法的基

╰半夏微凉°/ 2022年11月12日 12:59/ 0 赞/ 208 阅读

相关牛客网---贪心算法（python实现）

不贪心如何拿Offer 一：股票交易的最大收益：二：换酒问题：三：分发饼干：一：股票交易的最大收益：假定你知道某只

缺乏、安全感/ 2022年11月05日 08:52/ 0 赞/ 204 阅读

相关 Python|你真“贪心”之买股票

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。引言当今社会很多人都喜欢选择一种投资方式—买股票。股票波动比较大，自然风险也很高，当然如

╰+攻爆jí腚メ/ 2022年10月09日 00:53/ 0 赞/ 138 阅读

相关 python-----贪心

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。例如：A =

蔚落/ 2022年06月08日 12:29/ 0 赞/ 161 阅读

相关贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。举一个简单的贪心法例子，平时

本是古典何须时尚/ 2022年06月06日 03:11/ 0 赞/ 303 阅读

相关 python——三道贪心算法例题

1.找零钱问题：假设只有 1 分、 2 分、五分、 1 角、二角、五角、 1元的硬币。在超市结账时，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找

约定不等于承诺〃/ 2022年06月06日 00:08/ 0 赞/ 188 阅读

相关 P1080 国王游戏——————贪心，高精度，python

[P1080 国王游戏][P1080] 题目描述恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己

た入场券/ 2022年03月31日 13:54/ 0 赞/ 231 阅读

相关贪心算法

1.钞票支付问题，1元，2元，5元，10元，20元，50元，100元钞票无穷张，使用这些钞票怎么支付，最少需要多少张。思路：尽可能使用面额较大的金额数目。反证法：若不成立，

深碍√TFBOYSˉ_/ 2022年02月22日 08:49/ 0 赞/ 309 阅读

相关贪心算法

贪心算法概念设计贪心算法的步骤案例剪绳子问题描述解决思路代码实

我就是我/ 2021年11月04日 13:48/ 0 赞/ 457 阅读