.Net笔试题目精选(1)

显示全部楼层 · 2013-10-8 11:56:03

1: 请写一个函数实现整型数组的按位向右循环移位，比如：
1，2，3，4，5 要求向右循环移两位，结果要求是: 4，5，1，2，3 。
要求算法复杂度不大于O(n)，空间复杂度尽量小。

答：

代码1 1
public
static
void LoopRight(int[] ia,int it)
2       {
3
//移动位数不能是负数
4

if (it <
0)
5          {
6             Console.WriteLine("Invalid param!");
7
return;
8          }
9
//移的位数大于数组长度的话，其实就循环了，只需要移取余次即可
10

if (it > ia.Length)
11          {
12             it %= ia.Length;
13          }
14
int[] temp=new
int[ia.Length];
15
16
int i;
17
//先把后面一部分移到临时数组的前面
18

for ( i =
0; i < it; i++)
19          {
20             temp= ia[ia.Length - it + i];
21          }
22
23
//把前一部分补到临时数组的后面
24

for ( int j=0; j < ia.Length-it; i++,j++)
25          {
26             temp= ia[j];
27          }
28
//将结果复制到返回数组中
29

for (int j =
0; j < ia.Length; j++)
30          {
31             ia[j] = temp[j];
32          }
33       }

这是我今天现场想到的解法，但面试官一看，说时间复杂度是满足了，但是空间复杂度太大，问我有没什么想法，我想了下，当时头脑比较乱，也没想出好办法来。下来查了一下网上的实现，如这个所讲，最后这种解法应该比较高效：
数组循环移位
"假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：
1. 逆序排列abcd：abcd1234 → dcba1234；
2. 逆序排列1234：dcba1234 → dcba4321；
3. 全部逆序：dcba4321 → 1234abcd。
版本3
Reverse(char
*arr, int b, int e)
{
for(; b < e; b++, e--)
{
      char temp = arr[e];
      arr[e] = arr;
      arr = temp;
}
}
RightShift(
char
*arr, int N, int k)
{
k %= N;
Reverse(arr, 0, N-k-1);
Reverse(arr, N-k, N-1);
Reverse(arr, 0, N-1);
}

这样，我们就可以在线性时间内实现右移操作了。"

恩，上面这个解法的思路确实巧妙，只用了两个临时变量，但在笔试现场我觉得还是不容易想到呀。

2013-10-8 17:22:14

asasdasd