也来一道编程练习题

wqsong

写一个函数，实现整形数组循环右移位，要求空间复杂度不超过O(N)。
例如：
1 2 3 4 5右移两位变为4 5 1 2 3
题本身没难度，看怎么写了。
这是华为2010招聘，在哈尔滨的一道笔试题。

wqsong

1. void Ror(int arr[], int N, int n)
   
2. {
   
3.         int *pTemp;
   
4.         int dim = n%N;
   
5.         if(0 == dim)
   
6.                 return;
   
7.         pTemp = (int *)malloc(sizeof(int)*dim);
   
8.         if(!pTemp)
   
9.                 return;
   
10.         memcpy(pTemp, arr+N-dim, sizeof(int)*dim);
    
11.         memmove(arr+dim, arr, sizeof(int)*(N-dim));
    
12.         memcpy(arr, pTemp, sizeof(int)*dim);
    
13.         free(pTemp);
    
14. }

复制代码

自己顶一下，去华为打酱油时候我的答案。

Rainyboy

老老实实写一下，也许是这样的……总觉得落到出题人的陷进里面了……不过应该是O(N)吧……

1. 
   
2. //Arr[0~Length] Avaliable
   
3. void Ror(int Arr[],int Length,int n)
   
4. {
   
5.    n = n%Length;
   
6.    int* tArr = (int*)malloc(sizeof(int)*Length);
   
7.    if(!tArr||!n)
   
8.        return;
   
9.    for(int i=0;i<Length;++i)
   
10.        tArr[(i+n)%Length] = Arr[i];
    
11.    for(int i=0;i<Length;++i)
    
12.        Arr[i] = tArr[i];
    
13.    return;
    
14. }

复制代码

.

Rainyboy

为什么在跟你聊了“一行代码实现输出”的那个帖子之后，我现在写程序都会想把它们怎么写在一行里……

smtmobly

怎么一个右移写的那么复杂。呵呵。c看不懂！
def  f(x,n):
     x=x[:n-1]+x[n:]
     return x
右移动n位。呵呵！超级业余

smtmobly

上面那个写反了！
def  f(x,n):
    x=x[len(x)-n:]+x[:len(x)-n]
    return x
x=[1,2,3,4,5,6,7]
print f(x,2)
就是将尾部的n位复制到前面啊！呵呵！
上面程序结果是
[6, 7, 1, 2, 3, 4, 5]

Rainyboy

回复 smtmobly 的帖子

果然很强大……

smtmobly

呵呵，你开玩笑了！关键我不知道这个题目出的是什么意思

Rainyboy

回复 smtmobly 的帖子

我也不是很明白出题人的意图……坐等wqsong透露真相……

wqsong

回复 Rainyboy 的帖子

其实我也不知道他们的目的，最主要是看思路吧。。。
当时做题的时候我就想华为偏向于硬件操作，就故意用内存直接拷贝。。。一面的时候那面试官还说我那写法操作内存太赤裸了。。。:lol

smtmobly

回复 wqsong 的帖子

内存的问题不是我考虑的！呵呵
看来写个软件都不容易啊！

wqsong

回复 smtmobly 的帖子

。。。嗯，C/C++考虑内存调试维护都费事，太容易内存泄漏了。
有人说在C/C++编写和调试是平行的。。。
;@P

Rainyboy

好吧，我修正……

1. 
   
2. //Arr[0~Length] Avaliable
   
3. void Ror(int Arr[],int Length,int n)
   
4. {
   
5.    n = n%Length;
   
6.    int* tArr = (int*)malloc(sizeof(int)*Length);
   
7.    if(!tArr||!n)
   
8.        return;
   
9.    for(int i=0;i<Length;++i)
   
10.        tArr[(i+n)%Length] = Arr;
    
11.    for(int i=0;i<Length;++i)
    
12.        Arr = tArr;
    
13.    free(tArr);
    
14.    return;
    
15. }

复制代码