使用Java实现Frog River One算法

[LOADING...]

1. 简介

在本教程中，我们将学习 Frog River One（青蛙过河） 问题。

2. 问题陈述

在这个问题中，一只青蛙想要过河。只有当有一条连接两岸的叶子路径时，它才能过河。随着叶子从附近的树上落下，路径最终会形成，青蛙也就能过河了。问题是什么时候能过河。

形式上，河流就像一个包含 m 个位置的序列：起始位置为 1，目的地对应 m。一个非空数组 leaves 包含 n 个整数（从 1 到 m），其中 leaves[k] 表示在时间步 k 时叶子落下的位置。我们假设 n >= m，并从 0 开始计算时间步。我们返回从 0 开始计数的时间步。

我们的目标是找到青蛙能够到达目的地的最小时间步数。如果它永远无法过河，我们返回 -1。

2.1. 示例

设 m = 5 且 leaves = [1, 3, 1, 4, 5, 4, 2, 3]。

最初，k = 0，由于 leaves[0] = 1，一片叶子落在位置 1。我们需要位置 2-5 也有叶子才能过河。随着叶子的落下，路径随时间形成：

因此，青蛙可以在时间步 k = 6 时过河。由于我们从 0 开始计数，我们返回 7 (6+1)。

3. 基于 Set（集合）的方法

朴素的方法是在每个时间步检查路径是否完整。这涉及一个外层循环和一个嵌套的内层循环。它具有二次方时间复杂度，O(n^2)。

更好的方法是跟踪已经被覆盖的唯一位置。为此，我们使用 HashSet 来存储迄今为止覆盖的不同位置：

1. 使用索引 k（代表时间步）遍历数组 leaves。
   1. 我们将 leaves[k] 添加到我们的 hashset 中。
   2. 检查集合的大小。
   3. 如果大小等于 m，这意味着我们收集了从 1 到 m 所有位置的叶子。因此，我们立即返回 k+1，因为这是最早可能的过河时间。
   4. 否则，我们继续循环。
2. 如果循环结束且集合大小未达到 m，则无解，我们返回 -1。

3.1. 实现

下面是实现代码：

public int HashSetSolution(int m, @Nonnull int[] leaves) {
    Set leavesCovered = new HashSet<>();
    int status = -1;
    for (int k = 0; k < leaves.length; k++) {
        int position = leaves[k];
        leavesCovered.add(position);      
        if (leavesCovered.size() == m) {
            status = k+1;
            return status;
        }
    }
}

我们使用一个 HashSet (leavesCovered) 来存储已覆盖的叶子。我们遍历输入 leaves 并将每个位置添加到 leavesCovered（HashSet 不保留重复项）。然后，我们检查 leavesCovered 的大小是否等于 m。如果是，我们返回 k+1 作为解决方案（因为时间步从 0 开始，我们需要加 1）。如果我们循环结束，则没有解决方案，所以我们返回 -1。

3.2. 测试

让我们通过几个单元测试用例来演练这个解决方案。

在测试用例 whenLeavesCoverPath_thenReturnsEarliestTime() 中，我们设置 m = 7 且 leaves = [1, 3, 6, 4, 2, 3, 7, 5, 4]。在这里，leaves 填充了从 1 到 7 的所有位置。我们遍历 leaves 并在时间步 k = 7 处停止。因此，青蛙需要 8 个时间步，正如断言所示：

@Test
void whenLeavesCoverPath_thenReturnsEarliestTime() {
    int m = 7;
    int[] leaves = {1, 3, 6, 4, 2, 3, 7, 5, 4};
    assertEquals(8, frogRiverOne.HashSetSolution(m, leaves));
}

在 whenLeavesAreMissing_thenReturnsMinusOne() 中，没有叶子落在位置 5 上，因此两岸之间没有路径。结果，我们得到 -1：

@Test
void whenLeavesAreMissing_thenReturnsMinusOne() {
    int m = 7;
    int[] leaves = {1, 3, 6, 4, 2, 3, 7, 4};  // 5 is missing
    assertEquals(-1, frogRiverOne.HashSetSolution(m, leaves));
}

3.3. 时间和空间复杂度

基于 HashSet 的解决方案的平均时间复杂度为 O(n)，因为我们只遍历数组一次，且 HashSet 操作 add() 和 size() 平均为 O(1)。

然而，HashSet 存在冲突问题：如果许多元素哈希到同一个桶中，它在 Java 中会转换为平衡树。在连续哈希冲突的最坏情况下，add() 具有对数复杂度：O(log n)。因此，该方法具有线性对数 O (n log n) 的时间复杂度。

空间复杂度为 O(n + m)。由于 m <= n，它简化为 O(n)。

4. 基于位图的解决方案

在这里，我们使用一个大小为 m + 1 的布尔数组作为位图，将位置 1 到 m 直接映射到叶子索引。我们用它来跟踪已覆盖的位置。布尔数组为每个元素提供了严格的 O(1) 查找时间。

这是我们的方法：

1. 我们初始化位图以监视河流上所有已接收到叶子的位置，起初所有位置都标记为空。
2. 然后，我们初始化一个计数器来跟踪未覆盖的位置数量。
3. 我们遍历 leaves：
   1. 我们检查当前叶子的位置是否已被覆盖。
   2. 如果没有，我们更新位图并将计数器减一。
   3. 如果计数器等于零，则存在路径，我们返回时间。否则，我们移动到下一个叶子。
4. 如果我们循环结束且计数器 > 0，则叶子没有形成完整的路径，所以我们返回 -1。

4.1. 实现

接下来，我们转到实现：

public int BooleanArraySolution(int m, int[] leaves) {
    boolean[] leavesCovered = new boolean[m + 1];
    int leavesUncovered = m;
    for (int k = 0; k < leaves.length; k++) {
        int position = leaves[k];
        if (!leavesCovered[position]) {
            leavesCovered[position] = true;
            leavesUncovered--;
            if (leavesUncovered == 0) {
                return k+1;
            }
        }
    }
    return -1;
}

我们使用一个包含 m + 1 个元素的 boolean array（leavesCovered）来跟踪落下的叶子。这样，我们可以将每个叶子位置映射到我们的布尔数组。leavesCovered[0] 未被使用。

我们遍历输入 leaves。对于索引为 k 的每个叶子，我们检查它是否尚未被访问。如果是，我们在 leavesCovered 中将此索引设置为 true 并将跟踪器 leavesUncovered 减 1。此外，如果我们的跟踪器 leavesUncovered == 0，我们返回 k+1。如果我们循环结束，则没有解决方案，所以我们返回 -1。

我们使用与基于 HashSet 的解决方案相同的单元测试用例。

4.2. 时间和空间复杂度

该解决方案的平均和最坏情况时间复杂度均为 O(n)，因为它不像 HashSet 解决方案那样受冲突影响。

它的空间复杂度也是 O(n)。

5. 结论

在本文中，我们使用两种方法解决了 Frog River One 问题：HashSet 和布尔数组。使用布尔数组的解决方案通过避免哈希冲突，保证了严格的 O(n) 时间复杂度。

一如既往，完整的源代码可以在 GitHub 上 获取。

文章 Implementing Frog River One in Java 最早出现在 Baeldung 上。[LOADING...]
[LOADING...] [LOADING...] :x: [LOADING...] [LOADING...] [LOADING...] [LOADING...]