查找數組是否可以形成圖形

[採訪問題]我在最近的一次在線採訪中得到了這個問題。我不知道如何解決它。任何人都可以請幫我解決這個問題，以便我可以學習Java。查找數組是否可以形成圖形

湯姆在問題解決方面非常出色。爲了測試湯姆的技能，傑裏向湯姆提出了一個圖表問題。傑裏給了湯姆，一個N個整數的數組A.

圖是一個簡單的圖，如果它沒有自循環或多邊。

現在傑瑞問湯姆他是否可以設計一個簡單的N個頂點圖。條件是Tom必須對圖的頂點度使用A的每個元素。

現在，湯姆希望你的幫助來設計他的圖形。如果可以設計圖表，則打印「是」，否則打印「否」（不含引號）。

輸入單個整數T，在第一行中表示測試用例的數量。對於每個測試用例，有2行。第一行是一個整數N，表示陣列A的元素的數量第二行有N個空間分隔的整數，代表A.

的元件

輸出對於每一個測試的情況下，打印「YES」或「否」（不含引號）是否可以設計圖表，換一個新行。

約束

1<= T <= 100 
1<= N <= 100 
0<= Element of A <= 5000

樣品測試案例

輸入

1 
2 
1 1

輸出

YES

說明對於這個測試的情況下，用2個頂點的簡單圖可以被設計，其中每個頂點有度1.

輸入

輸出

YES 
NO

說明對於第一個試驗的情況下，我們可以設計一種簡單3個頂點的圖，它的度序列爲[1,2,1]。第一個頂點的度數爲1，第二個爲2，第三個爲1。對於第二個測試用例，我們不能製作3個頂點的簡單圖，它的度序列爲[1,1,1]。

來源

2017-02-17 Newbie

您的解釋很混亂，問題似乎沒有明確定義。你說第三行是由空間分隔的元素，然後將第三行解釋爲頂點的程度。測試用例行很不理智，與問題陳述無關。 – hhafeez

一個必要條件是A中元素的和是偶數。這是由於每個邊緣在鄰接列表中被計數兩次。

接下來要嘗試構建圖或至少「分配」節點對。

Sort elements of A in decending order, 
Let the largest (first) element be a, 
Check are element on positions 2 to a+1 larger than 0, 
    If there is a element with value 0 than it is not possible to construct a graph, 
Decrease these a elements by 1 and set first element to 0, 
Repeat process until all elements are 0.

注意，在隨後的步驟的排序可以在O（n）的與合併排序步驟中完成的，因爲列表包括三個排序部分：

第一元件（0），其可以去結束，
排序部分與元素，
其餘排序。

來源

2017-02-20 16:22:19 Ante

查找數組是否可以形成圖形

回答

相關問題