一道某高大上網際網路公司的筆試題分享

聲明：

首先聲明，我沒有參加此次考試（吾老矣），我隻是道聽途說，是否真的存在這道試題呢？誰知道呢！在此僅僅是想向大家分享一些知識。

原題大概描述：

給定一個二維數組，裡面随機的填寫0和1，求取把上下左右連續（斜線不算相連）的1周邊0的個數。在這裡可以把由1構成資料看成一個島嶼，求島嶼海岸線的長度，即周邊0的個數。

引子：

看過人機博弈-吃子棋遊戲（二）算氣的博友，應該瞬間就有思路了吧。其實圍棋的算氣，在沒有眼位的情況下，就是計算算實心島嶼的海岸線。在有眼位的情況下，圍棋算氣也是計算空心島嶼内部的海岸線長度和外部海岸線長度。什麼是圍棋的眼位，請百度之，我們不繼續讨論圍棋的眼位了。

解決思路：

我并不知道詳細的題目，是以對于此題空心島嶼的内部海岸線長度是否需要特殊處理無從知曉。不過，在算氣的時候檢測是否存在眼位并不難，加标示即可。如果确實是包含空心的島嶼，即形成眼位的圍棋，我們可以進行特殊處理。我們隻要将總氣數扣除内部眼位的氣數就ok了，怎麼扣除是個問題。

在這裡，我說個思路，不一定夠好，但可以解決問題。

1.确定内部海岸線的最小包圍盒（這裡有可能存有外部海岸線，但可以排除大部分外部海岸線），可以節省很多運算。

2.檢測包圍盒内海岸線點是否可以抵達包圍盒的曼哈頓距離最短的邊界，如果可以抵達，且與之相連接配接的海岸線上的點均可抵達，它們都是外部海岸線。

3.否則，如果無法走至包圍盒的此邊界，則證明其被包圍，屬于内部海岸線，且與之相連的點均屬于内部海岸線。

4.依據上述方法檢測包圍盒内部的不重複的所有點，即可得出哪些是内部海岸線。

我們知道這個算法效率不高（配合最小包圍盒，以及連通點性質相同，實際上尋路的次數應該很少），但它是正确的，被包圍的海岸線内部的點，就像困在島嶼裡的小怪物，永遠無法逃出來。而外部海岸線上的點僅僅會認為島嶼是個障礙物而已。

這個算法可以處理任意複雜的圖形，就算山路18彎，外部點也會曆經周折到達海岸線，空心島有好多空心，也不會搞錯内部點or外部點。

針對第二點用深度優先搜尋或是Astar算法均可以，我們目的是找到路就行，而不是找到最短的路。

總結：

       我發博文的時候，并沒有把圍棋中算氣算法抽象成為一個 1，0筆試題。大膽猜測一下，也許出題人正是看到相關博文，才萌生了出此題的想法。我想在CSDN上應該有一部分人更關注筆試題面試題相關的内容，而忽略了本有實質性内容而不是針對筆試題的文章，希望大家能夠從各種部落格中提取出抽象的知識，以不變應萬變。

如果你有更好的思路，可以留言讨論下。

再補充一個例子，很久以前我參加某公司筆試，遇到一題如下，給定一個數組，數組中的數值是随機的且亂序的，要求把偶數排在數組的前面，奇數排在數組的後面，還希望你的算法時間複雜度盡量低。可以使用C/C++語言作答。

你怎麼看這到題，如果你瞬間就有極好的方法，我得恭喜您，因為幾年前的我确實想了很長時間才寫出了正确但時間複雜度比标準答案略高的代碼，後來閱讀一些資料，說标準答案使用首尾兩個指針解決這個問題。恩，今天我要說的是，标準答案該更新了，或是題目該加以更多限制了。看了代碼你就明白了！

1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6     vector<int> nums{1,2,3,4,5,6,7,8,9,10};
 7     random_shuffle(nums.begin(),nums.end());
 8     partition(nums.begin(),nums.end(),[](int ele)->bool{return ele%2==0;});
 9     for(auto& ele:nums){cout<<ele<<" ";};
10     cout<<endl;
11 }      

僅僅10行代碼，包括一切。僅僅第8行代碼，就完成這道題。哈哈，我不希望出題人看見這篇部落格。因為也許他會無德的在題目後面加上一句話禁止使用STL。

而如果你是即将參加筆試的小同志，記得帶上STL攻城利器, 讓守城的人亮瞎雙眼。

有一點請放心，出題人在怎麼優化的代碼，也很難（但還是有可能，某些很專業化的問題，但是這種問題一般不會是面試題吧）在性能上超過STL。一是出題人的水準怎能和STL編寫者比。二是，C++編譯器更懂得優化STL，而不是你的代碼。