a**********2 发帖数: 340 | 1 选出了最大的那个数以后,较小的数不需要跟较大数理的每个数进行比较,只需要跟那些
跟最大数比较过的数进行比较,所以
是logn 而不是n/2 |
|
q****x 发帖数: 7404 | 2 要求O(1) space的话,怎么记住哪些数和最大数比较过? |
|
a**********2 发帖数: 340 | 3 选出了最大的那个数以后,较小的数不需要跟较大数理的每个数进行比较,只需要跟那些
跟最大数比较过的数进行比较,所以
是logn 而不是n/2 |
|
q****x 发帖数: 7404 | 4 要求O(1) space的话,怎么记住哪些数和最大数比较过? |
|
a****a 发帖数: 186 | 5 Given a number find whether the digits in the number can be used to form an
equation with + and '='. That is if the number is 123, we can have a
equation of 1+2=3. But even the number 17512 also forms the equation 12+5=17
.就是随便排列数字,用+和=构造等式。加号只能用一次,数字不需要是连续的。
想法:对给定的数进行排列,分成三个数,然后sum两小的是不是等于大的。另外,分的
时候对最大数进行长度限制,貌似可以减少搜索空间。
还有什么其他的好方法吗?我记得好像这个题被讨论过,谁记得那个连接,谢谢! |
|
|
h****e 发帖数: 928 | 7 这道题目如果真是FB的高频题,那就硬背一个最简洁的解法吧。 |
|
f*********i 发帖数: 197 | 8 解法应该是构造一个size 为 k的heap,时间复杂度是O(nlgk)但是有一点我想问大家,
你们是如何判断当前heap最顶端的数是属于哪个数组的呢。用hash的话会有两个key相
同的问题,一个个和数组的数比较的话那就太花时间了。
请问有没有比较好的方法判断。 |
|
|
|
|
|
d********t 发帖数: 9628 | 13 N组整数,每组都由小到大排列,如何快速找出N组都有的最大数? |
|
p*****2 发帖数: 21240 | 14
这题好像没练过。先说说我的想法再去看leetcode。
用一个queue,第一个数总保持最大的值。
每当读一个新数,如果当前最大数过了window,就pop,然后如果当前的数小于最后的
数,push进去。
如果当前的数大于尾巴, 把尾巴干掉。 |
|
p*****2 发帖数: 21240 | 15
这题好像没练过。先说说我的想法再去看leetcode。
用一个queue,第一个数总保持最大的值。
每当读一个新数,如果当前最大数过了window,就pop,然后如果当前的数小于最后的
数,push进去。
如果当前的数大于尾巴, 把尾巴干掉。 |
|
C***U 发帖数: 2406 | 16 假设我有一个正整数n,我要把他写成一些正整数的和。是组合问题,也就是说数字的
顺序不考虑。
有什么好的办法没有
我写了一个recrusive的,请大牛们指教一下
int count = 0;
//构造以max为最大数的 number的partition
void partitionWithMax(int number, int max) {
if(!number) {
count++;
return;
}
else {
int newMax = number > max ? max : number;
for(int i = newMax; i > 0; i--) {
partitionWithMax(number - i, i);
}
}
}
//让max从1到number都走一边
void partition(int number) {
for(int i = number; i > 0; i--) {
partitionW... 阅读全帖 |
|
S*******e 发帖数: 379 | 17 简单版本有这么复杂吗? 难道我们说的是不同方法?
我是说哪种最简单的
123 x 12,先做123x2,存到数组里,在做123x1,移位后加到数组里,10分钟差不多了把 |
|
b***m 发帖数: 5987 | 18 貌似可以考虑不要把当前行的最小数字减到1,这样要double好多次才能尽量跟最大数
凑齐。也许可以考虑什么公倍数之类的? |
|
c********t 发帖数: 5706 | 19 这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。 |
|
c********t 发帖数: 5706 | 20 这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。 |
|
c********t 发帖数: 5706 | 21 明白了,多谢!
把你说的扩展为n,要开至少n空间,存所有path,(用map好些)divide and conquer,
(如果每次不释放被conquer的数的path的话,还需要更多空间)最后留下最大数,和
它的path,这时候的path应该是lgn的。理论上比较次数为 n+lgn-1,但是存储读写次
数增加很多,时间优化了吗? |
|
c*u 发帖数: 22 | 22 来自主题: JobHunting版 - 请教一道题 第一次循环把数存到HashSet
第二次循环对HashSet删减,记录最大数
最后输出
C#
int[] array = { 8, 15, 5, 7, 12, 6, 14, 13, 9, 11, 8 };
HashSet set = new HashSet();
foreach (int val in array)
if (!set.Contains(val))
set.Add(val);
int min = 0, max = 0, maxCount = 0;
while (set.Count > 0)
{
int left = 0, right = 0, count = 1;
int val = set.First();
int now = val + 1;
while (set.Contains(now))
{
count++;
set.Remove(now);
now++;
}
right = now - 1;
now... 阅读全帖 |
|
e****e 发帖数: 418 | 23 多谢详细解答。差值相等的情况应该比较常见,例如第一个例子2 5 4 6里,差值2和1
各有两个duplicates.
我在想,也许heap或者改进型的heap或者其他类似数据结构,可以处理数值想等的情况
,就是多pop出几次相同的最大数而已。或者heap的元素类型就是list。unique的数值
, list含一个值,duplicate的数值,list含多个值,反正heap的元素类型要包含i和j
的值,i和j是原数组的下标智,它们的差值的绝对值就是a(i,j),也是heap insert(),
max()运算的依据。 |
|
s*****1 发帖数: 134 | 24 bless~
先Binary Search找最大数,再两个单调递增或递减的binary search找那个值 |
|
b******z 发帖数: 410 | 25 收到包袱:150k, 12.5%, 5000sh/4, 30k 签字费。热哭特说是老年的最大数。不知还
能不能多要?
硕士10年经验。 |
|
h****p 发帖数: 87 | 26 RT,感觉这个面试经常会问到,自己想到的是linked list, string
这题怎么做比较好?
求大牛们给个最优解 多谢 |
|
e*******8 发帖数: 94 | 27 这题programming problems上有. 用vector,然后从最低位存到最高
位。加和乘都是用的256-进制的.
乘法给了两个算法:一个就是小学学的那种算法,另外一个是karatsuba算法. |
|
|
A***o 发帖数: 358 | 29 Linear hashing, extensible hashing
如果有1M个数,每个数大概是100,0000,0000这样的整数,是不是hash table的size也
要很大啊,比如说等于数组中的最大数。最近做coursera上的algor........ |
|
g*********e 发帖数: 14401 | 30 来自主题: JobHunting版 - 周末上道题 一个heap不就可以了吗?
另外为啥是minheap? 我一直分不清max heap min heap哪个存最大数 |
|
z****e 发帖数: 54598 | 31 面试白板编程并不是要求你上来就背出最优解
很多时候是看你是否有个清晰的解题思路
这题如果你能把问题分拆,拆成一小快一小块
我觉得这更符合实际工作中的解题思路 |
|
b********6 发帖数: 97 | 32 举个例子吧,输入是一个数组 int[] a = {9,9},
那么 99+1 结果是 100,
返回一个 数组 int[] 为 {1,0,0}
如果输入是 {9,8}
返回的就是 {9,9}
做法就是从最高位加一后,记录overflow,从右向左扫一遍就好了。 |
|
w*********0 发帖数: 147 | 33 应该用divide and conquer就能解决吧,就在合并是比前两个最大值,就能得到第二个
最大数。 |
|
c****n 发帖数: 105 | 34 来自主题: JobHunting版 - 谈G家面经 输入数组是无序的,我给的是下面的方法
先scan 一遍,找出最大数max和出现的次数n
然后生成一个随机数m,between 1 to n
然后在scan一遍,找到第m个max,输出idx |
|
Z**********4 发帖数: 528 | 35 来自主题: JobHunting版 - 谈G家面经 可以这么做:
先必须用一个maxValue记录最大数的值,用作比对。
然后还需要记录maxIndex就是最大值所在的index.
还需要一个occur记录最大值出现的个数。
每次如果遇到一个没有当前maxValue大的数字,无视之。
如果遇到一个比当前maxValue大的数字,当然要更新maxValue. 而且也可以放心地更新
maxIndex,因为目前最大值是第一次出现。 occur也reset到1.
问题关键在于出现跟maxValue一样大的数字如何操作。就需要random地替换一个。先更
新orrcur让orrcur++
然后出个随机数使得当前的这个index有1/occur的概率被采用即可。
随机数可以就用C里面的 (rand()%occur + 1)这个范围就是[1, occur]而且可以
assume是等概率。
如果这个随机数==1, 那么就把当前的maxIndex更新,不然就do nothing.
数学证明应该可以用数学归纳法,这里只推前三个。
假设最大值出现的index是i1, i2, i3
P(maxIndex == i1) = 1 * (1-1/2) *(1-1/... 阅读全帖 |
|
m*****n 发帖数: 2152 | 36 没懂啊,find the biggest number that you can reach to via n swaps 是不是指经
过n swaps,最大数被换到数组头?
这个不是找n+1中的最大值,然后换到第一个吗? |
|
t***t 发帖数: 6066 | 37 这个跟数组元素个数和最大值都有关。
假设n个数,最大数是m,求最大质数肯定跟n,m都有关。 |
|
a***s 发帖数: 616 | 38 可以证明40开始的都不可以。6其实没啥用,6k = 2*3k。20除以3余2。
任何一个数除以3的余数为0, 1, 或2。所以当一个数a大于等于40时,
1.余0 =〉a = 3k;
2.余1 => a-2*20 = 3k;
3.余2 => a-20 = 3k。
所以从39开始倒着考虑。
39 = 3*13 + 0
38 = 3*12 + 2 = 20 + 3*6
37 = 3*12 + 1 = 20*2 + (-1)*3 不合法
所以最大数是37
one |
|
e***m 发帖数: 92 | 39 “然后把匹配以后每对数(一 个老鼠一个洞)的差的绝对值相加,求最小值“
--------难道不是最小化差的绝对值的最大数吗? |
|
z*******g 发帖数: 103 | 40 感觉最大应该这么定义:有唯一一个数与他所有数compare以后都显示这个数比较大。
那么从左取第一个数开始,与第二个compare,直到某个数比他大(如果到最后,那就
他最大)。然后从比他大的那个数开始重复上述过程。
例子如下: a, b, c, d, e, f, g, h, i, j, k
假设 a比b,c,d大,比e小,那么排除a, b,c,d;最大数只能在剩下的数里。
这样就相当回到了问题开始,不过砍掉了a,b,c,d
看了应该是 O(n)吧 |
|
F*****o 发帖数: 32 | 41 你的solution应该不是constant space.因为你额外数组的大小是基于最大数的大小。
In this case: A=[1,2,3,4,...,n],it is O(n).
所谓的constant space,是指无论input是什么样子的数组,你的space是constant。
所以,本题要在原数组中做文章。 |
|
n*******s 发帖数: 17267 | 42 直觉就是每次把index a->b的加K, 最后再选个最大数就可以了。 |
|
n*******s 发帖数: 17267 | 43 改了, 呵呵, 其实就是问你怎么找最大数吧?
或许需要改进一下, 只需要搜索最小的a和最大的b之间就可以了, 还需要改善的话,
就已经不是年老色衰的人能想明白的了。 |
|
|
|
|
s******n 发帖数: 793 | 47 BOA在建行取钱没费用
2011/06
连取了四次,每次一千取了四千(也可能是五千,记不清了)
不过点一下只能取一千,再继续取...
美国这边也差不多,ATM上一次最大数是800,我一般取一千以上得两次 |
|
s******n 发帖数: 793 | 48 BOA在建行取钱没费用
2011/06
连取了四次,每次一千取了四千(也可能是五千,记不清了)
不过点一下只能取一千,再继续取...
美国这边也差不多,ATM上一次最大数是800,我一般取一千以上得两次 |
|
Z**********g 发帖数: 14173 | 49 看他气度,最多一年14万
不过也不少了,顶估计30个Echowood了。 |
|
|