內容
可愛的潘潘有著一堆石頭，每顆石頭上面都有一個正整數編號。接著，她又利用複製機器把每顆石頭都複製了兩個，而編號當然跟原來那個一樣。
可是有一天，她不小心掉了一顆石頭，現在她想要找出她掉的那一顆石頭的編號。
輸入
只有一筆測資給你她現在所擁有的石頭的編號，用空格分開。
當然，個數一定是三的倍數減一個。
9 8 6 9 8 2 3 5 2 1 6 8 1 5 1 2 3 3 5 9
輸出
輸出她掉的那一顆石頭的編號。
6
解題思路
讀入資料後查表判斷是有有儲存過，然後會出現以下任一種情況
- 沒儲存過 → 將資料存到末項之後一個元素，次數設為 1 ，陣列長度 + 1
- 有儲存過，次數為 1 → 將次數 + 1
- 有儲存過，次數為 2 → 將元素和末項交換，將陣列長度 - 1 代表該筆資料作廢
按照上表對應處理所有元素，由於只會有一組只有兩個，剩下的都會有 3 個，而 3 個石頭又會觸發狀態 3，所以最後不管兩個石頭的那組原本在哪都會被換到首項，因此輸出時不用再遍歷一次，直接輸出即可。
下面另外提供一個雜湊表版本的，雜湊版本在能克服測資更大更極端的情況，不過由於本題測資不強所以耗時反而比陣列版更久就是了。
完整程式碼
陣列版
AC (6ms, 1.1MB)
#include <stdio.h>
#define BUFSIZE 1048576
int stone[BUFSIZE], cont[BUFSIZE];
inline char readChar()
{
static char buffer[BUFSIZE], * now = buffer + BUFSIZE, * end = buffer + BUFSIZE;
if (now == end)
{
if (end < buffer + BUFSIZE)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZE, stdin));
now = buffer;
}
return *now++;
}
inline char readUInt(unsigned int* dst)
{
register char ch;
while ((ch = readChar()) < '0')
if (ch == EOF) return 0;
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
return 1;
}
int main()
{
unsigned int tmp, len = 0;
while (readUInt(&tmp))
{
for (int i = 0; i < len; i++)
{
if (stone[i] == tmp)
{
if (cont[i] == 2)
stone[i] = stone[--len], cont[i] = cont[len];
else
cont[i]++;
goto end;
}
}
stone[len] = tmp, cont[len++] = 1;
end:;
}
printf("%d", stone[0]);
return 0;
}
|
雜湊表版
AC (9ms, 1.1MB)
#include <stdio.h>
#define BUKCNT 9887
#define BUKSIZ 1000000
#define BUFSIZE 1048576
typedef struct
{
unsigned int Key, Value, Next;
} Node;
unsigned int buckets[BUKCNT], freeBuk, lastNode;
Node dict[BUKSIZ];
inline char readChar()
{
static char buffer[BUFSIZE], * now = buffer + BUFSIZE, * end = buffer + BUFSIZE;
if (now == end)
{
if (end < buffer + BUFSIZE)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZE, stdin));
now = buffer;
}
return *now++;
}
inline char readUInt(unsigned int* dst)
{
register char ch;
while ((ch = readChar()) < '0')
if (ch == EOF) return 0;
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
return 1;
}
void setNode(int Key)
{
int targetBuk = Key % 9887, currNode = buckets[targetBuk];
while (currNode)
{
if (dict[currNode].Key == Key)
{
if (dict[currNode].Value == 2)
{
int del = dict[currNode].Next;
dict[currNode] = dict[del];
if (del)
{
dict[del].Next = freeBuk;
freeBuk = del;
}
return;
}
dict[currNode].Value++;
return;
}
currNode = dict[currNode].Next;
}
if (freeBuk)
currNode = freeBuk, freeBuk = dict[freeBuk].Next;
else
currNode = ++lastNode;
dict[currNode].Next = buckets[targetBuk];
buckets[targetBuk] = currNode;
dict[currNode].Key = Key;
dict[currNode].Value = 1;
}
int getAns()
{
int currNode;
for (int i = 0; i < BUKCNT; i++)
{
currNode = buckets[i];
while (currNode)
{
if (dict[currNode].Value == 2)
return dict[currNode].Key;
currNode = dict[currNode].Next;
}
}
}
int main()
{
int tmp;
while (readUInt(&tmp))
setNode(tmp);
printf("%d", getAns());
return 0;
}
|
