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了。 |
|
|
