亞馬遜經(jīng)典面試題實(shí)例詳解
更新時間:2017年10月11日 14:19:43 作者:JeemyJohn
這篇文章主要介紹了亞馬遜經(jīng)典面試題實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家,讓大家學(xué)習(xí)理解這部分內(nèi)容,需要的朋友可以參考下
亞馬遜面試題:
如下所示的Map中,0代表海水,1代表島嶼,其中每一個島嶼與其八領(lǐng)域的區(qū)間的小島能相連組成島嶼群。寫代碼,統(tǒng)計Map中島嶼個數(shù)。
/* Q1. Map [ 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ] */
實(shí)現(xiàn)代碼:
#include<iostream> #include<queue> using namespace std; typedef struct { int i; int j; }position; void search(int a[][], int n, int i, int j, int cnt) { queue<position> qu = new queue<position>(); position p; p.i = i; p.j = j; qu.push(p); a[i][j] = cnt; while (!qu.empty()) { p = qu.pop(); for (int ii = p.i - 1; ii <= p.i + 1; ii++) { for (int jj = p.j - 1; jj <= p.j + 1; jj++) { if (ii >= 0 && ii < n && jj >= 0 && jj < n && a[ii][jj] == 1 && (ii != i || jj != j)) { a[ii][jj] = cnt; p.i = ii; p.j = jj; qu.push(p); } } } } } int count(int a[][], int n) { int cnt = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 1) { cnt++; // 發(fā)現(xiàn)一個新陸地 search(a, n, i, j, cnt); } } } return cnt; } int main() { int n; cin >> n; int a[][] = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } int cnt = count(a, n); cout << cnt - 1 << endl; return 0; }
如有疑問請留言或者到本站社區(qū)交流討論,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
相關(guān)文章
C++?Qt實(shí)現(xiàn)動態(tài)增加垂直滾動條
本博文源于筆者正在工作的一個小內(nèi)容,內(nèi)容涉及到為qt動態(tài)增加垂直滾動條,文章分為三個部分,問題起源,問題解決方案,問題解決成功效果,思路清晰,文章干貨滿滿,復(fù)制源碼即可使用,需要的朋友可以參考下2023-08-08C語言之結(jié)構(gòu)體定義 typedef struct 用法詳解和用法小結(jié)
這篇文章主要介紹了C語言的結(jié)構(gòu)體定義typedef struct用法詳解和用法小結(jié),typedef是類型定義,typedef struct 是為了使用這個結(jié)構(gòu)體方便,感興趣的同學(xué)可以參考閱讀2023-03-03C++11?std::transform函數(shù)使用小結(jié)
std::transform是C++標(biāo)準(zhǔn)庫中的一個算法,它用于對輸入范圍內(nèi)的元素進(jìn)行操作,并將結(jié)果存儲在輸出范圍內(nèi),本文就介紹了std::transform函數(shù)的具體使用,感興趣的可以了解一下2023-09-09C++ throw關(guān)鍵字實(shí)現(xiàn)拋出異常和異常規(guī)范
本文主要介紹了C++ throw關(guān)鍵字實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-08-08