本文主要是介绍poj-3349-Snowflake Snow Snowflakes-哈希，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一个数n，然后给你n组数据，让你去找看是否有相同的雪花，很多人是把数据sort一遍，然后哈希，这样做能水过去，但是和题意有点差别，例如 1 2 3 4 5 6 和1 3 2 4 5 6，它不是相同的雪花，因为1的旁边的值不同啊， 这个题给了4000ms，看来很容易超时，一开始的思路是，建个结构体，下标是对应的那6个数的和对10011取于的结果，然后里面建一个二维数组，来存以前的雪花的数据，来一个雪花，先去看看对应下标里存没存东西，存的话取遍历，看是否相同，没有的话去存，按这个思路做的MLE，后来用的是数组模拟链表，思路是取开一个120W的结构题，里面存的是一个s,12位的数组和一个next 的值，12的数组s感觉很精髓，这一点我也是看的网上的，不过那个大神写的是一个2维的，我感觉1维就够了，它可以把12种情况都能表示出来，例如 1 2 3 4 5 6，和 6 1 2 3 4 5，这样的是相同的，数组模拟链表，关键是把下标的存的问题了，我说一下我这个题把，先去判断对应的头里面存没存东西，存的话，去按照next，去遍历，看是否找到，找不到，新建一个然后存到当前的最后一个nxet里面去。
代码： 跑了2125ms
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mod 100011
int top = 0;
bool flag ;
struct node
{int s[12];int next;
} ls[1200010],now,tem;
int bj[100010];
int buid()
{top++;ls[top].next = 0;return top;
}void add(int sum)
{if(bj[sum] == 0){int bh= buid();bj[sum] = bh;for(int i = 0; i < 6; i++)ls[bh].s[i+6] = ls[bh].s[i] = now.s[i];}else{int c = bj[sum];while(1){for(int i = 0; i < 6; i++){int ty = i, tp = 0;while(ls[c].s[ty] == now.s[tp] && tp< 6){ty++;tp++;}if(tp == 6){flag = true;break;}}if(flag)break;for(int i = 11; i >= 6; i--){int ty = i, tp = 0;while(ls[c].s[ty] == now.s[tp]&&tp<6){ty--;tp++;}if(tp == 6){flag = true;break;}}if(flag)break;if(ls[c].next == 0)break;elsec = ls[c].next;}if(!flag){int bh= buid();ls[c].next = bh;for(int i = 0; i < 6; i++)ls[bh].s[i] = now.s[i];for(int i = 0; i < 6; i++)ls[bh].s[i+6] = now.s[i];}}
}int main(){int n;top = 0;memset(bj,0,sizeof(bj));flag = false;scanf("%d",&n);while(n--){int i, j;int sum = 0;for(i = 0; i < 6; i++){scanf("%d",&now.s[i]);sum+=now.s[i];sum%=mod;}sum = sum%mod;if(flag){continue;}add(sum);}if(flag)printf("Twin snowflakes found.\n");elseprintf("No two snowflakes are alike.\n");return 0;}
这篇关于poj-3349-Snowflake Snow Snowflakes-哈希的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
