題目：

小明陪小紅去看鉆石，他們從一堆鉆石中隨機(jī)抽取兩顆并比較她們的重量。這些鉆石的重量各不相同。在他們們比較了一段時(shí)間后，它們看中了兩顆鉆石g1和g2。現(xiàn)在請(qǐng)你根據(jù)之前比較的信息判斷這兩顆鉆石的哪顆更重。

給定兩顆鉆石的編號(hào)g1,g2，編號(hào)從1開(kāi)始，同時(shí)給定關(guān)系數(shù)組vector,其中元素為一些二元組，第一個(gè)元素為一次比較中較重的鉆石的編號(hào)，第 二個(gè)元素為較輕的鉆石的編號(hào)。最后給定之前的比較次數(shù)n。請(qǐng)返回這兩顆鉆石的關(guān)系，若g1更重返回1，g2更重返回-1，無(wú)法判斷返回0。輸入數(shù)據(jù)保證合 法，不會(huì)有矛盾情況出現(xiàn)。

測(cè)試樣例： 2,3,[[1,2],[2,4],[1,3],[4,3]],4 返回: 1 1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <queue> 5 #include <unordered_map> 6 #include <algorithm> 7 using namespace std; 8 9 /* 10 1>2 11 2>4 12 1>3 13 4>3 14 要判斷2和3的關(guān)系 15 如果從2開(kāi)始能遍歷到3，那么2>3,反之2<3 16 類似圖的廣度優(yōu)先遍歷 17 1 建立一個(gè)哈希表，把左元素作為key，把右元素作為value（vector<int>結(jié)構(gòu)） 18 2 以g1開(kāi)始廣度優(yōu)先遍歷，直到遍歷到g2，則g1>g2；否則以g2開(kāi)始廣度優(yōu)先遍歷，直到遍歷到g1，則g1<g2;否則條件不足無(wú)法判斷 19 2.1 把與g1相連的頂點(diǎn)（即g1作為key對(duì)應(yīng)的value）依次入隊(duì)列 20 2.2 用一個(gè)哈希表標(biāo)記遍歷情況，key是頂點(diǎn)，value（bool類型）標(biāo)記是否遍歷過(guò) 21 */ 22 23 class Cmp { 24 bool compare(int g1, int g2, unordered_map<int, vector<int>> graph) 25 { 26 queue<int> que; 27 que.push(g1); 28 unordered_map<int, int> flag; 29 int temp; 30 while (!que.empty()) 31 { 32 temp = que.front(); 33 flag[temp] = 1; 34 que.pop(); 35 if (temp == g2) 36 return true; 37 else 38 { 39 for (int i = 0;i < graph[temp].size();i++) 40 { 41 if (!flag[graph[temp][i]])//如果graph[temp][i]沒(méi)有被遍歷過(guò) 42 que.push(graph[temp][i]); 43 } 44 } 45 } 46 return false; 47 } 48 public: 49 int cmp(int g1, int g2, vector<vector<int> > records, int n) { 50 // write code here 51 unordered_map<int, vector<int>> graph; 52 for (int i = 0;i < n;i++) 53 graph[records[i][0]].push_back(records[i][1]); 54 if (compare(g1, g2, graph)) 55 return 1; 56 else 57 { 58 if (compare(g2, g1, graph)) 59 return -1; 60 else 61 return 0; 62 } 63 } 64 }; 65 66 /* 67 測(cè)試樣例： 68 2, 3, [[1, 2], [2, 4], [1, 3], [4, 3]], 4 69 返回: 1 70 */ 71 int main() 72 { 73 vector<vector<int> > v{ {1,2},{2,4},{1,3},{4,3} }; 74 Cmp solution; 75 cout<<solution.cmp(2,3,v,4); 76 return 0; 77 }

轉(zhuǎn)載于:https://www.cnblogs.com/hslzju/p/5714795.html

總結(jié)

以上是生活随笔為你收集整理的比较重量 网易2016实习研发工程师编程题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。