logo
Redian新闻
>未名空间
>Hardware - 计算机硬件
>
台式机的USB 3.1 (gen 2) Type C 相对 Type A 接口有什么用？
avatar
台式机的USB 3.1 (gen 2) Type C 相对 Type A 接口有什么用？# Hardware - 计算机硬件
B*1
1 楼
Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
write an algorithm to rearrange the charecters so that the string will
become as
c1 c2 c3 c4 c5 ......c2n
Max complexity of algo should be O(n)
Do it without using extra storage
这题可以O(n)吗？
avatar
z*n
2 楼
的确非常强大，我整个文章都是用一次输入完成，一个修改都没有
这也太牛了吧 。
avatar
c*7
3 楼
oy
avatar
d*a
4 楼
笔记本据说可以做充电口
台式机？
avatar
g*i
5 楼
in place mergesort,应该不可以
avatar
g*n
6 楼
关于兔子育种的新论文？

【在 z*********n 的大作中提到】
: 的确非常强大，我整个文章都是用一次输入完成，一个修改都没有
: 这也太牛了吧 。
avatar
a*g
7 楼
有几个是common sense
比如最后一个
第六个是商品化的东西，有专门让人绑dvd的
最impressive的是第一个
avatar
z*e
8 楼
还可以带tb3
avatar
c*t
9 楼
你在本版看帖不认真。呵呵！
相见
http://www.mitbbs.com/article_t/JobHunting/31935043.html
中 dinohound 的回答。

c2n

【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
avatar
v*f
10 楼
哪个文章？

【在 z*********n 的大作中提到】
: 的确非常强大，我整个文章都是用一次输入完成，一个修改都没有
: 这也太牛了吧 。
avatar
N*f
11 楼
orz

【在 c*******7 的大作中提到】
: oy
avatar
f*t
12 楼
前面还有别的帖讨论过，in-place+O(n)不可能
上面提到的dinohound的答案用的是divide-and-conquer，时间复杂度是O(nlogn)
avatar
z*n
13 楼
随便胡乱灌水很多篇文章，从头到尾就输入拼音， 搜狗输入法给我短剧完全正确，正
确率100%.迄今为止见过最牛的输入法了

【在 v******f 的大作中提到】
: 哪个文章？
avatar
o*1
14 楼
伤不起，这动手能力不是一般的强。尤其是那个啤酒瓶接车轮的，不仅是动手能力强了
，这得艺高人胆大，粉身亦不怕，玻璃为钢铁，酒干成路霸。

【在 c*******7 的大作中提到】
: oy
avatar
B*1
15 楼
thanks all.
avatar
w*a
16 楼
发一下欣赏一下
avatar
K*a
17 楼
牛

【在 c*******7 的大作中提到】
: oy
avatar
d*y
18 楼
it can be done o(n) time and in place.
for each element you can calculate
the right index where you should swap the value.
there was similar question
from ITA. will post code later.

c2n

【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
avatar
z*n
19 楼
哈哈
发现这篇里有个错误
短句不是短句晕倒 还不知道咋修改

【在 z*********n 的大作中提到】
: 随便胡乱灌水很多篇文章，从头到尾就输入拼音， 搜狗输入法给我短剧完全正确，正
: 确率100%.迄今为止见过最牛的输入法了
avatar
j*e
20 楼
第三个啥意思
avatar
g*y
21 楼
我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
这个code比较ugly, 用计算loop head的办法来判断是否调整：
public String shuffle(String original) {
int N = original.length();
char[] c = original.toCharArray();
for (int i=0; iif (isLoopHead(i, N)) {
int j = i;
int k = position(j, N);
while (k != i) {
char t = c[i];
c[i] = c[k];
c[k] = t;
j = k;
k = position(j, N);
}
}
}
return new String(c);
}
private int position(int i, int N) {
return i}
private boolean isLoopHead(int i, int N) {
int j = position(i, N);
while (j != i) {
if (j < i) return false;
j = position(j, N);
}
return true;
}

for each element you can calculate
there was similar question

