本題是浙江理工大學ACM入隊200題第八套中的J題
我們先來看一下這題的題面.
題面
題目描述
寧寧參加奧數班，他遇到的第一個問題是這樣的：口口口+口口口=口口口，寧寧需要將1~9 九個數分別填進對應的空格內，使等式成立，現在寧寧填了一個算式，你能幫他驗證是否正確么？
輸入
輸入為多組測驗資料，
分別輸入三個三位數，依次表示等式里的三個數，
輸出
如果等式成立，輸出：YES!，否則輸出：NO!
樣例輸入
173 286 459
樣例輸出
YES!
題目分析與常見錯誤思路
這題很多朋友都想當然地以為只需要判斷等式是否成立即可,都選擇性的忽視了題目中明確寫出的要求:將1~9九個數分別填進對應的空格內.
所以我們需要額外實作判斷沒有使用重復的數.
解決方案
如何實作捏?首先我們需要依次取出每個數的各個十進制位,這里我已經有一篇博客給出明確的方法介紹了,不清楚的可以去看看(點我看鴨),這里不多贅述了.
接下來困住大多數朋友的都是判斷重復數字了,很多朋友對此毫無思路.
我們先來想想我們人腦是怎么判斷有沒有數字重復的呢?打個比方我們要在一組數字中找第一個數是否重復,那么當我們看到這組數字中的一個數后,我們會接著往后去看有沒有第二個這個數出現,如果有就是重復了,否則就是沒有.
我們是否也可以這樣實作我們這里判斷重復的代碼捏?答案是可行的,我們可以把這三個數的每個位合起來看成一個"陣列"中的元素,然后從左到右遍歷這個"陣列",再對于每一個遍歷到的數之后的數進行一次遍歷,看看其中是否有和這個數相等的數存在.不過這種思路遍歷次數較多,比較接近暴力演算法,時間復雜度很高(可以理解成代碼運行的速度很慢),屬于一種無解演算法.所以我們需要尋找一個更好的演算法.(這種思路的代碼就不貼了,想練代碼可以自己寫寫試試,交上去不清楚會不會時間超限,沒試過)
我們前面的演算法慢在哪呢?慢在我們每次都對遍歷到的數再啟動了一次遍歷,這使得我們遍歷的次數過多.而且每次遍歷都是在重復遍歷這些數.我們是否可以避免這些重復的操作,以此提高速度呢?答案是可行的.
那如何避免重復操作呢?我們可以對遍歷到的數進行一次記錄,記錄什么呢?我們上面這樣判斷的本質其實是在看有沒有哪個數字重復出現了兩次及以上,所以我們就記錄每個數字出現了幾次即可,這樣僅通過一次遍歷,我們便得到了可以判斷是否有重復數字的資料,大大減少了遍歷的次數.這其實便是所謂的用空間換時間的技巧.
那用什么記錄呢?我們目前會的資料結構非常少,基本只有陣列.那能否通過陣列來記錄呢?當前可以!我們希望記錄的形式是"數字:數字出現次數"這樣形式的一個對子,并且我們可以通過數字來訪問到這個數字出現的次數.這個對子和數學上的映射很像.而這個映射完全可以由陣列來完成,因為陣列本身的隨機訪問也可以看成一種映射.
我們知道,當我們給定陣列中某個元素的下標,我們即可得到這個下標對應的那個元素(即隨機訪問),這便是一種現成的映射.那我們自然可以通過把數字作為下標,把數字出現的次數作為下標對應的元素,來充分利用陣列自帶的這種映射實作我們需要的功能.即,我們使用一個長度為10的陣列,在其下標1到9的各個元素中存盤1到9各個數字出現的次數.這樣我們就可以通過各個數字來直接訪問到各個數字出現的個數了.在這里,這個陣列也被稱作桶,是不是很形象鴨?當然,如果有一定資料結構基礎的朋友看到我們的需求,應該會馬上聯想到哈希表,不過這題沒必要使用,因為桶廣義地來講也是一種哈希表(哈希函式回傳這個數字本身).
參考代碼
下面給出了我自己做這道題時候的完整代碼:
(僅作為參考,一定要自己寫一下奧,作弊沒意思,害人又害己)
#include <stdio.h>
#include <string.h>
// 陣列最好定義在main外面(以后你們會知道為啥的)
int num[10]; // 作為桶,下標所對應的元素儲存著下標這個數字出現的次數,由此形成一個一一映射
int main()
{
int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) != EOF)
{
if (a + b != c) // 如果不滿足加法式,直接輸出然后輸入下一組
{
printf("NO!\n");
continue; // 跳過本組處理,開始下一組的輸入
}
for (int i = 0; i < 3; i++) // 各個數字依次取出各個位
{
num[a % 10]++; // 下標為該數字的元素儲存著該數字出現的次數,將該數字的出現次數加一
a /= 10;
num[b % 10]++;
b /= 10;
num[c % 10]++;
c /= 10;
}
int i; // 為了判斷for是否正常退出這里我i定義在外面,也可以在單獨搞一個變數來記錄是否有數重復
for (i = 1; i < 9; i++)
{
if (num[i] > 1) // 如果一個數字出現了兩次
{
printf("NO!\n");
break; // 直接跳出這個for回圈,不用再找有沒有重復了(只要一組重復就不滿足了)
}
}
if (i == 9) // for正常退出時i應為9,如果不為9就是被break強行退出了
{
printf("YES!\n");
}
memset(num, 0, sizeof(num)); // 桶初始化(別忘了鴨!不然就會連著上次輸入一起累加了)如果不會用memset也可以考慮直接寫一個for回圈把每一元素設定為0
}
return 0;
}
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這篇題解就到這里了,各位朋友如果有問題歡迎到acm成員群中提問哦!
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/gemini-star/p/zstuACM200_8J.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509627.html
標籤：其他
上一篇：Java類的序列化和反序列化
下一篇：一文入門Qt Quick