Redian新闻
>
这才是人生赢家,ymm算个毛线
avatar
这才是人生赢家,ymm算个毛线# Biology - 生物学
e*n
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
avatar
x*l
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 武汉大学生命科学学院,讲师
avatar
p*2
3
这不就是two sum吗?
用两个pointer前后往里移动。
如果用hashtable存一下数字出现的次数。
avatar
f*n
4
只能呵呵呵
想想也不过就10年前,还跟王延轶同志在小黑屋偶遇,一起western blot曝光呢
她为了SHU博士也没念就回国了,在WHU读的博士
后来听说去了病毒所做研究员
没想到。。。

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

avatar
w*o
5
北京二爷,
能说说如何“用hashtable存一下数字出现的次数”?
存这个信息有什么用?

【在 p*****2 的大作中提到】
: 这不就是two sum吗?
: 用两个pointer前后往里移动。
: 如果用hashtable存一下数字出现的次数。

avatar
x*l
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读的博士
: 后来听说去了病毒所做研究员
: 没想到。。。

avatar
p*2
7

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

【在 w****o 的大作中提到】
: 北京二爷,
: 能说说如何“用hashtable存一下数字出现的次数”?
: 存这个信息有什么用?

avatar
f*y
8
卧槽,说了半天原来在说舒红兵老婆。她跟颜妹妹也就隔个舒红兵吧!
avatar
z*8
9
求两数的和 没必要吧
如果只有一个5, 处理到这个5的时候 hashtable里面还没有这个值
三数以上就需要了

【在 p*****2 的大作中提到】
:
: 判断重复。
: 比如你有一个5, sum=10, 你要知道你有几个5, 如果一个5就不可以。两个就可以。

avatar
h*t
10
颜宁和舒红兵什么关系?没关系吧

【在 f****y 的大作中提到】
: 卧槽,说了半天原来在说舒红兵老婆。她跟颜妹妹也就隔个舒红兵吧!
avatar
G*e
11
How about using multimap?
avatar
f*y
12
说清楚一点,舒红兵老婆的科研水平查YMM差了一个舒红兵的档次。
avatar
p*2
13
Shi

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

【在 z*********8 的大作中提到】
: 求两数的和 没必要吧
: 如果只有一个5, 处理到这个5的时候 hashtable里面还没有这个值
: 三数以上就需要了

avatar
f*c
14
这不是two sum吗?不用什么hashtable,直接先排下序,然后两个指针往中间走,两个
数和等于target,两个指针就同时往中间走一步,不等于target,相应的一个指针走一
步?
avatar
G*e
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,相应的一个指针走一
: 步?

avatar
e*n
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?
avatar
k*I
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;

avatar
g*v
18
mark
avatar
k*g
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;
}
avatar
q*y
20
map里存出现次数,每用掉一个数就把对应次数减1,减为0时从map中删除。
avatar
e*n
21
复杂度O(n)
因为里面的for loop最多只会执行两次(只要找到不是本身的另一个等值元素就break)

【在 k******I 的大作中提到】
: 你这个复杂度多少? While 里面套loop...
avatar
i*7
22
压根不用扫两次。扫一次就够了,一边扫一边建hash_map一边对比。
avatar
b*d
23
这里9+1,1+9要输出两次?神马情况?

正确输出:(5+5应出现两次)
9+1
6+4
5+5
5+5
4+6
1+9

【在 e***n 的大作中提到】
: 复杂度O(n)
: 因为里面的for loop最多只会执行两次(只要找到不是本身的另一个等值元素就break)

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。