九章演算法 | Snapchat 面試題 : 青蛙跳

撰文 | JZ

專欄 | 九章演算法

題目描述

一隻青蛙正在過河。河被分成了x段並且每一段都可能存在或不存在一個石頭。這隻青蛙可以跳至石頭上，但不能跳進水裡。

現有一個石頭位置的升序列表，判斷這隻青蛙能否能夠跳至最後一個石頭，從而過河。最初青蛙在第一塊石頭上並且假定第一跳只能跳一段。

如果這隻青蛙之前一次跳了k段，那麼它的下一跳必須是k-1、k或k+1段。注意該青蛙只能向前跳。

樣例

樣例1： [0, 1, 3, 5, 6, 8, 12, 17]

共有8個石頭

第1個石頭在第0段

第2個石頭在第1段

第3個石頭在第3段

……

最後一個石頭在第17段

此樣例返回結果為true。青蛙可跳1段至第2塊石頭，之後跳2段至第3塊石頭，再跳2段至第4塊石頭，再跳3段至第6塊石頭，再跳4段至第7塊石頭，再跳5段至第8塊石頭，即最後一塊石頭，從而過河。

樣例二[0, 1, 2, 3, 4, 8, 9, 11]

此樣例返回結果為false。因為第5塊和第6塊石頭間間距太大，所以無法跳至最後一塊石頭。

解題思路分析

看到這道題，有動態規劃的特徵。首先判斷能不能到達某狀態是動規的常見題型，其次後面的狀態需要用到前面的狀態（即問題可以分解），所以從動態規劃的角度分析一下。

狀態

這道題難以下手的地方就在於一個狀態不只和當前點（青蛙所處的位置）有關，還和跳了多少段到當前位置有關，因為這個數值影響了下一跳的範圍。所以每一個狀態要記錄兩個值，我們用d(i, j)來表示，d(i, j)本身定義為一個布爾型，表示能否通過跳j段到達第i塊石頭。

方程

當我們定義好狀態後，方程就顯得較為自然了。不過我們首先定義兩個東西。

一、

題目中所給的表示石頭位置的升序列表

我們把它定義為一個整數數組名為stones[]

二、

一個pos(x)函數，這個函數返回一個整數

這個整數表示第x段的石頭是這條河中的第幾塊石頭（即給一個整數，返回這個整數在stones[]數組的下標）

假若第x段沒有石頭（即stones數組中不包含這個數）就返回-1。於是我們就有方程d(i, j) = d(pos(stones[i]-j), j-1) || d(pos(stones[i]-j), j) || d(pos(stones[i]-j), j+1).

簡要解釋一下，跳了j段到達第i塊石頭，意味著是從第pos(stones[i]-j)塊石頭跳過來的（如果這塊石頭存在）。又因為跳了j段，所以上一跳所跳的段數必須是j、j-1或j+1的其中之一。所以三個值中若有一個是可達的，那麼d(i, j)就也是可達的。當然，若第pos(stones[i]-j)塊石頭就不存在，那麼當然d(i,j)也就不可達。

初始化和最終狀態

依據題意，初始狀態時d(0, 0)為true。對於最終狀態，假設河中一共有x塊石頭，那麼若d(x, *)中有任何一個位置是true就返回true，否則返回false。

動規思路分析完畢後我們再分析一下一些編程細節。

跳過的段數要計算到多少（即d(i, j)中每一層的j要計算到多少）。這裡我們通過思考可以發現，這個數量最多不會超過歷史最遠的一跳+1。所以我們維護一個歷史最遠跳來作為這裡所跳段數的邊界。

注意數組超界問題，因為所跳段數可以減一，所以要控制其必須大於0。

這道題用廣度優先搜索亦可，但是要注意調至同一個石頭時所跳的段數不同，結果並不同，所以記錄是否入隊的數組依然要是二維的。

參考代碼

http://www.jiuzhang.com/solutions/frog-jump/

面試官角度分析

這道題的重點是要能發現狀態的記錄方法和相應方程。若還能注意到編程中的幾個注意點(比如dp狀態的處理)便可給面試官一個上佳的印象。

相關面試題

http://www.lintcode.com/zh-cn/problem/jump-game/

http://www.lintcode.com/zh-cn/problem/jump-game-ii/