f*2
2 楼
2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
algorithm to change this array to a1, b1, a2, b2, ..., an, bn
答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
假设是int型，这样写行不行：
int *rearrange(int *arr, int N)
{
if (arr == NULL)
return NULL;
int new_arr[2*N];
for (int i = 0; i < N; i++)
{
new_arr[2*i] = arr[i];
new_arr[2*i+1] = arr[N+i];
}
arr = new_arr;
return arr;
}
algorithm to change this array to a1, b1, a2, b2, ..., an, bn
答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
假设是int型，这样写行不行：
int *rearrange(int *arr, int N)
{
if (arr == NULL)
return NULL;
int new_arr[2*N];
for (int i = 0; i < N; i++)
{
new_arr[2*i] = arr[i];
new_arr[2*i+1] = arr[N+i];
}
arr = new_arr;
return arr;
}
D*d
3 楼
有 O(n) 的算法, 以下是我的解法:
if i in [0 ... n-1], ==> 2*i
if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
, then
0 --> 0,
1 --> 1 * 2 = 2,
2 --> 2 * 2 = 4,
4 --> (4-3+1)*2-1 = 3
3 --> (3-3+1)*2-1 = 1
an
【在 f*****2 的大作中提到】
: 2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
: algorithm to change this array to a1, b1, a2, b2, ..., an, bn
: 答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
: 额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
: 另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
: 假设是int型，这样写行不行：
: int *rearrange(int *arr, int N)
: {
: if (arr == NULL)
: return NULL;
if i in [0 ... n-1], ==> 2*i
if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
, then
0 --> 0,
1 --> 1 * 2 = 2,
2 --> 2 * 2 = 4,
4 --> (4-3+1)*2-1 = 3
3 --> (3-3+1)*2-1 = 1
an
【在 f*****2 的大作中提到】
: 2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
: algorithm to change this array to a1, b1, a2, b2, ..., an, bn
: 答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
: 额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
: 另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
: 假设是int型，这样写行不行：
: int *rearrange(int *arr, int N)
: {
: if (arr == NULL)
: return NULL;
f*2
4 楼
你是指不定义其他数组也有O（n）的解法吗？你的方法也得定义一个新数组吧？
【在 D**********d 的大作中提到】
: 有 O(n) 的算法, 以下是我的解法:
: if i in [0 ... n-1], ==> 2*i
: if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
: 从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
: 算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
: , then
: 0 --> 0,
: 1 --> 1 * 2 = 2,
: 2 --> 2 * 2 = 4,
: 4 --> (4-3+1)*2-1 = 3
【在 D**********d 的大作中提到】
: 有 O(n) 的算法, 以下是我的解法:
: if i in [0 ... n-1], ==> 2*i
: if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
: 从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
: 算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
: , then
: 0 --> 0,
: 1 --> 1 * 2 = 2,
: 2 --> 2 * 2 = 4,
: 4 --> (4-3+1)*2-1 = 3
s*r
5 楼
完美洗牌问题
s*r
6 楼
有时间 O(N) 空间 O(1) 的解法
这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle
这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle
s*u
7 楼
ccup指的是cc150？第二章不是链表么。。。
l*n
8 楼
这题很有意思的，总体思路就是存下个位置的值nextVal，把当前位置的值currVal填进
去，然后处理刚才记住的nextVal，如此重复。但是这种重复虽然自身会形成一个环，
整个问题却有多个环。比如下面的例子，1构成一个，2、3、5构成一个，4、6、7构成
一个，8再一个。[1, 2, 4, 8]是每个环的起点。
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 5, 2, 6, 3, 7, 4, 8]
O(n)时间O(1)空间的解法某种意义上就是能算出来每个环的起点。下面是2~34长度的数
组的环的起点，1、2和数组长度自身肯定包含，但是余下的好像很难看出来直接的规律。
[1, 2]
[1, 2, 4]
[1, 2, 6]
[1, 2, 4, 8]
[1, 2, 4, 10]
[1, 2, 12]
[1, 2, 14]
[1, 2, 4, 6, 8, 16]
[1, 2, 4, 18]
[1, 2, 20]
[1, 2, 4, 6, 8, 10, 22]
[1, 2, 6, 24]
[1, 2, 6, 26]
[1, 2, 4, 10, 28]
[1, 2, 30]
[1, 2, 4, 6, 8, 12, 16, 32]
[1, 2, 4, 6, 12, 34]
【在 s*****r 的大作中提到】
: 有时间 O(N) 空间 O(1) 的解法
: 这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
: MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle
去，然后处理刚才记住的nextVal，如此重复。但是这种重复虽然自身会形成一个环，
整个问题却有多个环。比如下面的例子，1构成一个，2、3、5构成一个，4、6、7构成
一个，8再一个。[1, 2, 4, 8]是每个环的起点。
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 5, 2, 6, 3, 7, 4, 8]
O(n)时间O(1)空间的解法某种意义上就是能算出来每个环的起点。下面是2~34长度的数
组的环的起点，1、2和数组长度自身肯定包含，但是余下的好像很难看出来直接的规律。
[1, 2]
[1, 2, 4]
[1, 2, 6]
[1, 2, 4, 8]
[1, 2, 4, 10]
[1, 2, 12]
[1, 2, 14]
[1, 2, 4, 6, 8, 16]
[1, 2, 4, 18]
[1, 2, 20]
[1, 2, 4, 6, 8, 10, 22]
[1, 2, 6, 24]
[1, 2, 6, 26]
[1, 2, 4, 10, 28]
[1, 2, 30]
[1, 2, 4, 6, 8, 12, 16, 32]
[1, 2, 4, 6, 12, 34]
【在 s*****r 的大作中提到】
: 有时间 O(N) 空间 O(1) 的解法
: 这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
: MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle
T*e
9 楼
我对你的代码有疑问，你生成的new_arr是分配在stack上的，这样当函数结束的时候这
个区域就要被删除了，返回的指针指向的区域是非法的。你这段代码通过测试了吗？
个区域就要被删除了，返回的指针指向的区域是非法的。你这段代码通过测试了吗？
相关阅读
收到据信了，随便写点三个月的OFFER可以接吗？求EBAY的REFER收到OFFER,纠结于去工作还是读PHDOffer 的几个问题Does stem OPT extension qualify for h1-b cap-gap extension ????如果有绿卡，需要在CV里注明么？怎么注明？被DREAM COMPANY拒了，极度郁闷快要得抑郁症了谁来科普一下背景调查都查些什么东西？Z今天上市了吗？onsite结果等了快两周了。。不淡定了。。求祝福。。h1b visa 资料里面的工资包含bonus吗?(Updated) 不淡定了，求blessBloomberg R&D online exam主要考什么？电面最后要对方的电话或者email是不是很不好Qualcomm的Destination Q问H1B问题请大牛们推荐java junior position面试的书 (转载)这种情况该怎么办？