2011-07-18 20:53:45Morris
d244. 一堆石頭 (Hash)
學會 Hash table, 拿舊題來練習一下
/**********************************************************************************/
/* Problem: d244 "一堆石頭" from */
/* Language: C */
/* Result: AC (56ms, 254KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-18 20:51:54 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Mod 123
struct list {
int tag;
short t;
struct list *next;
}*HASH[Mod], *curr, *prev, *temp;
void InsHash(int n) {
int m = n%Mod;
if(HASH[m] == NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
HASH[m] = curr;return;
}
temp = HASH[m], prev = NULL;
while(temp->tag <= n) {
if(temp->tag == n) {temp->t++;return;}
if(temp->next != NULL)
prev = temp, temp = temp->next;
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
temp->next = curr; return;
}
}
if(prev != NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
prev->next = curr, curr->next = temp;
}
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
HASH[m] = curr, curr->next = temp;
}
return;
}
void FreeAll() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a], prev = NULL;
while(curr != NULL) {
prev = curr, curr = curr->next;
free(prev);
}
HASH[a] = NULL;
}
}
void Find() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a];
while(curr != NULL) {
if(curr->t == 2) {
printf("%d\n", curr->tag);
return ;
}
curr = curr->next;
}
}
}
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int n;
FreeAll();
while(1) {
n = Input();
if(n == -1) break;
InsHash(n);
}
Find(), FreeAll();
return 0;
}
/**********************************************************************************/
/* Problem: d244 "一堆石頭" from */
/* Language: C */
/* Result: AC (56ms, 254KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-18 20:51:54 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Mod 123
struct list {
int tag;
short t;
struct list *next;
}*HASH[Mod], *curr, *prev, *temp;
void InsHash(int n) {
int m = n%Mod;
if(HASH[m] == NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
HASH[m] = curr;return;
}
temp = HASH[m], prev = NULL;
while(temp->tag <= n) {
if(temp->tag == n) {temp->t++;return;}
if(temp->next != NULL)
prev = temp, temp = temp->next;
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->next = NULL, curr->t = 1;
temp->next = curr; return;
}
}
if(prev != NULL) {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
prev->next = curr, curr->next = temp;
}
else {
curr = (struct list *)malloc(sizeof(struct list));
curr->tag = n, curr->t = 1;
HASH[m] = curr, curr->next = temp;
}
return;
}
void FreeAll() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a], prev = NULL;
while(curr != NULL) {
prev = curr, curr = curr->next;
free(prev);
}
HASH[a] = NULL;
}
}
void Find() {
int a;
for(a = 0; a < Mod; a++) {
curr = HASH[a];
while(curr != NULL) {
if(curr->t == 2) {
printf("%d\n", curr->tag);
return ;
}
curr = curr->next;
}
}
}
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int n;
FreeAll();
while(1) {
n = Input();
if(n == -1) break;
InsHash(n);
}
Find(), FreeAll();
return 0;
}
上一篇：d919. 最大面積
下一篇：a191. 在世界遙遠的彼方