w**t
发帖数: 23 | 1 summer intern
4个人
第一个：一副牌，52张，如何测试一个洗牌算法是否好
如何设计一个电梯
第二个：逆时针打印一个m*n的矩阵
第三个：A!+B!+C! = ABC, A,B,C都是0-9的数，ABC是这三个digit组成的三位数，问A
B C分 别是几，如果A! + B! + C! + D! = ABCD，那么如何迅速找ABCD
第四个（boss）：一个有序序列，从某个地方rotate，求在rotate的位置，比如
1 3 5 0 0 0，那么rotate的位置是4，他后来只用了4行就写出来了，很nb，被bs了~~ |
g**e
发帖数: 6127 | 2 5!+4!+1!+=145
四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下
A
【在 w**t 的大作中提到】
: summer intern
: 4个人
: 第一个：一副牌，52张，如何测试一个洗牌算法是否好
: 如何设计一个电梯
: 第二个：逆时针打印一个m*n的矩阵
: 第三个：A!+B!+C! = ABC, A,B,C都是0-9的数，ABC是这三个digit组成的三位数，问A
: B C分 别是几，如果A! + B! + C! + D! = ABCD，那么如何迅速找ABCD
: 第四个（boss）：一个有序序列，从某个地方rotate，求在rotate的位置，比如
: 1 3 5 0 0 0，那么rotate的位置是4，他后来只用了4行就写出来了，很nb，被bs了~~
|
v******y
发帖数: 22 | 3 第四个是O(log(n)) 的解法么？四行，牛，求解 |
g**e
发帖数: 6127 | 4 没说ABCD不能相同，实际上ABCD如果不同，是无解的，要再想想
一下
【在 g**e 的大作中提到】
: 5!+4!+1!+=145
: 四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下
:
: A
|
k*****7
发帖数: 72 | 5 1 3 5 0 0 0，为啥rotate的位置是4不是3？
如果1,2,3,4,0,0，那rotate位置按轮转之前还是之后的？
Anyway，用for循环，a[i+1]<=a[i]就return，4行刚好，O(n)时间 |
D*****7
发帖数: 766 | 6 FindRotation(int* array, int start, int end)
{
int middle = (start + end)/2;
if (array[start] <= array[end])
return start;
return (array[start] > array[midlle]) ? FindRotation(array, start,
middle) : FindRotation(array, middle, end);
}
假设是升序排列，大概是这样，没有测试过。
【在 v******y 的大作中提到】
: 第四个是O(log(n)) 的解法么？四行，牛，求解
|
g**e
发帖数: 6127 | |
g**e
发帖数: 6127 | 8 我觉得A!+B!+C!+D!=ABCD这个没有解啊，穷举了一遍也没有
【在 g**e 的大作中提到】
: 没说ABCD不能相同，实际上ABCD如果不同，是无解的，要再想想
:
: 一下
|
g**e
发帖数: 6127 | 9 试试 0 0 0 0 1 0？
你这是O(n)了。我发现这个问题有重复数字的时候写对相当困难 |
c**m
发帖数: 535 | |
|
|
r*******e
发帖数: 7583 | 11 试了，没问题
不是O(n)，最后两行的条件是不会同时发生的，最后一个if clause可以去掉
【在 g**e 的大作中提到】
: 试试 0 0 0 0 1 0？
: 你这是O(n)了。我发现这个问题有重复数字的时候写对相当困难
|
g**e
发帖数: 6127 | 12 我给的这个例子不就是a[mid]==a[low]==a[high]么
【在 r*******e 的大作中提到】
: 试了，没问题
: 不是O(n)，最后两行的条件是不会同时发生的，最后一个if clause可以去掉
|
a***y
发帖数: 117 | 13 hi, how can you get 5!+4！+1！ = 145？ is there any theorem can explain
this or other things?
一下
【在 g**e 的大作中提到】
: 5!+4!+1!+=145
: 四个数的话就在1-7之间选4个，而且一定有7，有5，所以一共有C(2,5)=10种，穷举一下
:
: A
|
r*******e
发帖数: 7583 | 14 恩，是有问题
不过你给的test case在我刚那段代码下结果碰巧是对的
0 1 0 0 0 0才会出问题，这样的情况有点麻烦
【在 g**e 的大作中提到】
: 我给的这个例子不就是a[mid]==a[low]==a[high]么
|
d*******l
发帖数: 338 | 15 careercup的那本书上好像有这题，上面提到如果有重复的话，O(n)是必须的，就拿全
零然后只有一个1的情况来说，1在不同位置都是有可能的，除非把所有位置都看一遍否
则是无法确定的
【在 r*******e 的大作中提到】
: 恩，是有问题
: 不过你给的test case在我刚那段代码下结果碰巧是对的
: 0 1 0 0 0 0才会出问题，这样的情况有点麻烦
|
g**e
发帖数: 6127 | 16 A!+B!+C!=ABC
考虑5!=120, 6!=720，首先不可能有6，不然720里面的7无法实现，所以只可能0-5。
另外一定有5，不然4!x3也不到100. 确定了一个就好办了，另外一定有1，因为最高位
是1.剩下的就是4了
【在 a***y 的大作中提到】
: hi, how can you get 5!+4！+1！ = 145？ is there any theorem can explain
: this or other things?
:
: 一下
|
C*Y
发帖数: 736 | 17 careercup上那道题是在rotated后的array中search某个数
大量duplicate的话就是O(n)的
【在 d*******l 的大作中提到】
: careercup的那本书上好像有这题，上面提到如果有重复的话，O(n)是必须的，就拿全
: 零然后只有一个1的情况来说，1在不同位置都是有可能的，除非把所有位置都看一遍否
: 则是无法确定的
|
d*******l
发帖数: 338 | 18 我也编程试了下没解。。。亏我还在纸上试了半天，不知这题是怎么个意思
【在 g**e 的大作中提到】
: 我觉得A!+B!+C!+D!=ABCD这个没有解啊，穷举了一遍也没有
|
i**9
发帖数: 351 | 19 This question is a bit different with the one on careercup, careercup 上那道
题是search a key,跟这个（只要求找出去拐点,）不一样, so it is doable in O(
lgn) for repeats
【在 d*******l 的大作中提到】
: careercup的那本书上好像有这题，上面提到如果有重复的话，O(n)是必须的，就拿全
: 零然后只有一个1的情况来说，1在不同位置都是有可能的，除非把所有位置都看一遍否
: 则是无法确定的
|
c**y
发帖数: 172 | 20 Binary search works for an array with duplicate elements.
However, a modified binary search doesn't work for a rotated array with
duplicate elements (see Careercup book p181).
So how should we deal with a rotated array without duplicate elements?
Trying to use the modified binary search is good, but it is hard to remember
. We can first locate the special location, and then use the ordinary binary
search in the "right" range. |
|
|
B*M
发帖数: 1340 | 21 你咋那么聪明哪！
【在 g**e 的大作中提到】
: 我给的这个例子不就是a[mid]==a[low]==a[high]么
|
B*M
发帖数: 1340 | 22 这个rotate是什么意思？没懂
A
【在 w**t 的大作中提到】
: summer intern
: 4个人
: 第一个：一副牌，52张，如何测试一个洗牌算法是否好
: 如何设计一个电梯
: 第二个：逆时针打印一个m*n的矩阵
: 第三个：A!+B!+C! = ABC, A,B,C都是0-9的数，ABC是这三个digit组成的三位数，问A
: B C分 别是几，如果A! + B! + C! + D! = ABCD，那么如何迅速找ABCD
: 第四个（boss）：一个有序序列，从某个地方rotate，求在rotate的位置，比如
: 1 3 5 0 0 0，那么rotate的位置是4，他后来只用了4行就写出来了，很nb，被bs了~~
|
a***y
发帖数: 117 | 23 thanks, gate, good explanation.
【在 g**e 的大作中提到】
: A!+B!+C!=ABC
: 考虑5!=120, 6!=720，首先不可能有6，不然720里面的7无法实现，所以只可能0-5。
: 另外一定有5，不然4!x3也不到100. 确定了一个就好办了，另外一定有1，因为最高位
: 是1.剩下的就是4了
|
