亞馬遜經(jīng)典面試題實(shí)例詳解

更新時(shí)間：2017年10月11日 14:19:43 作者：JeemyJohn

這篇文章主要介紹了亞馬遜經(jīng)典面試題實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家學(xué)習(xí)理解這部分內(nèi)容，需要的朋友可以參考下

亞馬遜面試題：

如下所示的Map中，0代表海水，1代表島嶼，其中每一個(gè)島嶼與其八領(lǐng)域的區(qū)間的小島能相連組成島嶼群。寫(xiě)代碼，統(tǒng)計(jì)Map中島嶼個(gè)數(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)一個(gè)新陸地
        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;
}

如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章:

相關(guān)文章

在C++中使用HP-Socket
這篇文章主要介紹了C++中簡(jiǎn)單使用HP-Socket，HP-Socket 是一套通用的高性能 TCP/UDP /HTTP 通信框架，包含服務(wù)端組件、客戶端組件和 Agent 組件，廣泛適用于各種不同應(yīng)用場(chǎng)景的 TCP/UDP /HTTP 通信系統(tǒng)，下面來(lái)看看更具體的介紹吧
2021-11-11
C語(yǔ)言動(dòng)態(tài)內(nèi)存管理介紹
大家好，本篇文章主要講的是C語(yǔ)言動(dòng)態(tài)內(nèi)存管理介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽
2021-12-12
C語(yǔ)言實(shí)現(xiàn)字母大小寫(xiě)轉(zhuǎn)換的方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)字母大小寫(xiě)轉(zhuǎn)換的方法,涉及C語(yǔ)言字符串的遍歷與轉(zhuǎn)換技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下
2015-07-07
gcc中extra qualification錯(cuò)誤的解決
今天小編就為大家分享一篇gcc中extra qualification錯(cuò)誤的解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2019-12-12
c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)
本文介紹了c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)，二分查找指首先將數(shù)組中間值和目標(biāo)值進(jìn)行比較，如果相等則返回；如果不相等，則選擇中間值左邊的一半或者右邊的一半進(jìn)行比較；不斷重復(fù)直到檢索完畢，下文相關(guān)資料需要的朋友可以參考一下
2022-03-03
C++實(shí)現(xiàn)簡(jiǎn)單貪吃蛇小游戲
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單貪吃蛇小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2021-05-05
VSCode C++多文件編譯的簡(jiǎn)單使用方法
這篇文章主要介紹了VSCode C++多文件編譯的簡(jiǎn)單使用方法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2021-03-03
C語(yǔ)言求逆矩陣案例詳解
這篇文章主要介紹了C語(yǔ)言求逆矩陣案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-08-08
C++實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)框架SimpleNN的詳細(xì)過(guò)程
本來(lái)自己想到用C++實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)主要是想強(qiáng)化一下編碼能力并入門(mén)深度學(xué)習(xí)，對(duì)C++實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)框架SimpleNN的詳細(xì)過(guò)程感興趣的朋友一起看看吧
2021-08-08
一篇文章徹底弄懂C++虛函數(shù)的實(shí)現(xiàn)機(jī)制
C++中的虛函數(shù)的作用主要是實(shí)現(xiàn)了多態(tài)的機(jī)制,基類(lèi)定義虛函數(shù),子類(lèi)可以重寫(xiě)該函數(shù),在派生類(lèi)中對(duì)基類(lèi)定義的虛函數(shù)進(jìn)行重寫(xiě)時(shí),需要在派生類(lèi)中聲明該方法為虛方法,這篇文章主要給大家介紹了關(guān)于如何通過(guò)一篇文章徹底弄懂C++虛函數(shù)的實(shí)現(xiàn)機(jī)制,需要的朋友可以參考下
2021-06-06