九章演算法 | Facebook 面試題 : 桌上的戰艦

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個由X和.構成的二維字元數組，統計其中「戰艦」的數目。「戰艦」指的是橫向或者是縱向的連續的1-n個『X』。

給定的輸入保證不同的「戰艦」不相鄰，不存在非法輸入。

樣例輸入：

輸入：

X..X

...X

...X

輸出：2

下面的輸入是非法的，因為存在相鄰的「戰艦」。

...X

XXXX

...X

題目分析

看到這個題目，我們容易聯想到迷宮類或者地圖類題目，不同的是本題不需要找到路徑，需要找到的是有多少個連續的X區域。所以我們容易想到利用DFS搜索，搜索的同時標記已經走過的區域，每次碰到沒有走過的區域就將最終結果加一，最後得到的結果就是所求的「戰艦」數目。

另外，注意到本題有其特殊之處，每個戰艦必須是1*N或者N*1的，因此，我們可以保證每次一直沿著同一個方向搜索就可以找到屬於同一艘「戰艦」的所有『X』。

參考代碼

Follow-up 挑戰

上述搜索解法已經能夠順利解決本題。時間複雜度為O(m*n),空間複雜度為O(1),但是我們需要修改board數組中的值。或者如果不修改數組中值的話，我們需要另外開一個數組記錄該位置是否已經訪問過，空間複雜度就成為O(m*n)了。

我們能否不修改原數組，同時只遍歷一次原數組，只用O(1)的空間複雜度解決這個問題？

注意到，題目保證輸入的數據一定是合法的，而合法的輸入數據中，不同的「戰艦」一定不相鄰，因此，不同戰艦的「船頭」也一定不相鄰。所以，對於這道題目，我們僅僅通過計數有多少個船頭就可以得到結果。而一艘戰艦要麼是1*N的，要麼是N*1的，即戰艦的方向是向右或者向下的，「船頭」的左邊和上邊一定不是『X』,而非船頭的左邊或者上邊一定是X，否則就不是合法的輸入。

參考代碼

Lintcode 相關面試題

Bomb-enemy

面試官角度分析

本題屬於中等偏下難度，主要考察面試者搜索的思想。如果能夠利用DFS解決本題就可以達到hire的程度，如果能夠利用本題輸入數據的特殊之處給出O(1)的空間複雜度的解法，可以達到strong hire 。