如何確定我是否可以在數組中達到零點？

Question

我給了一個數組，arr = [3,4,2,3,0,3,1,2,1]和一個startIndex。當我在索引i時，我可以通過arr [i]向左或向右移動。我的任務是找到我是否可以達到0. 任何人都可以幫助我的方法嗎？ 謝謝:)

Answer 1

解決的辦法是尋找路徑在圖形

這裏真正的問題沒有得到解決，它的正確建模的問題。解決方案是微不足道的。

首先，你並沒有真正的數組。你有什麼是圖。如果你從未做過任何graph theory，這將會有點複雜。

陣列中的每個索引都是node。存儲在該索引處的值將爲您提供lines，使用指示移動方向的箭頭將其鏈接到其他節點。例如，您指定的數組給出了以下圖表：

每個節點都標有它在數組中的位置（0到8）。 您想要到達的節點是紅色的。 這是假設你可以移動到數組的開頭，一旦到達數組的末尾，反之亦然。

現在您只需找到4與您的startIndex之間的路徑。您可以申請Dijkstra's algorithm找到最短路徑。

太好了。現在我該如何製作圖表？

如果你對如何實現一個圖表沒有任何想法，you can check this stackoverflow question爲java實現。

您可以輕鬆找到任何其他語言的實現。