用 Java 實作 Frog River One

1. 引言

在本教程中，我們將學習青蛙河一號問題。

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)	葉片位置（ leaves[k])	覆蓋	尚未涵蓋
0	1	1	2、3、4、5
1	3	1、3	2、4、5
2	1	1、3	2、4、5
3	4	1、3、4	2、5
4	5	1、3、4、5	2
5	4	1、3、4、5	5
6	2	1、2、3、4、5

因此，青蛙可以在時間步長k = 6 過河。當我們從 0 開始計數時，我們返回 7 (6+1)。

3. 基於集合的方法

最簡單的方法是在每個時間步驟檢查路徑是否完整。這涉及一個外層循環和一個嵌套的內層循環。它的時間複雜度為二次方，即O(n 2 ) 。

更好的方法是追蹤已覆蓋的唯一位置。為此，我們使用 HashSet 來儲存目前為止已覆蓋的不同位置：

1. 遍歷數組中索引為k leaves節點（表示時間步）。
   1. 我們將leaves[k]添加到我們的哈希集中。
   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.

我們遍歷輸入的leaves.對於索引為k每個葉子節點，我們檢查它是否尚未被訪問過。如果尚未被存取過，則將leavesCovered中的索引設為true ，並將追蹤器leavesUncovered值減 1。此外，如果追蹤器leavesUncovered ==0. ，則傳回k+1 。如果循環結束，則表示無解，因此傳回 -1。

我們使用與基於HashSet解決方案相同的單元測試案例。

4.2 時間與空間複雜性

此解決方案的平均和最壞情況時間複雜度均為O(n) ，因為它不像 HashSet 解決方案那樣容易發生衝突。

它的空間複雜度為O(n).

5. 結論

本文中，我們使用兩種方法解決了蛙河一問題：哈希集合（HashSet）和布林數組。使用布林數組的解決方案透過避免哈希衝突，保證了嚴格的O(n)時間複雜度。

與往常一樣，完整的原始程式碼可在 GitHub 上找到。