用 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 來儲存目前為止已覆蓋的不同位置:
- 遍歷數組中索引為
kleaves節點(表示時間步)。- 我們將
leaves[k]添加到我們的哈希集中。 - 檢查套裝尺寸。
- 如果大小等於
m,則表示我們已經收集了從 1 到m所有位置的葉子。因此,我們立即返回k+1,因為這是最早可能的穿越時間。 - 否則,我們繼續循環。
- 我們將
- 如果循環結束時集合大小仍未達到
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)查找時間。
我們的方法如下:
- 我們初始化位圖,以監控河流上所有已收到葉子的位置,從所有標記為空的位置開始。
- 然後,我們初始化一個計數器來追蹤未覆蓋位置的數量。
- 我們遍歷
leaves節點:- 我們檢查目前葉片的位置,看看它是否已被覆蓋。
- 否則,我們更新位圖並將計數器減一。
- 如果計數器歸零,則存在一條路徑,我們返回目前時間。否則,我們移動到下一個葉子節點。
- 如果循環結束且計數器大於 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 上找到。