.Net笔试题目精选(1)
1: 请写一个函数实现整型数组的按位向右循环移位，比如：
1，2，3，4，5 要求向右循环移两位， 结果要求是: 4，5，1，2，3 。
要求算法复杂度不大于O(n)，空间复杂度尽量小。
答：
http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gifhttp://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif代码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;
15
16
int i;
17
//先把后面一部分移到临时数组的前面
18
for ( i =
0; i < it; i++)
19 {
20 temp= ia- it + i];
21 }
22
23
//把前一部分补到临时数组的后面
24
for ( int j=0; j < ia.Length-it; i++,j++)
25 {
26 temp= ia;
27 }
28
//将结果复制到返回数组中
29
for (int j =
0; j < ia.Length; j++)
30 {
31 ia = temp;
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;
arr = 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);
}
这样，我们就可以在线性时间内实现右移操作了。"
恩，上面这个解法的思路确实巧妙，只用了两个临时变量，但在笔试现场我觉得还是不容易想到呀。
asasdasd
页:
[1]