【在 d********y 的大作中提到】
: it can be done o(n) time and in place.
: for each element you can calculate
: the right index where you should swap the value.
: there was similar question
: from ITA. will post code later.
:
: c2n
avatar
z*n
22 楼
现在这几篇都是搜狗输入法输入的

【在 w******a 的大作中提到】
: 发一下欣赏一下
avatar
s*i
23 楼
aluminum can, just for decoration

【在 o******1 的大作中提到】
: 伤不起，这动手能力不是一般的强。尤其是那个啤酒瓶接车轮的，不仅是动手能力强了
: ，这得艺高人胆大，粉身亦不怕，玻璃为钢铁，酒干成路霸。
avatar
x*s
24 楼
就这个问题而言，貌似可以证明只有一个loop吧。能给个两个loop的例子？

in-

【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
avatar
S*T
25 楼
it已经读过你的mind了

【在 z*********n 的大作中提到】
: 随便胡乱灌水很多篇文章，从头到尾就输入拼音， 搜狗输入法给我短剧完全正确，正
: 确率100%.迄今为止见过最牛的输入法了
avatar
G*Y
26 楼
靠

【在 c*******7 的大作中提到】
: oy
avatar
g*y
27 楼
N = 8时，就是两个loop

【在 x******s 的大作中提到】
: 就这个问题而言，貌似可以证明只有一个loop吧。能给个两个loop的例子？
:
: in-
avatar
i*o
28 楼
唐诗宋词元曲也能才算牛。嗯。
avatar
i*s
29 楼
强！
avatar
x*s
30 楼
嗯，我之前搞错了一个index.

【在 g**********y 的大作中提到】
: N = 8时，就是两个loop
avatar
a*o
31 楼
good one

【在 c*******7 的大作中提到】
: oy
avatar
d*y
32 楼
测试了1-20的整数。
class Mix2Array
{
int[] arr;
public bool mix2Array()
{
if (arr == null || arr.Length % 2 != 0)
{
Console.WriteLine("invalid input!");
return false;
}
for (int i = 1; i < arr.Length - 2; i++)
{
int targetIndex = target(i, arr.Length);
while (targetIndex < i)
{
targetIndex = target(targetIndex, arr.Length);
}
if (i != targetIndex)
{
swap(i, targetIndex);
}
printArray();
}
return true;
}
private void swap(int i, int targetIndex)
{
arr[i] ^= arr[targetIndex];
arr[targetIndex] ^= arr[i];
arr[i] ^= arr[targetIndex];
}
private int target(int i, int length)
{
if (i % 2 == 1)
{
return length / 2 + i / 2;
}
else
{
return i / 2;
}
}
}

办法来记住调整过的。

【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
avatar
s*l
33 楼
第九个为什么要打马赛克？
avatar
s*c
34 楼
in-place matrix transposition
http://en.wikipedia.org/wiki/In-place_matrix_transposition

c2n

【在 B*******1 的大作中提到】
: Given a string having 2n charecters as c1 c3 c5 c7...c2n-1 c2 c4 c6 .....c2n
: write an algorithm to rearrange the charecters so that the string will
: become as
: c1 c2 c3 c4 c5 ......c2n
: Max complexity of algo should be O(n)
: Do it without using extra storage
: 这题可以O(n)吗？
avatar
k*n
35 楼
可以用没错，就是难看
avatar
s*x
36 楼
This can be done in O(n).
I had posted a correct answer about two years ago.
avatar
c*h
37 楼
dvd player主意不错
avatar
s*x
38 楼
My original post seems to have been deleted.
You can find it by google "shyx shuffle"
avatar
e*s
39 楼
i have one of the last kind
avatar
g*y
40 楼
这个work, 思路很赞。

【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
avatar
k*u
41 楼
悲剧。。
avatar
s*x
42 楼
not really. try 1 - 100. there will be failures.

【在 g**********y 的大作中提到】
: 这个work, 思路很赞。
avatar
B*1
43 楼
本版高人好多啊，careercup那里都是一堆臭老印的烂code，都不如牛人们的短短几行
啊。
avatar
g*y
44 楼
Are you sure? 我算了N = 2 to 10000，都是对的。从数学上说，我大致可以理解，但
是没想到简单明了的证明。

