Java Program to Find the Earliest Time When a Frog Can Jump to The Other Side of a River

2025年3月26日 | 阅读 3 分钟

一只小青蛙有一个越过河流的任务。它最初位于一岸的 0 号位置，想要到达对岸的 X+1 号位置。河流表面会随着时间在不同位置落下树叶。

更具体地说，你有一个数组 A，其中每个元素表示一片叶子落入河流的时刻。目标是找出青蛙能够成功跳到河对岸的最早时刻。

青蛙需要有从 1 到 X 的所有位置都有叶子才能过河。水流速度可忽略不计，这意味着叶子一旦落下就不会移动。

示例

考虑 X=5 的情况，落叶数组 A 为

A=[1,3,1,4,2,3,5,4]

在这个例子中，在第 6 秒，一片叶子落在了 5 号位置，这使得从 1 到 5 的所有位置都得到了覆盖。因此，青蛙最早可以跳到对岸的时间是 6 秒。

算法

步骤 1: 创建一个空的 HashSet，命名为 positions，用于跟踪河流上必需的叶子位置。

步骤 2: 将从 1 到 X（含）的所有整数添加到 positions HashSet 中。这些代表需要被落叶覆盖的位置。

步骤 3: 遍历数组 A 中的每个元素，该元素表示叶子随时间落下的位置。如果该位置存在于 positions HashSet 中，则将其移除。

步骤 4: 每次移除后，检查 positions HashSet 是否为空。如果为空，则返回当前时间索引（time），表示所有必需的位置都已覆盖。

步骤 5: 如果循环完成后 positions HashSet 仍然不为空，则返回 -1，表示在数组结束时并非所有位置都被覆盖。

让我们在 Java 程序中实现上述步骤。

文件名: FrogJump.java

import java.util.HashSet; 
class FrogJump { 
// creating a function that takes an integer X and an array of integers A as inputs
    public int solution(int X, int[] A) { 
        // HashSet to keep track of covered positions
        HashSet<Integer> positions = new HashSet<>(); // Create a new HashSet to store the positions that need to be covered by leaves
        // Populate the HashSet with all positions that need to be covered
//Loop iterate over all the integers from 1 to X (inclusive)
        for (int i = 1; i <= X; i++) { 
            positions.add(i); // Add each integer (position) to the HashSet
        }
        // Iterate through the array A
        for (int time = 0; time < A.length; time++) { // Loop through each index in the array A
            // Remove the position from the HashSet if it's present
            positions.remove(A[time]); // Remove the position A[time] from the HashSet if it exists
            // If the HashSet is empty, it means all positions are covered
            if (positions.isEmpty()) { // Check if the HashSet is empty
                return time; // Return the current index (time) because all required positions are covered
            }
        }
        // If not all positions are covered by the end of the array, return -1
        return -1; // Return -1 if not all positions were reached by the end of the array
    }
    public static void main(String[] args) { 
        // Create an instance of FrogJump
        FrogJump sol = new FrogJump(); // Create a new instance of the FrogJump class
        //Example input
        int X = 5; // Define the number of positions (1 through X) that need to be covered
        int[] A = {1, 3, 1, 4, 2, 3, 5, 4}; // Create an array where every element denotes the location of a leaf dropping at a specific time index
        // Call the solution method and print the result
        int result = sol.solution(X, A); // Call the solution method with X and A and store the result in variable 'result'
        System.out.println("The earliest time the frog can jump is: " + result); // Print the result, showing the earliest time when all positions are covered
    }
}   

输出

 
The earliest time the frog can jump is: 6

下一个主题Java 中的 public 与 private 关键字

Java Program to Find the Earliest Time When a Frog Can Jump to The Other Side of a River

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java Program to Find the Earliest Time When a Frog Can Jump to The Other Side of a River

算法

相关帖子

Java 中使用 == 和 .equals() 方法比较 String 的区别

Prim's algorithm Java

Java 中的并行流

Java Developer Roles and Responsibilities

Java 中的字符串回文排列

PMD 是什么

Java 21 中的 Generational ZCG

How to Remove Last Character from String in Java

Float Vs Double Java

Count Total Set Bits in First Natural Numbers in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器