PKU OJ 1002(487-3279)電話號碼解題方法與個人最簡短程式碼

PKU OJ 1002(487-3279)電話號碼解題方法與個人最簡短程式碼

以前一次偶然的機會聽說了最短程式碼競賽,這兩天不想幹啥事,便開始做一做OJ吧,

題目見這裡:http://poj.org/problem?id=1002

主要是一個字串讀取與轉換,我的實現程式碼程式碼長度為651位元組,39行。

#include <stdio.h>
#include <map>
typedef long D;
typedef std::map<D,D> M;
char mC[]="2223334445556667777888999";
int main(int argc, char **argv)
{
D n,t;
M m;
scanf("%d\n",&n);
for(;n!=0;n--)
{
char s[64],c;
gets(s);
t=0;
for(D i=0;s[i]!='\0';i  )
{
c=s[i];
if(c>='0'&&c<='9')
t=10*t c-'0';
if(c>='A'&&c<'Z'&&c!='Q')
t=10*t mC[c-'A']-'0';
}
m[t]  ;
}
M::iterator it=m.begin(),iE=m.end();
while(it!=iE)
{
if(it->second>1)
{
n  ;
printf("%03d-%04d %d\n",it->first/10000,it->first%10000,it->second);
}
it  ;
}
if(!n)
printf("No duplicates.\n");
return 0;
}

講解一下上述程式碼利用了以下幾個C 的語法特性:

(1)map類,可以對每個標準電話號碼進行快速的統計和計數,插入新的資料非常方便。

(2)m[t] ; 這個語句詳細的解釋可以參看《C Primer》中關於map類模版的介紹。

如果t不在map中,則新增一個元素,m[t]的值會初始化為0,然後進行一個自增操作,即計數值為1。

否則,m[t]的值由原來的值加1。

(3)typedef定義,主要是減少一點程式碼長度;

(4)OJ需要注意的問題,剛開始沒有注意可能沒有重複專案,中間又因為沒考慮Q會出現在測試資料中所以一直錯誤。

最後附圖程式碼長度與狀態:

2013-7-29更新:

最後也順便附上一個C語言版本,和上面的類似,程式碼也更加簡短了,537字,效率也相對更高,不過記憶體使用有點多了(C 也可以不用map類進行一樣的改寫):

#include <stdio.h>
typedef long D;
#define z 10000000
D m[z]={0};
char mC[]="2223334445556667777888999";
int main()
{
D n,t,i;
scanf("%d\n",&n);
for(;n!=0;n--)
{
char s[64],c;
gets(s);
t=0;
for(i=0;s[i]!='\0';i  )
{
c=s[i];
if(c>='0'&&c<='9')
t=10*t c-'0';
if(c>='A'&&c<'Z'&&c!='Q')
t=10*t mC[c-'A']-'0';
}
m[t]  ;
}
for(i=0;i<z;i  )
{
if(m[i]>1)
{
n  ;
printf("%03d-%04d %d\n",i/10000,i%10000,m[i]);
}
}
if(!n)
puts("No duplicates.");
return 0;
}

程式碼長度與執行結果如下,執行時間還是會受到一些非穩定因素的干擾的。有時候時間短一點~~