【在 s**x 的大作中提到】
: not really. try 1 - 100. there will be failures.
avatar
s*x
45 楼
Sorry I mis-read the code.
The code from doubleplay is correct.
However, it is not O(n) time. If you don't believe me, try measure it.
avatar
g*y
46 楼
I know, if you count that index calculation as operation, then it's not O(n)
. But I guess in interview, that is not counted. Only swap is counted.
I read your code, it's correct, but too difficult for interview :-)

【在 s**x 的大作中提到】
: Sorry I mis-read the code.
: The code from doubleplay is correct.
: However, it is not O(n) time. If you don't believe me, try measure it.
avatar
u*r
47 楼
我从中间开始交换，假设输入数组存储为a[1...n,n+1...2n]
从a[n],a[n+1]开始，每次把a[n]和a[n+1]交换到正确位置去，直到a[n]=n,a[n+1]=n+1
为止，然后处理a[n-1],a[n+2]，知道最外头，这样每次交换保证两个数位于正确位置
，所以最多交换次数就是n.
大家看看有没有问题？
void main()
{
int n = 20,k,t,tt;
int* c = new int [2*n];
for (int i=0;i<2*n;i++)
{
c[i] = l(i+1,n);
cout<}
cout<int idx1 = n, idx2=n+1;
for(idx2=n+1;idx2<=2*n;idx2++,idx1--)
{
while (c[idx2-1] != idx2)
{
t = c[idx2-1];
c[idx2-1] = c[t-1];
c[t-1] = t;
t = c[idx1-1];
c[idx1-1] = c[t-1];
c[t-1] = t;
}
}
for (int i=0;i<2*n;i++)
{
cout<}
cout<return;
}
avatar
r*g
48 楼
看不明白，for里面的while存在，怎么还是O(n)的?

【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
avatar
u*r
49 楼
他只计算swap操作，其他的没算。

【在 r*******g 的大作中提到】
: 看不明白，for里面的while存在，怎么还是O(n)的?
avatar
m*q
51 楼
这个貌似不是O(n)啊
只有在原数组中的数字是有规律的时候，才能保证O(n).
例如原数组为 abcde12345 需要变成a1b2c3d4e5
这时候可以简单的判断数组中的元素是否已经被换到了
它的最终位置。如果没有这个前提的话是这个方法无法保证O(n).

