l*********r
发帖数: 26 | 1 1. Int to string (pay attention to the smallest negative number)
2. Given two sorted list, find the k smallest number (binary search)
3. You can win three kinds of basketball points, 1 point, 2 points, and 3
points. Given a total score X, print out all the combination to compose X. (
recursion/ Dp)
4. Given a stream of integers, at a given time, there is a number appeared
more than half time, how to find this number. (classic streaming algorithm
) |
s*********t
发帖数: 1663 | 2 ding
总看到itoa的题目，弱弱地问一下，是不是sprintf，ssteram之类的都不许用？
第四个题没想法
(
algorithm
【在 l*********r 的大作中提到】
: 1. Int to string (pay attention to the smallest negative number)
: 2. Given two sorted list, find the k smallest number (binary search)
: 3. You can win three kinds of basketball points, 1 point, 2 points, and 3
: points. Given a total score X, print out all the combination to compose X. (
: recursion/ Dp)
: 4. Given a stream of integers, at a given time, there is a number appeared
: more than half time, how to find this number. (classic streaming algorithm
: )
|
m*****g
发帖数: 226 | 3 3是coin change的一种。就是每个都试，不算dp
4前面讨论过好象，就是用一个counter计数
cnt = 0;
curNum = 0;
while(input>>temp)
{
if(!cnt) curNum = temp;
if(temp == curNum)
cnt++;
else
cnt--;
}
大概就是这样 |
f****4
发帖数: 1359 | 4 lz 面的啥职位？这4道都要求写代码么?
Given two sorted list, find the k smallest number
这个能用binary search么？谁给解释一下咋用binary search
保证list都是从小到大排序，2个list分别scan，输出小的那个值，然后那个指针后移
；得到k个停止 |
s*********t
发帖数: 1663 | 5 这个很直观
binary就是只保留两数组的头K个
然后比a[k/2],b[k/2]，每次缩小一般搜索范围
如果list指的是链表那还是算了。。
【在 f****4 的大作中提到】
: lz 面的啥职位？这4道都要求写代码么?
: Given two sorted list, find the k smallest number
: 这个能用binary search么？谁给解释一下咋用binary search
: 保证list都是从小到大排序，2个list分别scan，输出小的那个值，然后那个指针后移
: ；得到k个停止
|
f****4
发帖数: 1359 | 6 恩，我的意思就是list的binary search。。。
顺带的，大家都是在哪里看这些题目啊？精华区？
【在 s*********t 的大作中提到】
: 这个很直观
: binary就是只保留两数组的头K个
: 然后比a[k/2],b[k/2]，每次缩小一般搜索范围
: 如果list指的是链表那还是算了。。
|
c******f
发帖数: 2144 | |
k*******n
发帖数: 8891 | |
t**n
发帖数: 272 | 9 第四题对消法,如果两个整数不一样就消除
一样就计数
(
algorithm
【在 l*********r 的大作中提到】
: 1. Int to string (pay attention to the smallest negative number)
: 2. Given two sorted list, find the k smallest number (binary search)
: 3. You can win three kinds of basketball points, 1 point, 2 points, and 3
: points. Given a total score X, print out all the combination to compose X. (
: recursion/ Dp)
: 4. Given a stream of integers, at a given time, there is a number appeared
: more than half time, how to find this number. (classic streaming algorithm
: )
|
b********9
发帖数: 103 | 10 第四题题目没有看懂啊。有谁能解释一下？多谢！
对消。。。计数。。。以前版上有讨论么？
哪位来帮忙解释一下！多谢！ |
|
|
l*****a
发帖数: 14598 | 11 count=0;
for(int i=0;i
{
if(count==0){temp=a[i];count++;}
else{ if(temp!=a[i]){count--;}
else count++;
}
}
return temp;
【在 b********9 的大作中提到】
: 第四题题目没有看懂啊。有谁能解释一下？多谢！
: 对消。。。计数。。。以前版上有讨论么？
: 哪位来帮忙解释一下！多谢！
|
a*******1
发帖数: 17 | 12 每次删除2个不同的数，那剩下的数中，那个target出现的次数仍然超过总数的一半。
int nTimes = 0;
int target = 0;
for(int i=0; i
if(nTimes==0){
target = a[i];
nTimes = 1;
} else {
if(target==a[i])
nTimes++;
else
nTimes--;
}
}
return target; |
b********9
发帖数: 103 | 13 对吗？
int a[7] = {1,2,2,2,3,3,3};
算完后， nTimes = 1; Target = 3;
3没有超过一半的出现次数
【在 a*******1 的大作中提到】
: 每次删除2个不同的数，那剩下的数中，那个target出现的次数仍然超过总数的一半。
: int nTimes = 0;
: int target = 0;
: for(int i=0; i: if(nTimes==0){
: target = a[i];
: nTimes = 1;
: } else {
: if(target==a[i])
: nTimes++;
|
a*******1
发帖数: 17 | 14 题目的要求是at a given time, there is a number appeared more than half time,
how to find this number. Assumption就是要有一个数出现次数超过半数吧. |
b********9
发帖数: 103 | 15 你是对的。我忽略了这个assmuption。
有这个assumption，其实题目就转化为求出现次数最多的数。出现最多的数也就是出现
超过一半的那个数。所以大家一起对消，最后剩下的总是出现次数最多的那个数。
另外，之前完全误解了题目意思。题目应该编辑为more than half times不是more
than half time。。是次数。。不是时间。。。：）
time,
【在 a*******1 的大作中提到】
: 题目的要求是at a given time, there is a number appeared more than half time,
: how to find this number. Assumption就是要有一个数出现次数超过半数吧.
|
j*****u
发帖数: 1133 | 16 3要注意按一定顺序(比如开始用2了就不能再用3了)，因为1 3 1和3 1 3算一种
【在 m*****g 的大作中提到】
: 3是coin change的一种。就是每个都试，不算dp
: 4前面讨论过好象，就是用一个counter计数
: cnt = 0;
: curNum = 0;
: while(input>>temp)
: {
: if(!cnt) curNum = temp;
: if(temp == curNum)
: cnt++;
: else
|
