摘要：
http://poj.org/problem?id=3320给出一串数字，并要求所有数字的最短长度。想法：哈希不是很有用。这个问题也涉及到其他人的代码，并且已经思考了很长时间。1#包括<；iostream>；2#包括<；算法>；3#包括<；字符串>；4#包括<；cstring>；5使用命名空间
http://poj.org/problem?id=3320
题意：
给出一串数字，要求包含所有数字的最短长度。
思路：
哈希一直不是很会用，这道题也是参考了别人的代码，想了很久。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 7 const int PRIME = 99999; 8 9 int n; 10 int len; 11 12 //开散列法，也就是用链表来存储，所以下面的len是从PRIME开始的，因为前面的都是头结点。 13 14 struct node //key是数值大小，num是该key出现的次数，因为是链表存储，所以next指向下一个结点 15 { 16 int key; 17 int num; 18 int next; 19 }p[1000005]; 20 21 int a[1000005]; 22 23 int _hash(int num) 24 { 25 int k = num%PRIME; //取余 26 while (p[k].next != -1) //该数值已经出现过了 27 { 28 if (num > p[p[k].next].key) break; //按递减的方式排列 29 else if (num == p[p[k].next].key) return p[k].next; //如果已经出现过了，直接返回 30 k = p[k].next; 31 } 32 //没有出现过，添加新的结点 33 p[len].key = num; 34 p[len].num = 0; 35 p[len].next = p[k].next; 36 p[k].next = len; 37 len++; 38 return len - 1; 39 } 40 41 int main() 42 { 43 //freopen("D:\txt.txt", "r", stdin); 44 while (~scanf("%d", &n) && n) 45 { 46 for (int i = 0; i < PRIME; i++) 47 p[i].next = -1; 48 len = PRIME; 49 int left = 0; 50 int ans; 51 for (int i = 0; i < n; i++) 52 { 53 scanf("%d", &a[i]); 54 int temp = _hash(a[i]); 55 p[temp].num++; 56 if (p[temp].num == 1) //说明第一次出现，所以肯定要包括进去，此时ans肯定等于i-left+1 57 { 58 ans = i - left + 1; 59 continue; 60 } 61 //如果之前已经出现过 62 temp = _hash(a[left]); 63 //如果left指向的数值后面还有出现，那么可以右移一位 64 while (left<n - 1 && p[temp].num>1) 65 { 66 p[temp].num--; 67 left++; 68 temp = _hash(a[left]); 69 } 70 if (ans > i - left + 1) ans = i - left + 1; 71 } 72 printf("%d ", ans); 73 } 74 return 0; 75 }
接下来再附上尺取法的做法，主要思路和上面是差不多的。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 #include<set> 6 #include<map> 7 using namespace std; 8 9 const int maxn = 1000000 + 5; 10 11 int n; 12 int x[maxn]; 13 set<int> p; 14 map<int, int> q; 15 16 int main() 17 { 18 //freopen("D:\txt.txt", "r", stdin); 19 while (~scanf("%d", &n)) 20 { 21 p.clear(); 22 q.clear(); 23 for (int i = 1; i <= n; i++) 24 { 25 scanf("%d", &x[i]); 26 } 27 28 for (int i = 1; i <= n; i++) 29 p.insert(x[i]); 30 31 int ans = n; 32 int total = p.size(); //不重复的数 33 int sum = 0; 34 int left = 1, right = 1; 35 while (left<=n && right <= n) 36 { 37 if (q[x[right]] == 0) sum++; //这个数没有出现过 38 q[x[right]]++; 39 40 while (q[x[left]] > 1) 41 { 42 q[x[left]]--; 43 left++; 44 } 45 if (sum == total) 46 { 47 ans = min(ans, right - left + 1); 48 if (q[x[left]] == 1) sum--; 49 q[x[left]]--; 50 left++; 51 } 52 right++; 53 } 54 printf("%d ", ans); 55 } 56 return 0; 57 }