本文主要是介绍月球美容计划之二分哈希，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
哈希
把背包基础看完，后面实在深入不下去了，白书讲的也不过这些，背包九讲讲的完全不理解，介绍根本没有接触过的模型，决定吧背包进度放慢，随日后刷题再扩充总结。今天看了哈希和二分，发现基本没有内容可以写，当时WN姐十几分钟突突把哈希讲完了，讲的晕晕乎乎的，认识哈希几个月了，这几个月做题不知不觉的发现原来我之前一直使用的方法叫做哈希啊。
其实哈希没有什么可以终结的，估计也不会有简单到单纯的哈希题目，哈希会是成为以后题目中一个小小降低时间复杂度的技巧。
我觉得唯一可以总结的就是链地址法处理冲突，想当时集训的时候，一整天就做了一个题，只为实现链地址法。当时题目以及代码。
#include<stdio.h>
#include<string.h>struct m
{int data;int tim;struct m * next;
} a[100001];int addm(int n,int d)
{m *p = &a[n],*t;t = p;while (p != NULL){if (p->data == d){p->tim++;return 0;}p = p->next;if (t->next != NULL)t = t->next;}p = t;p->next = new m;p = p->next;p->data = d;p->tim = 1;p->next = NULL;return 0;
}
int imax;
int fid (void)
{int t = 0,n = 0,i;m *p;for (i = 0; i < 100000; i++){p = &a[i];while (p != NULL){if (p->tim > t){t = p->tim;n = p->data;}else if (p->tim == t){if (p->data < n){n = p->data;}}p = p->next;}}imax = n;return t;
}int main()
{int n,i,m,t;memset(a,0,sizeof (a));scanf ("%d",&n);for (i = 0; i < n; i++){scanf ("%d",&t);addm(t % 100000,t);}int num = fid();printf ("%d %d\n",imax,num);return 0;
}
二分查找
集训结束做的题中好像也没几个用到二分查找的，顺序查找注定了它适用范围的局限。二分在寒假的时候一直以一个函数使用，其实真正做题的时候不一定这么隆重，一个循环就够了。
总结二分模板：
for (i = 0; i < n; i++)scanf ("%d",&a[i]);
int k;
scanf ("%d",&k);
l = 0; //头指针
r = n - 1; //尾指针
int tf = 0,m;
while (l <= r && !tf)
{m = (l + r) / 2;if (a[m] == k)tf = 1;else{if (k > a[m])l = m + 1;elser = m - 1;}
}if (tf)puts ("YES");
elseputs ("NO");
这篇关于月球美容计划之二分哈希的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
