題目連結:
題目大意:
輸入有多列,每列給定一正整數(該數為 4 位數 ~ 10 位數,且不含任何 0 在其中),試問該正整數可以藉由重新排列組合其各個位數而得到哪些完全平方數?
輸出那些可以重組出來的完全平方數(每個之間空一個空白)。如果沒有任何可能的完全平方數,則輸出一列的「0」。參見範例輸出。
範例輸入:
1269
3133
範例輸出:
1296 2916 9216
0
解題思維:
先找出 4 位數 ~ 10 位數所有可能的完全平方數。這個可以藉由窮舉所有小於 100000 的所有正整數,對於每個這樣的數 i, 即可找到一個與它對應的完全平方數 i × i。
然後對於每個 S = i × i 之值,統計 S 這個數字中 0 ~ 9 的出現次數。如果 S 中有 0 ,則可以略過 S ,因為輸入保證沒有任何位數為 0 ;如果沒有 0 ,則將 1 ~ 9 根據數量並由小到大接成另一個數字。例如 S = 9216 ,會得到 1269。
可以看到該值可能會有多個完全平方數所對應。如 1269 ,其有 1296 、 2916 、 9216 三個完全平方數對應它。所以我們將每個這種值,利用雜湊表(Hash Table)儲存有哪些完全平方數對應它。
然後我們在輸入時,對於每個給定的正整數都按照類似的分解重組之過程。然後看重組之後的數字 C ,有沒有作為鍵值(Key)存在於 C 之中。
如果沒有,代表原本的數字無法重組成任何完全平方數,所以輸出「0」;反之,將雜湊表裡鍵值 C 對應的完全平方數全部輸出即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。