a*0
2 楼
穆迪谈到在和八马讨论social security agreement, 这个会包括h4 EAD吗？ 我靠，不
会等到最后人家出一个agreement，h4EAD是India only的政策吧
会等到最后人家出一个agreement，h4EAD是India only的政策吧
h*g
3 楼
眼角膜算长好了吗？跳闪的话，有影响吗？
N*N
4 楼
题目应该是a1b2c3d4?
确定是字母顺序都排好序的，而且交替出现的吗？
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
确定是字母顺序都排好序的，而且交替出现的吗？
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
x*z
5 楼
从哪得知的？
现在H4ead的road block是国会，不是总统
国会不给DHS funding去干EA，那么uscis就没钱招人来处理EAD application,那就干脆
不让政策生效。就这么简单，哦巴马再同意也没用。
【在 a*0 的大作中提到】
: 穆迪谈到在和八马讨论social security agreement, 这个会包括h4 EAD吗？ 我靠，不
: 会等到最后人家出一个agreement，h4EAD是India only的政策吧
现在H4ead的road block是国会，不是总统
国会不给DHS funding去干EA，那么uscis就没钱招人来处理EAD application,那就干脆
不让政策生效。就这么简单，哦巴马再同意也没用。
【在 a*0 的大作中提到】
: 穆迪谈到在和八马讨论social security agreement, 这个会包括h4 EAD吗？ 我靠，不
: 会等到最后人家出一个agreement，h4EAD是India only的政策吧
q*z
6 楼
这么大,应该可以吧.
看到焦外的光圈是多边形的
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
看到焦外的光圈是多边形的
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
d*o
7 楼
这种题就是quick sort中的partition那一步。
看到abcd就放到前面去。
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
看到abcd就放到前面去。
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
t*t
8 楼
国会有权决定funding的用途么？（比如规定DHS funding中的一部分只能用于h4 ead这
样）这样算不算立法干预行政？
【在 x*z 的大作中提到】
: 从哪得知的？
: 现在H4ead的road block是国会，不是总统
: 国会不给DHS funding去干EA，那么uscis就没钱招人来处理EAD application,那就干脆
: 不让政策生效。就这么简单，哦巴马再同意也没用。
样）这样算不算立法干预行政？
【在 x*z 的大作中提到】
: 从哪得知的？
: 现在H4ead的road block是国会，不是总统
: 国会不给DHS funding去干EA，那么uscis就没钱招人来处理EAD application,那就干脆
: 不让政策生效。就这么简单，哦巴马再同意也没用。
S*M
9 楼
这种去mall里跟santa或者easter bunny照相都是要打闪光灯的
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
b*8
10 楼
感觉很像用位操作去解。。。
h*g
11 楼
不知道为什么会这样，大概镜头里有灰的关系吧，我新的买了没拆洗过
【在 q*z 的大作中提到】
: 这么大,应该可以吧.
: 看到焦外的光圈是多边形的
【在 q*z 的大作中提到】
: 这么大,应该可以吧.
: 看到焦外的光圈是多边形的
b*y
12 楼
careercup上的面经。。。感觉问的应该是把偶数index上的挪到后面
比如jacket->jceakt
给的例子太特殊了，估计是为了容易看懂？
比如jacket->jceakt
给的例子太特殊了，估计是为了容易看懂？
h*g
13 楼
我这是抢拍，父母都在旁边，不太好意思打闪。。。而且外闪也没带
【在 S*M 的大作中提到】
: 这种去mall里跟santa或者easter bunny照相都是要打闪光灯的
【在 S*M 的大作中提到】
: 这种去mall里跟santa或者easter bunny照相都是要打闪光灯的
m*x
14 楼
divide and conquer, nlogn
【在 b*******y 的大作中提到】
: careercup上的面经。。。感觉问的应该是把偶数index上的挪到后面
: 比如jacket->jceakt
: 给的例子太特殊了，估计是为了容易看懂？
【在 b*******y 的大作中提到】
: careercup上的面经。。。感觉问的应该是把偶数index上的挪到后面
: 比如jacket->jceakt
: 给的例子太特殊了，估计是为了容易看懂？
q*z
15 楼
可以很明显的看到8边形,是8片光圈的镜头?
【在 h*******g 的大作中提到】
: 不知道为什么会这样，大概镜头里有灰的关系吧，我新的买了没拆洗过
【在 h*******g 的大作中提到】
: 不知道为什么会这样，大概镜头里有灰的关系吧，我新的买了没拆洗过
l*c
16 楼
for(int i = 0; pow(2,(i+2)) <= n; i++) {
for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
for (int tmp = 0; tmp < pow(2,i); tmp++) {
swap(s[j], s[j+pow(2,i)]);
}
}
}
怎么觉得很难写啊，思路如下
a1b2c3d4.... -> ab12cd34 ->abcd1234
我算是抛个破砖吗
for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
for (int tmp = 0; tmp < pow(2,i); tmp++) {
swap(s[j], s[j+pow(2,i)]);
}
}
}
怎么觉得很难写啊，思路如下
a1b2c3d4.... -> ab12cd34 ->abcd1234
我算是抛个破砖吗
T*r
17 楼
一直有很多人说对宝宝拍照用闪光灯不好, 可能会伤眼睛. 我想问这些
人的问题是, 你认为宝宝多大以后拍照用闪光灯才不会伤眼睛? 六个月?
一岁? 两岁? 三岁? 十岁? 十八岁? 不管你给出什么答案, 说说理由吧.
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
人的问题是, 你认为宝宝多大以后拍照用闪光灯才不会伤眼睛? 六个月?
一岁? 两岁? 三岁? 十岁? 十八岁? 不管你给出什么答案, 说说理由吧.
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
a*y
18 楼
just swap at different stage with different position，常见提原体应该是
a1a2a3b1b2b3
a1a2a3b1b2b3
h*g
19 楼
P+大公主
【在 q*z 的大作中提到】
: 可以很明显的看到8边形,是8片光圈的镜头?
【在 q*z 的大作中提到】
: 可以很明显的看到8边形,是8片光圈的镜头?
d*x
20 楼
关键字：置换群
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
S*M
21 楼
我是说她这个年龄可以闪了
具体这张照片，显然没必要用闪光灯
【在 h*******g 的大作中提到】
: 我这是抢拍，父母都在旁边，不太好意思打闪。。。而且外闪也没带
具体这张照片，显然没必要用闪光灯
【在 h*******g 的大作中提到】
: 我这是抢拍，父母都在旁边，不太好意思打闪。。。而且外闪也没带
e*e
22 楼
Agree.
public void convert(char[] a) {
swap(a, 1, 2);
swap(a, 5, 6);
swap(a, 2, 4);
swap(a, 3, 5);
}
private void swap( char[] a, int i, int j ) {
char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
【在 l****c 的大作中提到】
: for(int i = 0; pow(2,(i+2)) <= n; i++) {
: for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
: for (int tmp = 0; tmp < pow(2,i); tmp++) {
: swap(s[j], s[j+pow(2,i)]);
: }
: }
: }
: 怎么觉得很难写啊，思路如下
: a1b2c3d4.... -> ab12cd34 ->abcd1234
: 我算是抛个破砖吗
public void convert(char[] a) {
swap(a, 1, 2);
swap(a, 5, 6);
swap(a, 2, 4);
swap(a, 3, 5);
}
private void swap( char[] a, int i, int j ) {
char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
【在 l****c 的大作中提到】
: for(int i = 0; pow(2,(i+2)) <= n; i++) {
: for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
: for (int tmp = 0; tmp < pow(2,i); tmp++) {
: swap(s[j], s[j+pow(2,i)]);
: }
: }
: }
: 怎么觉得很难写啊，思路如下
: a1b2c3d4.... -> ab12cd34 ->abcd1234
: 我算是抛个破砖吗
q*z
23 楼
其实更多的是心理作用,没有理论证明,小孩的眼睛一定会被闪光灯
伤害,有的小孩从小被闪,似乎也没事.
但是小孩小的时候会被突然的强光吓到,这样你也拍不下去了.
大人在旁边看到这样也会心疼.
【在 T********r 的大作中提到】
: 一直有很多人说对宝宝拍照用闪光灯不好, 可能会伤眼睛. 我想问这些
: 人的问题是, 你认为宝宝多大以后拍照用闪光灯才不会伤眼睛? 六个月?
: 一岁? 两岁? 三岁? 十岁? 十八岁? 不管你给出什么答案, 说说理由吧.
伤害,有的小孩从小被闪,似乎也没事.
但是小孩小的时候会被突然的强光吓到,这样你也拍不下去了.
大人在旁边看到这样也会心疼.
【在 T********r 的大作中提到】
: 一直有很多人说对宝宝拍照用闪光灯不好, 可能会伤眼睛. 我想问这些
: 人的问题是, 你认为宝宝多大以后拍照用闪光灯才不会伤眼睛? 六个月?
: 一岁? 两岁? 三岁? 十岁? 十八岁? 不管你给出什么答案, 说说理由吧.
t*h
24 楼
remember the last unswapped digit, and swap it with next letter?
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
h*g
25 楼
这焦外的光斑怎么这样。。。我大公主用到现在，第一次出线八角形的
【在 S*M 的大作中提到】
: 我是说她这个年龄可以闪了
: 具体这张照片，显然没必要用闪光灯
【在 S*M 的大作中提到】
: 我是说她这个年龄可以闪了
: 具体这张照片，显然没必要用闪光灯
a*s
26 楼
你这个题目有歧义，首先问清楚abcd是不是要有顺序大小要求，1234也是一样，
c3a5d1 是不是要写成cad351
因为看上去是要排序的，要排序就不太可能O（n）了吧。
周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
伪代码：
1） 边界条件1： 全是字母
2） 边界条件2： 全是数字
3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
环，循环里面怎么写，不用讲了吧。
c3a5d1 是不是要写成cad351
因为看上去是要排序的，要排序就不太可能O（n）了吧。
周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
伪代码：
1） 边界条件1： 全是字母
2） 边界条件2： 全是数字
3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
环，循环里面怎么写，不用讲了吧。
c*y
27 楼
这个难道不是很正常？你以为大公主就能违背物理定律了？
【在 h*******g 的大作中提到】
: 这焦外的光斑怎么这样。。。我大公主用到现在，第一次出线八角形的
【在 h*******g 的大作中提到】
: 这焦外的光斑怎么这样。。。我大公主用到现在，第一次出线八角形的
m*k
28 楼
假设是不需要排序的,即数字和字母各在一边,保持原来顺序.
你能详细讲一下你的做法吗? 两个指针这个没看明白.
【在 a*****s 的大作中提到】
: 你这个题目有歧义，首先问清楚abcd是不是要有顺序大小要求，1234也是一样，
: c3a5d1 是不是要写成cad351
: 因为看上去是要排序的，要排序就不太可能O（n）了吧。
: 周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
: 伪代码：
: 1） 边界条件1： 全是字母
: 2） 边界条件2： 全是数字
: 3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
: 一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
: 环，循环里面怎么写，不用讲了吧。
你能详细讲一下你的做法吗? 两个指针这个没看明白.
【在 a*****s 的大作中提到】
: 你这个题目有歧义，首先问清楚abcd是不是要有顺序大小要求，1234也是一样，
: c3a5d1 是不是要写成cad351
: 因为看上去是要排序的，要排序就不太可能O（n）了吧。
: 周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
: 伪代码：
: 1） 边界条件1： 全是字母
: 2） 边界条件2： 全是数字
: 3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
: 一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
: 环，循环里面怎么写，不用讲了吧。
q*z
29 楼
查了一下,大公主还真是8片光圈叶片
【在 h*******g 的大作中提到】
: 这焦外的光斑怎么这样。。。我大公主用到现在，第一次出线八角形的
【在 h*******g 的大作中提到】
: 这焦外的光斑怎么这样。。。我大公主用到现在，第一次出线八角形的
C*y
30 楼
还是不明白
能讲稍微详细一点吗
谢谢
【在 a*****s 的大作中提到】
: 你这个题目有歧义，首先问清楚abcd是不是要有顺序大小要求，1234也是一样，
: c3a5d1 是不是要写成cad351
: 因为看上去是要排序的，要排序就不太可能O（n）了吧。
: 周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
: 伪代码：
: 1） 边界条件1： 全是字母
: 2） 边界条件2： 全是数字
: 3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
: 一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
: 环，循环里面怎么写，不用讲了吧。
能讲稍微详细一点吗
谢谢
【在 a*****s 的大作中提到】
: 你这个题目有歧义，首先问清楚abcd是不是要有顺序大小要求，1234也是一样，
: c3a5d1 是不是要写成cad351
: 因为看上去是要排序的，要排序就不太可能O（n）了吧。
: 周一刚遇到一个偶数奇数群置换问题。确实只需要O（n）
: 伪代码：
: 1） 边界条件1： 全是字母
: 2） 边界条件2： 全是数字
: 3） 字母数字混合情况： 两个指针，一个指在字符串头，一个指在字符串尾，用
: 一个循环，如果第一个指针小于第二个指针（我只的是指针指的数组index大小）就循
: 环，循环里面怎么写，不用讲了吧。
T*r
31 楼
有多少这样的例子, 举几个吧. 俺先举自己的例子, 俺家两娃被俺闪了
无数次, 俺记忆中连一次这样的例子都没见过.
【在 q*z 的大作中提到】
: 查了一下,大公主还真是8片光圈叶片
无数次, 俺记忆中连一次这样的例子都没见过.
【在 q*z 的大作中提到】
: 查了一下,大公主还真是8片光圈叶片
i*7
32 楼
今天碰到同样的题目。
对方说明如果是a3b4d2c1
最后排出来的要是abcd1234。。。
最后果断开了两个数组做counting sort。。然后我想应该就是O(n) O(1)了。
对方说明如果是a3b4d2c1
最后排出来的要是abcd1234。。。
最后果断开了两个数组做counting sort。。然后我想应该就是O(n) O(1)了。
h*g
33 楼
哈哈=。=我以为是镜头里的灰衍射出来的。。。
【在 c********y 的大作中提到】
: 这个难道不是很正常？你以为大公主就能违背物理定律了？
【在 c********y 的大作中提到】
: 这个难道不是很正常？你以为大公主就能违背物理定律了？
i*7
34 楼
但其实如果是a3b4d2c1的话，我只能提出一个O(nlogn) O(1)的算法了。
题目其实和某个微软题类似，就是把正负数分开，但是顺序不变的那种
类似与mergesort的思想，然后swap range。
题目其实和某个微软题类似，就是把正负数分开，但是顺序不变的那种
类似与mergesort的思想，然后swap range。
d*0
35 楼
大公主到底好玩不，看评价好像毁誉参半呀
g*e
36 楼
why is this O(1)?
【在 i*********7 的大作中提到】
: 今天碰到同样的题目。
: 对方说明如果是a3b4d2c1
: 最后排出来的要是abcd1234。。。
: 最后果断开了两个数组做counting sort。。然后我想应该就是O(n) O(1)了。
【在 i*********7 的大作中提到】
: 今天碰到同样的题目。
: 对方说明如果是a3b4d2c1
: 最后排出来的要是abcd1234。。。
: 最后果断开了两个数组做counting sort。。然后我想应该就是O(n) O(1)了。
S*M
37 楼
你啥时候有俩娃了?
gongxi gongxi
【在 T********r 的大作中提到】
: 有多少这样的例子, 举几个吧. 俺先举自己的例子, 俺家两娃被俺闪了
: 无数次, 俺记忆中连一次这样的例子都没见过.
gongxi gongxi
【在 T********r 的大作中提到】
: 有多少这样的例子, 举几个吧. 俺先举自己的例子, 俺家两娃被俺闪了
: 无数次, 俺记忆中连一次这样的例子都没见过.
vn
38 楼
这个应该可以O(n)O(1)做出来
主要思路就是
0 1 2 3 4 5 6 7 变成
0 2 4 6 1 3 5 7
把1先存着用2顶 再把空出的2的位置用4顶。。。下一步在从3下手
必须一步到位
不可能一点一点的挪
但是具体算法 似乎很麻烦 有人想出来叫唤下～～
主要思路就是
0 1 2 3 4 5 6 7 变成
0 2 4 6 1 3 5 7
把1先存着用2顶 再把空出的2的位置用4顶。。。下一步在从3下手
必须一步到位
不可能一点一点的挪
但是具体算法 似乎很麻烦 有人想出来叫唤下～～
h*g
39 楼
我主力人像头=。=因为没别的选择了
【在 d*****0 的大作中提到】
: 大公主到底好玩不，看评价好像毁誉参半呀
【在 d*****0 的大作中提到】
: 大公主到底好玩不，看评价好像毁誉参半呀
vn
40 楼
想想这些题就算真的实际出现了 如果不是特别需要performance 谁花那个时间做这种
优化啊
想着想着就觉得自己做题在浪费时间。。。
优化啊
想着想着就觉得自己做题在浪费时间。。。
q*z
41 楼
我的小孩曾经被爷爷闪哭了
【在 T********r 的大作中提到】
: 有多少这样的例子, 举几个吧. 俺先举自己的例子, 俺家两娃被俺闪了
: 无数次, 俺记忆中连一次这样的例子都没见过.
【在 T********r 的大作中提到】
: 有多少这样的例子, 举几个吧. 俺先举自己的例子, 俺家两娃被俺闪了
: 无数次, 俺记忆中连一次这样的例子都没见过.
b*y
42 楼
这个和我想的一样。。。
但是不整齐的就没戏了
ａ１ｂ２ｃ３ｄ４ｅ５ｆ６
这个就不好换了
【在 l****c 的大作中提到】
: for(int i = 0; pow(2,(i+2)) <= n; i++) {
: for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
: for (int tmp = 0; tmp < pow(2,i); tmp++) {
: swap(s[j], s[j+pow(2,i)]);
: }
: }
: }
: 怎么觉得很难写啊，思路如下
: a1b2c3d4.... -> ab12cd34 ->abcd1234
: 我算是抛个破砖吗
但是不整齐的就没戏了
ａ１ｂ２ｃ３ｄ４ｅ５ｆ６
这个就不好换了
【在 l****c 的大作中提到】
: for(int i = 0; pow(2,(i+2)) <= n; i++) {
: for(int j = pow(2,i)+ 1; j < n; j = j +pow(2,(i+2))) {
: for (int tmp = 0; tmp < pow(2,i); tmp++) {
: swap(s[j], s[j+pow(2,i)]);
: }
: }
: }
: 怎么觉得很难写啊，思路如下
: a1b2c3d4.... -> ab12cd34 ->abcd1234
: 我算是抛个破砖吗
T*r
43 楼
上个月老二出生 :)
【在 S*M 的大作中提到】
: 你啥时候有俩娃了?
: gongxi gongxi
【在 S*M 的大作中提到】
: 你啥时候有俩娃了?
: gongxi gongxi
a*s
44 楼
public ArrayList groupSwap(ArrayList str, int i, int j){
int p1=0;
int p2=str.size()-1;
//first consider boundary condition 1 all belongs to group 1
while(Integer.parseInt(str.get(p1).toString())%2==1 && p1
}
//then consider boundary condition 2 all belongs to group2
while(Integer.parseInt(str.get(p2).toString())%2==0 && p1
}
if(p1==p2) return str;
//normal condition
else{
changeValue(str,p1,p2);
//for (int m:str) System.out.print(m+"\t");
p1++;
p2--;
while(p1
p1++;
}
else {
changeValue(str,p1,p2);
p2--;
}
}
return str;
}
}
int p1=0;
int p2=str.size()-1;
//first consider boundary condition 1 all belongs to group 1
while(Integer.parseInt(str.get(p1).toString())%2==1 && p1
}
//then consider boundary condition 2 all belongs to group2
while(Integer.parseInt(str.get(p2).toString())%2==0 && p1
}
if(p1==p2) return str;
//normal condition
else{
changeValue(str,p1,p2);
//for (int m:str) System.out.print(m+"\t");
p1++;
p2--;
while(p1
p1++;
}
else {
changeValue(str,p1,p2);
p2--;
}
}
return str;
}
}
d*0
45 楼
我只能用DA40和FA50.
【在 h*******g 的大作中提到】
: 我主力人像头=。=因为没别的选择了
【在 h*******g 的大作中提到】
: 我主力人像头=。=因为没别的选择了
w*o
46 楼
置换很容易，但时间绝对不是O(n)：
char[] A = {'a', '1','b', '2', 'c', '3', 'd', '4', 'e', '5', 'f', '6', 'g',
'7', 'h', '8', 'i', '9'};
int n = A.length; int mid = n / 2;
for(int i = 1; i < mid; i++)
{
for(int j = mid - i, k = mid; j < mid; j++, k++)
{
char ch = A[j];
A[j] = A[k];
A[k] = ch;
}
}
下面这个是一次置换到位，时间是O(n)，但空间不是O（1）:
int n = A.length; int mid = n / 2;
boolean[] visited = new boolean[mid - 1];
for (int k = visited.length - 1; k >= 0; k--)
{
if (visited[k]) continue;
int i = 2 * k + 1;
int rem = i;
char pre = A[i];
do {
if (i % 2 == 1)
{
visited[i / 2] = true;
i = mid + i / 2;
} else {
i = i / 2;
}
char ch = A[i];
A[i] = pre;
pre = ch;
} while (i != rem);
}
char[] A = {'a', '1','b', '2', 'c', '3', 'd', '4', 'e', '5', 'f', '6', 'g',
'7', 'h', '8', 'i', '9'};
int n = A.length; int mid = n / 2;
for(int i = 1; i < mid; i++)
{
for(int j = mid - i, k = mid; j < mid; j++, k++)
{
char ch = A[j];
A[j] = A[k];
A[k] = ch;
}
}
下面这个是一次置换到位，时间是O(n)，但空间不是O（1）:
int n = A.length; int mid = n / 2;
boolean[] visited = new boolean[mid - 1];
for (int k = visited.length - 1; k >= 0; k--)
{
if (visited[k]) continue;
int i = 2 * k + 1;
int rem = i;
char pre = A[i];
do {
if (i % 2 == 1)
{
visited[i / 2] = true;
i = mid + i / 2;
} else {
i = i / 2;
}
char ch = A[i];
A[i] = pre;
pre = ch;
} while (i != rem);
}
s*s
47 楼
解释下什么叫“眼角膜”先。
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
【在 h*******g 的大作中提到】
: 眼角膜算长好了吗？跳闪的话，有影响吗？
i*7
48 楼
我是这么理解o(1)这个概念的。
o(1)不代表不用buffer，只是这个buffer的量是常数级别不和输入输出挂钩的。
那么开counting数组，一个26长度的数组去数英文字符，一个10长度的数组去数0~9
这个buffer是属于固定常数级别的，跟输入输出没有关系。
所以space是解读为O(1)
【在 g**e 的大作中提到】
: why is this O(1)?
o(1)不代表不用buffer，只是这个buffer的量是常数级别不和输入输出挂钩的。
那么开counting数组，一个26长度的数组去数英文字符，一个10长度的数组去数0~9
这个buffer是属于固定常数级别的，跟输入输出没有关系。
所以space是解读为O(1)
【在 g**e 的大作中提到】
: why is this O(1)?
S*M
49 楼
可以培养老大的摄影兴趣
这样以后记录老二成长过程的任务就不用你干了
【在 T********r 的大作中提到】
: 上个月老二出生 :)
这样以后记录老二成长过程的任务就不用你干了
【在 T********r 的大作中提到】
: 上个月老二出生 :)
i*7
50 楼
我还记得版里面报过一个a家的题目。
是在圆周率的小数点后面取每连续四个数为一组，然后求第一次出现duplicate的情况。
可用hash_map做。但当时面试者回答算法复杂度为O(n)的时候面试官认为是错的，面试
官认为是O(1)
理由有二。
1. 圆周率是固定的，所以你总会在同样的点找到duplicate。
2. 这个理由更strong一点。四位数的组合分别就是0001~9999。也就是buffer的size固
定应该为9999的上限。所以是为O(1)
当然，我觉得这有些诡辩的意思。
看个人理解吧
【在 g**e 的大作中提到】
: why is this O(1)?
是在圆周率的小数点后面取每连续四个数为一组，然后求第一次出现duplicate的情况。
可用hash_map做。但当时面试者回答算法复杂度为O(n)的时候面试官认为是错的，面试
官认为是O(1)
理由有二。
1. 圆周率是固定的，所以你总会在同样的点找到duplicate。
2. 这个理由更strong一点。四位数的组合分别就是0001~9999。也就是buffer的size固
定应该为9999的上限。所以是为O(1)
当然，我觉得这有些诡辩的意思。
看个人理解吧
【在 g**e 的大作中提到】
: why is this O(1)?
h*g
51 楼
我有M50/1.4。。。
我现在考虑也搞个DA70算了。。。
【在 d*****0 的大作中提到】
: 我只能用DA40和FA50.
我现在考虑也搞个DA70算了。。。
【在 d*****0 的大作中提到】
: 我只能用DA40和FA50.
a*s
52 楼
big O的概念要弄清楚，否则很容易出错。
O(n)时间复杂度肯定是可以的，意思是只扫描一遍，参考俺的奇数偶数置换；
O（1）是空间复杂度，意思是只是用常数个额外的空间，跟输入字符串的大小无函数关
系你用10000个都没关系，但是这10000个必须是无论字符串多大，都是这么多。
O(n)时间复杂度肯定是可以的，意思是只扫描一遍，参考俺的奇数偶数置换；
O（1）是空间复杂度，意思是只是用常数个额外的空间，跟输入字符串的大小无函数关
系你用10000个都没关系，但是这10000个必须是无论字符串多大，都是这么多。
d*0
53 楼
DA70我的心理价位是350AR，恐怕很难达到了
【在 h*******g 的大作中提到】
: 我有M50/1.4。。。
: 我现在考虑也搞个DA70算了。。。
【在 h*******g 的大作中提到】
: 我有M50/1.4。。。
: 我现在考虑也搞个DA70算了。。。
N*N
54 楼
同理o(n) 时间扫描一百遍也可以的，只要对任何n都是100遍。。
【在 a*****s 的大作中提到】
: big O的概念要弄清楚，否则很容易出错。
: O(n)时间复杂度肯定是可以的，意思是只扫描一遍，参考俺的奇数偶数置换；
: O（1）是空间复杂度，意思是只是用常数个额外的空间，跟输入字符串的大小无函数关
: 系你用10000个都没关系，但是这10000个必须是无论字符串多大，都是这么多。
【在 a*****s 的大作中提到】
: big O的概念要弄清楚，否则很容易出错。
: O(n)时间复杂度肯定是可以的，意思是只扫描一遍，参考俺的奇数偶数置换；
: O（1）是空间复杂度，意思是只是用常数个额外的空间，跟输入字符串的大小无函数关
: 系你用10000个都没关系，但是这10000个必须是无论字符串多大，都是这么多。
h*g
55 楼
回国就有了，新的400刀，二手的肯定只要350刀
【在 d*****0 的大作中提到】
: DA70我的心理价位是350AR，恐怕很难达到了
【在 d*****0 的大作中提到】
: DA70我的心理价位是350AR，恐怕很难达到了
C*y
56 楼
还是没看懂
Integer.parseInt(str.get(p1).toString())%2==1
你传入的已经是int了，为啥要变成string然后在变成int
为什么要%2？
【在 a*****s 的大作中提到】
: public ArrayList groupSwap(ArrayList str, int i, int j){
: int p1=0;
: int p2=str.size()-1;
: //first consider boundary condition 1 all belongs to group 1
: while(Integer.parseInt(str.get(p1).toString())%2==1 && p1
: }
: //then consider boundary condition 2 all belongs to group2
: while(Integer.parseInt(str.get(p2).toString())%2==0 && p1
Integer.parseInt(str.get(p1).toString())%2==1
你传入的已经是int了，为啥要变成string然后在变成int
为什么要%2？
【在 a*****s 的大作中提到】
: public ArrayList
: int p1=0;
: int p2=str.size()-1;
: //first consider boundary condition 1 all belongs to group 1
: while(Integer.parseInt(str.get(p1).toString())%2==1 && p1
: }
: //then consider boundary condition 2 all belongs to group2
: while(Integer.parseInt(str.get(p2).toString())%2==0 && p1
d*0
57 楼
国内的DA40也是400刀，不知道怎么想的
【在 h*******g 的大作中提到】
: 回国就有了，新的400刀，二手的肯定只要350刀
【在 h*******g 的大作中提到】
: 回国就有了，新的400刀，二手的肯定只要350刀
a*s
58 楼
这个是奇数偶数互换，所有奇数在前，偶数在后。跟那个字母和数字算法不是一样么？
【在 C***y 的大作中提到】
: 还是没看懂
: Integer.parseInt(str.get(p1).toString())%2==1
: 你传入的已经是int了，为啥要变成string然后在变成int
: 为什么要%2？
【在 C***y 的大作中提到】
: 还是没看懂
: Integer.parseInt(str.get(p1).toString())%2==1
: 你传入的已经是int了，为啥要变成string然后在变成int
: 为什么要%2？
h*g
59 楼
我下半年准备把FA43换成DA40
【在 d*****0 的大作中提到】
: 国内的DA40也是400刀，不知道怎么想的
【在 d*****0 的大作中提到】
: 国内的DA40也是400刀，不知道怎么想的
j*9
60 楼
其实并没有这么复杂的。
假设initial array is 1c3a2d4b
首先我们知道字母a，和数字 1 应该在什么位置，换句话说：a 应该在index 0； 1应
该在 index length of array /2, 也就是在index 4
ok， 其他的字母和数字可以通过他们和a, 1 的distance, 找到它们应该在的位置，比
如说字母c应该在（c-a）+ 0 = 2, 数字 3应该在（3－1）＋4 ＝ 6.
ok，接下来就是要考虑到swap的问题了，我们从头开始遍历这个数组，1c3a2d4b
第一个item 是数字1，我们计算它应该在的位置（1－1）＋4 ＝ 4, 所以我们swap
with the item which is in index 4 that is 2, 所以现在变成2c3a1d4b， 我们可以
发现数字1已经到了它应该在的位置，我们在看这个时候的item，现在是数字2,ok，数
字2不属于这个位置，继续计算它应该在的位置（2－1）＋4 ＝ 5, 然后继续swap。一
直swap 到应该属于这个位置的数字或字母的出现。
ok，下一个问题是，我们要做多少次swap呢，最多n次（n ＝ length of the array）
。 因为，我们每做一次swap，至少有一个数字或字母会到它们应该所在的位置。那么
我们最多只要做n次swap，就可以得到我们想要的sequence了。
time complexity : O(n)（遍历整个数组） ＋ O(n)（最多做的swap）＝ O(n)
space complexity: apparently O(1)
假设initial array is 1c3a2d4b
首先我们知道字母a，和数字 1 应该在什么位置，换句话说：a 应该在index 0； 1应
该在 index length of array /2, 也就是在index 4
ok， 其他的字母和数字可以通过他们和a, 1 的distance, 找到它们应该在的位置，比
如说字母c应该在（c-a）+ 0 = 2, 数字 3应该在（3－1）＋4 ＝ 6.
ok，接下来就是要考虑到swap的问题了，我们从头开始遍历这个数组，1c3a2d4b
第一个item 是数字1，我们计算它应该在的位置（1－1）＋4 ＝ 4, 所以我们swap
with the item which is in index 4 that is 2, 所以现在变成2c3a1d4b， 我们可以
发现数字1已经到了它应该在的位置，我们在看这个时候的item，现在是数字2,ok，数
字2不属于这个位置，继续计算它应该在的位置（2－1）＋4 ＝ 5, 然后继续swap。一
直swap 到应该属于这个位置的数字或字母的出现。
ok，下一个问题是，我们要做多少次swap呢，最多n次（n ＝ length of the array）
。 因为，我们每做一次swap，至少有一个数字或字母会到它们应该所在的位置。那么
我们最多只要做n次swap，就可以得到我们想要的sequence了。
time complexity : O(n)（遍历整个数组） ＋ O(n)（最多做的swap）＝ O(n)
space complexity: apparently O(1)
m*x
61 楼
呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
a1b2c3d4的case，也不想想这样的问题还有什么意思？
这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
部分。
二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
*log(n). 这个方法适合写code，一般面试官的思路在这里。
这个问题大概一年前这个板上有过比较详尽的讨论，很多人给出了不错的想法。比较现
在，感觉牛人变少了。呵呵。
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
a1b2c3d4的case，也不想想这样的问题还有什么意思？
这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
部分。
二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
*log(n). 这个方法适合写code，一般面试官的思路在这里。
这个问题大概一年前这个板上有过比较详尽的讨论，很多人给出了不错的想法。比较现
在，感觉牛人变少了。呵呵。
【在 b*******y 的大作中提到】
: 时间Ｏ(ｎ)空间O(1)
: 咋整？
g*e
62 楼
人家要O(n) time O(1) space，我想了半天也没想出来，以为众大牛们不屑回答这类简
单题了
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
单题了
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
C*y
63 楼
如果元素个数不是2^n的话，请问怎么如何用divide and conquer做？
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
vn
64 楼
re O（n） 不过我都不屑了 大牛肯定更不屑 hoho
【在 g**e 的大作中提到】
: 人家要O(n) time O(1) space，我想了半天也没想出来，以为众大牛们不屑回答这类简
: 单题了
:
: 是n
【在 g**e 的大作中提到】
: 人家要O(n) time O(1) space，我想了半天也没想出来，以为众大牛们不屑回答这类简
: 单题了
:
: 是n
Q*e
65 楼
其实出这样的题目恨无聊。
不知能搞出哈来。
欧用的编程题目是
写个程序，返回数组中最小的。
书上有的就免了。不是傻子都能找到。
不知能搞出哈来。
欧用的编程题目是
写个程序，返回数组中最小的。
书上有的就免了。不是傻子都能找到。
m*x
66 楼
呵呵，good question. 不过我前面已经提示了。
一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
这其实是一个两个words的reverse order问题，应该很简单吧？
【在 C***y 的大作中提到】
: 如果元素个数不是2^n的话，请问怎么如何用divide and conquer做？
:
: 是n
一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
这其实是一个两个words的reverse order问题，应该很简单吧？
【在 C***y 的大作中提到】
: 如果元素个数不是2^n的话，请问怎么如何用divide and conquer做？
:
: 是n
m*x
67 楼
题目是否无聊并不重要。现在FLG面试的游戏规则就是做这样的题目，你可以不和他们
玩。要玩就要遵守这样的规则。
【在 Q*******e 的大作中提到】
: 其实出这样的题目恨无聊。
: 不知能搞出哈来。
: 欧用的编程题目是
: 写个程序，返回数组中最小的。
: 书上有的就免了。不是傻子都能找到。
玩。要玩就要遵守这样的规则。
【在 Q*******e 的大作中提到】
: 其实出这样的题目恨无聊。
: 不知能搞出哈来。
: 欧用的编程题目是
: 写个程序，返回数组中最小的。
: 书上有的就免了。不是傻子都能找到。
w*o
68 楼
完全同意mmx所说的。
如果只是把数字和字母分开，然后不按原顺序，而按大小顺序的话排列的话，那跟原字
符串有什么关系，完全可以撇开原串，自己构造就可以了。
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
如果只是把数字和字母分开，然后不按原顺序，而按大小顺序的话排列的话，那跟原字
符串有什么关系，完全可以撇开原串，自己构造就可以了。
是n
【在 m*x 的大作中提到】
: 呵呵，看了半天，没看到make sense的答案。有人还老想着把这个问题trivialize成
: a1b2c3d4的case，也不想想这样的问题还有什么意思？
: 这个题general的描述是：对一个偶数长度的数组，找到一个算法，把偶数位的元素移
: 到后半部分，奇数位的元素在前半部分。奇数位和偶数位各自内部相对次序保持不变。
: 基本思路有两种解法，一是通过permutation的思路找到变换的方法。这个有general解
: 法，针对所有的变换。对这个具体的问题，没有简易的方法。而且算法的核心在数学的
: 部分。
: 二是divide and conquer，前半后半各自分治之后，需要一个O(n)的操作对两部分子数
: 组做位置对调。这个调换的trick是类比字符串改变词的顺序。所以整体时间复杂度是n
: *log(n). 这个方法适合写code，一般面试官的思路在这里。
w*o
69 楼
还是不明白大牛所说的，我只能做到O(n^2)+O(1),或者O（n)+O(n)；我用了
Programming Pearls里的思想，但不能找到一个好的方法找到下一个起点，
麻烦大牛看看我前面的帖子，提点意见。
【在 m*x 的大作中提到】
: 呵呵，good question. 不过我前面已经提示了。
: 一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
: 价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
: 这其实是一个两个words的reverse order问题，应该很简单吧？
Programming Pearls里的思想，但不能找到一个好的方法找到下一个起点，
麻烦大牛看看我前面的帖子，提点意见。
【在 m*x 的大作中提到】
: 呵呵，good question. 不过我前面已经提示了。
: 一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
: 价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
: 这其实是一个两个words的reverse order问题，应该很简单吧？
w*x
70 楼
这题太难了,过吧
a*a
71 楼
这个程序可以满足要求，
前提是字符和数字交替出现，不排序（除非连续的字符数字）
不过有点缺陷。绝大多case能通过
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
const int SIZE=14;
int from,to=0;
char c1,c2;
char str[SIZE] = {'a','1','b','2','c','3','d','4','e','5','f','6','g','
7'};
for(int i=1;i
if(to==0){
if(i % 2 ==1 || to==1)
{
from =i;
to=(i-1+SIZE)/2;
c1=str[to];
str[to]=str[i];
//inter=from;
c2=c1;
}
}
else
{
from =to;
if(from%2==1)
{
to=(from-1+SIZE)/2;
}
else
{
to=from/2;
}
c1=str[to];
str[to]=c2;
c2=c1;
//if (to==1) break;
}
}
return 0;
}
前提是字符和数字交替出现，不排序（除非连续的字符数字）
不过有点缺陷。绝大多case能通过
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
const int SIZE=14;
int from,to=0;
char c1,c2;
char str[SIZE] = {'a','1','b','2','c','3','d','4','e','5','f','6','g','
7'};
for(int i=1;i
if(to==0){
if(i % 2 ==1 || to==1)
{
from =i;
to=(i-1+SIZE)/2;
c1=str[to];
str[to]=str[i];
//inter=from;
c2=c1;
}
}
else
{
from =to;
if(from%2==1)
{
to=(from-1+SIZE)/2;
}
else
{
to=from/2;
}
c1=str[to];
str[to]=c2;
c2=c1;
//if (to==1) break;
}
}
return 0;
}
f*4
72 楼
a1b1a2b2a3b3按位划分成长度为2^i的子串4+2
子串内部重排(a1a2b1b2)(a3b3)后, 再对先后串的后前半部分原地换序.
依次换序每次都能搞定一半的位置, 复杂度O(n),O(1)
【在 C***y 的大作中提到】
: 如果元素个数不是2^n的话，请问怎么如何用divide and conquer做？
:
: 是n
子串内部重排(a1a2b1b2)(a3b3)后, 再对先后串的后前半部分原地换序.
依次换序每次都能搞定一半的位置, 复杂度O(n),O(1)
【在 C***y 的大作中提到】
: 如果元素个数不是2^n的话，请问怎么如何用divide and conquer做？
:
: 是n
a*m
73 楼
肯定都是字符么？那用对照表int count[36]计数就行了。最后扫一遍对照标。
a*m
74 楼
他弄错了，如果这个是o(1)那么扫描数组找到第一个指定数字也就可以o(1)了。除非他
想cache结果。理由2只能说计算是否有重复是o(1)。
况。
【在 i*********7 的大作中提到】
: 我还记得版里面报过一个a家的题目。
: 是在圆周率的小数点后面取每连续四个数为一组，然后求第一次出现duplicate的情况。
: 可用hash_map做。但当时面试者回答算法复杂度为O(n)的时候面试官认为是错的，面试
: 官认为是O(1)
: 理由有二。
: 1. 圆周率是固定的，所以你总会在同样的点找到duplicate。
: 2. 这个理由更strong一点。四位数的组合分别就是0001~9999。也就是buffer的size固
: 定应该为9999的上限。所以是为O(1)
: 当然，我觉得这有些诡辩的意思。
: 看个人理解吧
想cache结果。理由2只能说计算是否有重复是o(1)。
况。
【在 i*********7 的大作中提到】
: 我还记得版里面报过一个a家的题目。
: 是在圆周率的小数点后面取每连续四个数为一组，然后求第一次出现duplicate的情况。
: 可用hash_map做。但当时面试者回答算法复杂度为O(n)的时候面试官认为是错的，面试
: 官认为是O(1)
: 理由有二。
: 1. 圆周率是固定的，所以你总会在同样的点找到duplicate。
: 2. 这个理由更strong一点。四位数的组合分别就是0001~9999。也就是buffer的size固
: 定应该为9999的上限。所以是为O(1)
: 当然，我觉得这有些诡辩的意思。
: 看个人理解吧
b*y
75 楼
...还是没懂。。。
【在 m*x 的大作中提到】
: 呵呵，good question. 不过我前面已经提示了。
: 一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
: 价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
: 这其实是一个两个words的reverse order问题，应该很简单吧？
【在 m*x 的大作中提到】
: 呵呵，good question. 不过我前面已经提示了。
: 一个例子是如何把a1a2b1b2a3a4a5b3b4b5 convert 成 a1a2a3a4a5b1b2b3b4b5. 其实等
: 价于把b1b2a3a4a5转变为a3a4a5b1b2. O(n)time O(1)space.
: 这其实是一个两个words的reverse order问题，应该很简单吧？
相关阅读