这才是人生赢家，ymm算个毛线 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

这才是人生赢家，ymm算个毛线

这才是人生赢家，ymm算个毛线# Biology - 生物学

e*n2019-03-10 08:03

1 楼

第一遍扫描array用hashmap存array[i]，
第二遍扫描找出hashmap（target - array[i]）
但是如果遇到重复多次的数（如下例程 x=5）且x+x=target=10， C++ 的hashtable （
map) 就只存第一次出现的x 请问有什么办法解决？
#include
#include
#define N 12
using namespace std;
void find2SumTarget(int arr[N], int target){
map hashT;
int i;
map::iterator m;
for (i=0; ihashT.insert(make_pair(arr[i], i));
}
for (i=0; im = hashT.find(target - arr[i]);
if ( m!=hashT.end() && i!=m->second )
printf("%d + %d\n", arr[m->second], arr[i]);
}

}
void main(){
int arr[] = {1, 4, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
find2SumTarget(arr, 10);
}
实际输出：（错误：5+5出现三次）
9+1
6+4
5+5
5+5
5+5
4+6
1+9
正确输出：(5+5应出现两次）
9+1
6+4
5+5
5+5
4+6
1+9

x*l2019-03-10 08:03

2 楼

82年的美女王延轶同志任武汉病毒研究所所长
2018年10月底，一名女性科研干部升任正厅级，她就是中科院武汉病毒所所长王延轶.
拥有博士学位的王延轶，此前任武汉病毒研究所副所长。据公开资料，她生于1981年，
2004年毕业于北京大学生命科学学院，后留学美国科罗拉多大学获硕士学位。当年她来
到武汉大学，6年间任武大生命科学学院讲师、副教授。
2012年3月，王延轶调任中科院武汉病毒所，先后任分子免疫学学科组长，病毒病理研
究中心副主任，2014年12月任所长助理，一年后升任武汉病毒所副所长，直至去年底调
整。
据武汉病毒所官网介绍，王延轶的主要研究方向为病毒与宿主相互作用机制。先后主持
或承担过国家自然科学基金、973等多项课题。在国际知名刊物发表SCI论文近30篇。
作为一名年轻的研究员，她曾获得中国免疫学青年学者奖、国家自然科学二等奖、国家
百千万人才工程“有突出贡献中青年专家”、湖北省五四青年奖章、“中国科学院杰出
青年”等奖项和荣誉称号。2013年，她还入选了国家“万人计划”首批青年拔尖人才。
此外，王延轶于2010年5月加入了中国致公党，并于去年10月当选致公党武汉市副主任
委员。
教育背景
2007-09--2010-06 武汉大学博士
2004-08--2006-06 美国科罗拉多大学医学院硕士
2000-09--2004-06 北京大学学士
工作经历
2015/12至今中科院武汉病毒所，副所长
2014/12至2015/12 中科院武汉病毒所，所长助理
2014/09至今中科院武汉病毒所病毒病理研究中心，副主任
2014/07至2015/06 武昌区卫生和计划生育委员会（挂职），副主任
2012/03至今中科院武汉病毒所分子免疫学学科组，研究员/学科组长
2010/11至2012/02 武汉大学生命科学学，副教授
2006/08至2010/10 武汉大学生命科学学院，讲师

p*22019-03-10 08:03

3 楼

这不就是two sum吗？
用两个pointer前后往里移动。
如果用hashtable存一下数字出现的次数。

f*n2019-03-10 08:03

4 楼

只能呵呵呵
想想也不过就10年前，还跟王延轶同志在小黑屋偶遇，一起western blot曝光呢
她为了SHU博士也没念就回国了，在WHU读的博士
后来听说去了病毒所做研究员
没想到。。。

【在 x****l 的大作中提到】

: 82年的美女王延轶同志任武汉病毒研究所所长
: 2018年10月底，一名女性科研干部升任正厅级，她就是中科院武汉病毒所所长王延轶.
: 拥有博士学位的王延轶，此前任武汉病毒研究所副所长。据公开资料，她生于1981年，
: 2004年毕业于北京大学生命科学学院，后留学美国科罗拉多大学获硕士学位。当年她来
: 到武汉大学，6年间任武大生命科学学院讲师、副教授。
: 2012年3月，王延轶调任中科院武汉病毒所，先后任分子免疫学学科组长，病毒病理研
: 究中心副主任，2014年12月任所长助理，一年后升任武汉病毒所副所长，直至去年底调
: 整。
: 据武汉病毒所官网介绍，王延轶的主要研究方向为病毒与宿主相互作用机制。先后主持
: 或承担过国家自然科学基金、973等多项课题。在国际知名刊物发表SCI论文近30篇。

w*o2019-03-10 08:03

5 楼

北京二爷，
能说说如何“用hashtable存一下数字出现的次数”？
存这个信息有什么用？

【在 p*****2 的大作中提到】

: 这不就是two sum吗？
: 用两个pointer前后往里移动。
: 如果用hashtable存一下数字出现的次数。

x*l2019-03-10 08:03

6 楼

博士毕业四年内杰青。这才叫真牛逼！你们还在博后挣扎吧。。哈哈
2007/09-2010/06 武汉大学生命科学学院，微生物学，博士
学术荣誉
2010/10 武汉大学青年教师教学竞赛二等奖
2010/10 中国免疫学青年学者奖
2011/12 武汉大学珞珈青年学者
2012/11 第三届武汉青年科技奖
2013/03 武汉市三八红旗手
2013/10 国家万人计划首批青年拔尖人才
2013/11 第四届武汉市优秀科技工作者
2014/08 国家杰出青年科学基金
2015/02 教育部自然科学奖一等奖
2015/05 湖北省青年五四奖章
2015/12 国家百千万人才工程“有突出贡献中青年专家”
2015/12 国家自然科学二等奖(第3完成人)

【在 f*****n 的大作中提到】

: 只能呵呵呵
: 想想也不过就10年前，还跟王延轶同志在小黑屋偶遇，一起western blot曝光呢
: 她为了SHU博士也没念就回国了，在WHU读的博士
: 后来听说去了病毒所做研究员
: 没想到。。。

p*22019-03-10 08:03

7 楼

判断重复。
比如你有一个5, sum=10, 你要知道你有几个5, 如果一个5就不可以。两个就可以。

【在 w****o 的大作中提到】

: 北京二爷，
: 能说说如何“用hashtable存一下数字出现的次数”？
: 存这个信息有什么用？

f*y2019-03-10 08:03

8 楼

卧槽，说了半天原来在说舒红兵老婆。她跟颜妹妹也就隔个舒红兵吧！

z*82019-03-10 08:03

9 楼

求两数的和没必要吧
如果只有一个5，处理到这个5的时候 hashtable里面还没有这个值
三数以上就需要了

【在 p*****2 的大作中提到】

:
: 判断重复。
: 比如你有一个5, sum=10, 你要知道你有几个5, 如果一个5就不可以。两个就可以。

h*t2019-03-10 08:03

10 楼

颜宁和舒红兵什么关系？没关系吧

【在 f****y 的大作中提到】

: 卧槽，说了半天原来在说舒红兵老婆。她跟颜妹妹也就隔个舒红兵吧！

G*e2019-03-10 08:03

11 楼

How about using multimap?

f*y2019-03-10 08:03

12 楼

说清楚一点，舒红兵老婆的科研水平查YMM差了一个舒红兵的档次。

p*22019-03-10 08:03

13 楼

Shi

求两数的和没必要吧如果只有一个5，处理到这个5的时候 hashtable里面还没有这个
值三数以上就需要了
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 z*********8 的大作中提到】

: 求两数的和没必要吧
: 如果只有一个5，处理到这个5的时候 hashtable里面还没有这个值
: 三数以上就需要了

f*c2019-03-10 08:03

14 楼

这不是two sum吗？不用什么hashtable，直接先排下序，然后两个指针往中间走，两个
数和等于target，两个指针就同时往中间走一步，不等于target，相应的一个指针走一
步？

G*e2019-03-10 08:03

15 楼

If you sort first, the time complexity would be O(nlogn). Hashtable only
requires O(n) (linear time) in average case.

【在 f******c 的大作中提到】

: 这不是two sum吗？不用什么hashtable，直接先排下序，然后两个指针往中间走，两个
: 数和等于target，两个指针就同时往中间走一步，不等于target，相应的一个指针走一
: 步？

e*n2019-03-10 08:03

16 楼

搞定.用了multimap 和两个iterator.
#include
#include
#define N 13
using namespace std;
void find2SumTarget(int arr[N], int target){
int i;
multimap hashT;
multimap::iterator iter1, iter2;
typedef multimap::size_type sz_type;
for (i=0; ihashT.insert(make_pair(arr[i], i));
}
iter1 = hashT.begin();
while(iter1 != hashT.end()){
iter2 = hashT.find(target - arr[iter1->second]);
sz_type entries = hashT.count(target - arr[iter1->second]);
for( sz_type cnt=0; cnt !=entries; cnt++, iter2++ ){
if ( iter1->second!=iter2->second ){
printf("%d + %d\n", arr[iter1->second], arr[iter2->second]);
hashT.erase(iter2);
break;
}
}
hashT.erase(iter1);
iter1 = hashT.begin();
}

}
void main(){
int arr[] = {1, 4, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
find2SumTarget(arr, 10);
getchar();
}

【在 G******e 的大作中提到】

: How about using multimap?

k*I2019-03-10 08:03

17 楼

你这个复杂度多少？ While 里面套loop...

【在 e***n 的大作中提到】

: 搞定.用了multimap 和两个iterator.
: #include
: #include
: #define N 13
: using namespace std;
: void find2SumTarget(int arr[N], int target){
: int i;
: multimap hashT;
: multimap::iterator iter1, iter2;
: typedef multimap::size_type sz_type;

g*v2019-03-10 08:03

18 楼

mark

k*g2019-03-10 08:03

19 楼

弱人路过，用的是楼上说的两个指针往中间走的办法
#include
using namespace std;
void find2sum(int a[], int size, int target)
{
if (size<2)
return;
for (int i=0, j=size-1; iint sum = a[i]+a[j];
if (sum == target) {
cout<i++; j--;
} else if (sum > target) {
j--;
} else if (sum < target) {
i++;
}
}
}
int main(int argc, char* argv[])
{
//int a[] = {1, 4, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
//int a[] = {1, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
// int a[] = {1, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
int a[] = {5, 5, 5};
find2sum(a, sizeof(a)/sizeof(int), 10);
return 0;
}