【在 d********y 的大作中提到】
: 测试了1-20的整数。
: class Mix2Array
: {
: int[] arr;
: public bool mix2Array()
: {
: if (arr == null || arr.Length % 2 != 0)
: {
: Console.WriteLine("invalid input!");
: return false;
avatar
c*m
52 楼
double play 的算法真的很妙，可以试用几种不同的SHUFFLE, 只需要换那个TARGET
函数即可。我依葫芦画瓢写了两个:
original array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
after odd-even shuffle:
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20
after in-shuffle:
1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20
这个算法看起来有2个LOOP, 但里面那个LOOP 很少RUN， 应该可以证明里面的LOOP 总
数有个UPPER BOUND, 总的时间复杂度很有可能就是O(N)。
public class InShuffle {
public static int target_idx(int idx,int length)
{
int next;
next=2*idx;
if(next>length-1)
next=next-length+1;
return next;
}
public static int target_idx_inshuffle(int idx, int length){
int next;
if(idx%2==1){
next=length/2+idx/2;
}
else
next=idx/2;
return next;
}
public static int [] inshuffle(int [] a){
for(int i=1;iint next=target_idx_inshuffle(i,a.length);
while(nextnext=target_idx_inshuffle(next,a.length);
}
int temp=a[i];
a[i]=a[next];
a[next]=temp;
}

return a;
}
public static int [] shuffle(int [] a){
for(int i=1;iint next=target_idx(i,a.length);
while(nextnext=target_idx(next,a.length);
}
int temp=a[i];
a[i]=a[next];
a[next]=temp;
}

return a;
}
public static void main(String [] args){
int [] a=new int [20];
int [] b;
for(int i=0;i<20;i++){
a[i]=i+1;
}
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(a[i]);
}
System.out.println("\n after odd-even shuffle");
b=shuffle(a.clone());
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(b[i]);
}

System.out.println("\n after in-shuffle");
b=inshuffle(a.clone());
for(int i=0;i<20;i++){
System.out.print(" ");
System.out.print(b[i]);
}
}
}
avatar
c*m
53 楼
买卖题的验证码发疯了，老是输不对。
avatar
g*s
54 楼
int [] rearrange(int [] k) {
if (k == null || k.length < 3)
return k;
int [] n = new int[size_t];
for (int i = 0; i < k.length; i++) {
if (i%2 == 1) {
n[i] = k[i/2];
}
else {
n[i] = k[k.length / 2 + i/2];
}
}
return n;
}
avatar
c*t
55 楼
gloomyturkey,
谢谢你的代码。
我运行了你的代码，非常正确。可是我不太理解它是如何工作的。
我debug了N=12的case,
我发现真正做几乎所有工作的是当index=1的时候，在那个while() 里通过 i, k, swap
值来完成的。对于别的index, isLoopHead 都是false. 当index=0, 和index=11的时候
isLoopHead 返回真，但是不用调整。
你能不能通俗易懂的说说你的logic?
isLoopHead()到底是想做什么？为什么isLoopHead（）本身还有一个while()?它的物理
含义是什么？
你所谓的"loop"到底是代表什么？ loop head指的又是什么？
position()好理解，是得到应该的位置。

办法来记住调整过的。

【在 g**********y 的大作中提到】
: 我想看看你的code, 计算index不难，但是index loop有多个时，我没想到什么好的办法来记住调整过的。
: 这个code比较ugly, 用计算loop head的办法来判断是否调整：
: public String shuffle(String original) {
: int N = original.length();
: char[] c = original.toCharArray();
: for (int i=0; i: if (isLoopHead(i, N)) {
: int j = i;
: int k = position(j, N);
: while (k != i) {
avatar
g*y
56 楼
你看doubleplay的code吧，更有效率。我的code处理方式是：对一个loop, 依次交换，
但是这个交换只在loopHead的位置进行，也就是index最小的地方。
doubleplay的code是：反向交换，每次把正确值调整到位置i。正确值位置大于i, 直接
调整；小于i, 说明该值已经被挪到下一个位置，循环找，找到后(也就是pos > i)时，
调整。
shyx有更进一步的解释和code, 见：http://fayaa.com/code/view/612/

swap

【在 c*********t 的大作中提到】
: gloomyturkey,
: 谢谢你的代码。
: 我运行了你的代码，非常正确。可是我不太理解它是如何工作的。
: 我debug了N=12的case,
: 我发现真正做几乎所有工作的是当index=1的时候，在那个while() 里通过 i, k, swap
: 值来完成的。对于别的index, isLoopHead 都是false. 当index=0, 和index=11的时候
: isLoopHead 返回真，但是不用调整。
: 你能不能通俗易懂的说说你的logic?
: isLoopHead()到底是想做什么？为什么isLoopHead（）本身还有一个while()?它的物理
: 含义是什么？
avatar
w*x
57 楼
int ClacTarget(int nLen, int nIndex)
{
assert(nLen > 0 && nIndex > 0 && nLen > nIndex);
if (nIndex < nLen/2)
return 2 * nIndex;
return (nIndex - nLen/2) * 2 + 1;
}
char* InplaceConvert(char* str)
{
if (NULL == str)
return NULL;
int nLen = strlen(str);
if (0 == nLen || nLen%2 != 0)
return str;
int nCount = nLen - 2;
for (int i = 1; i < nLen && nCount > 0; i += 2)
{
int nCur = ClacTarget(nLen, i);
char cTmp = str[nCur];
str[nCur] = str[i];
nCount--;
while (nCur != i)
{
nCur = ClacTarget(nLen, nCur);
char c = str[nCur];
str[nCur] = cTmp;
cTmp = c;
nCount--;
}
}

return str;
}
avatar
H*X
58 楼
也写了一下, a是数组指针, n 是数组大小,
没有计算index, 直接就是从左到右扫描, 如果a[i]的数值不对就一直swap,一直到a[i]
=i+1.
计算了一下, 如果array length是100000的话, while()循环里面的指令被执行了99796
次,对比了一下之前doubleplay的算法, 他的swap()也是执行了99796次, 不过他的
while()循环里面被执行了552860次.
void re_order(int* a, int n)
{
int i,j,k;
for (i = 1; iwhile (a[i] != i+1) {
k = a[i];
j = a[k -1];
a[k-1] = k;
a[i] = j;
}
}
}
avatar
r*g
59 楼
我比较了你和doubleplay的算法，然后自己用二分法写了个，二分法的效率是O(nlogn)
我现在还没看懂doubleplay的算法，你的算法更容易理解，每次判断是否是loop的开头
，doubleplay那个至今理解不了。
但是我发觉你们的结果都没有二分法快啊，我用的N=10000000，你能不能测试下，不知
道结果是不是和我类似，难道是c++的问题？
感觉你们这个也不是O(N)，shyx那个是O(N)，但是很难想到什么基于素数的算法。
void Swap(int * array,int begin,int end){
for (int i=0;iint tmp=array[begin+i];
array[begin+i]=array[end-i];
array[end-i]=tmp;
}
}
void Convert(int * array,int begin,int total){
int N=total/2;
if(N==1)
return;
if(N==2){
Swap(array,begin+1,begin+2);
return;
}
int middle=N/2;
//a b -> b a. a: begin+middle to begin+N-1, b: begin+N to begin+N+
middle-1
Swap(array, begin+middle,begin+N-1);
Swap(array, begin+N,begin+N+middle-1);
Swap(array, begin+middle, begin+N+middle-1);

Convert(array, begin, (middle)*2);
Convert(array, begin+(middle)*2, (N-middle)*2);
}

【在 g**********y 的大作中提到】
: 你看doubleplay的code吧，更有效率。我的code处理方式是：对一个loop, 依次交换，
: 但是这个交换只在loopHead的位置进行，也就是index最小的地方。
: doubleplay的code是：反向交换，每次把正确值调整到位置i。正确值位置大于i, 直接
: 调整；小于i, 说明该值已经被挪到下一个位置，循环找，找到后(也就是pos > i)时，
: 调整。
: shyx有更进一步的解释和code, 见：http://fayaa.com/code/view/612/
:
: swap
avatar
C*l
60 楼
大家都是数学王啊，都用这么专业的字眼。
你那个extra storage是指连几个数字或几个pointer都不给用还是可以用几个呢？如果
准用3个格子 O(n) 很简单。我不懂多少，就insertion。O(n) time O(1) storage
overhead。
avatar
C*l
61 楼
怎么说都好了，阁下是好人。
http://fayaa.com/code/view/612/raw/

【在 s**x 的大作中提到】
: Sorry I mis-read the code.
: The code from doubleplay is correct.
: However, it is not O(n) time. If you don't believe me, try measure it.
相关阅读
太不稳定:PBO没有HDMI输出了...求助配置建议 SSD 组 raid 0, 写入600MB/s这个HP笔记本怎么样有人在T420s光驱位装SSD并做SSDx2 RAID吗？问下一般的内存X201都支持么？comcast 的新router大家都怎么整的?本本升级的几个小白问题请问在美国如何自己装机？学校内网ip可以搭建vpn么？哪位兄弟能传一个PBO的那个rtmp的修改包啊？win8 的界面出来了 (转载)M-Audio Studiophile AV 40 vs. Hivi 惠威 M100 2.0刚定了asus u31JG-A1 @BH, $678atom 230的itx cpu mobo combo还能卖多少钱？小本本无VGA外接口，屏幕坏了，怎么不拆硬盘，导出数据t61p 刷 win7 求功略。涉内蒙六四敏感内容 搜狐全网被中共封杀什么软件可以合理的清理硬盘啊？人生完美了HTC Inspire对比MOTO Atrix和Samsung Infuse，哪个牛？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。