今天微软面试的一道算法题。求各位帮忙解决。！
给定方法签名：
- C/C++ code
MoveSubArrayToTheEnd(int[] array, int numberOfElements)
传入一个数组如 {1,2,3,4,5,6,7}
将数组前面 head的一个子集移到数组末尾end
如input numberOfElements=3，则{1,2,3,4,5,6,7}=>{4,5,6,7,1,2,3}
input numberOfElements=5，则{1,2,3,4,5,6,7}=>{6,7,1,2,3,4,5}
如何写出该算法？
我没完整正确的写出来。请不要使用FCL提供的类库函数。。
[解决办法]
=7的时候是如何？
[解决办法]
如果可以的话，直接另外定义一个数组，这个构造就不用说了吧，太简单了
如果是只有一个数组，采用移动的方式，那就直接
定义n=numberOfElements-1,maxindex=array.length-1;
array[n]---array[maxindex]交换
n--;maxindex--;
重复以上步骤直到n到0
[解决办法]
- C# code
public int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements) { int[] temp_arr = new int[numberOfElements]; for (int i = 0; i < numberOfElements; i++) { temp_arr[i] = array[i]; } return array.Except(temp_arr).Union(temp_arr).ToArray(); }
[解决办法]
前面要出一点小问题，之前判断以下n是否》numberOfElements/2,大于用上方法
如果小于，那就倒过来看待，是一样的，逻辑反正就是这样的了
[解决办法]
[解决办法]
应当用1个变量就可以实现。
[解决办法]
string a = "a,b,c,d";
string b = "1,2,3,4";
string[] arr1 = a.Split(','); //将字符串转换成数组arr1
string[] arrtemp = b.Split(',');
int[] arr2 = new int[arrtemp.Length]; //用来存放将字符串转换成int[]
for (int i = 0; i < arrtemp.Length; i++)
{
arr2[i] = int.Parse(arrtemp[i]);
}
foreach (var arr in arr1.ToList())
{
Console.WriteLine(arr);
}
先转字符串
再
input numberOfElements=3 就从左向右substring 3个 ，在从右向佐 substring 总长-3个
再拼在一起 变回字符串
[解决办法]
变回数组
[解决办法]
前半部倒置，后半部倒置，再整个倒置，代码回去在弄，上课中。。。
用的是BA=(A倒置B倒置)倒置
[解决办法]
public int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements)
{
//--加一下那其他的判断
for (int i = numberOfElements;i<array.length; i++)
{
array[i-numberOfElements]=array[i];
}
return array.Except(temp_arr).Union(temp_arr).ToArray();
}
[解决办法]
- C# code
public int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements) {//--加一下那其他的判断 for (int i = numberOfElements;i<array.length; i++) { array[i-numberOfElements]=array[i]; } return array }
------解决方案--------------------
[解决办法]
=10要什么效果
[解决办法]
上面那个思想已经很简单了，不容易写错了。。。这个是编程珠玑里面的题目吧？
[解决办法]
- C# code
public int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements) { numberOfElements = Math.Abs(array.Length - numberOfElements); for (int i = 0; i < numberOfElements; i++) { for (int j = array.Length-1; j >0 ; j--) { int temp_move = array[j]; array[j] = array[j -1]; array[j - 1] = temp_move; } } return array; }
[解决办法]
- C# code
public void MoveSubArrayToTheEnd(int[] array, int numberOfElements) { var p = new int[array.Length]; for (int i = 0; i < array.Length; i++) { p[i] = array[i]; if (i <(array.Length- numberOfElements)) { array[i] = array[i + numberOfElements]; } else { array[i] = p[i + numberOfElements-array.Length]; } } }
[解决办法]
public void MoveSubArrayToTheEnd(int[] array, int numberOfElements)
{
int temp;
int j = arry.Length - numberOfElements;
for (int i = 0; i++; i < numberOfElements)
{
temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
j++;
}
}
[解决办法]
public void MoveSubArrayToTheEnd(int[] array, int numberOfElements)
{
int temp;
int j = arry.Length - numberOfElements;
for (int i = 0; i++; i < numberOfElements)
{
temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
j++;
}
}
这么简单吗？
[解决办法]
LZ，数组长度+1，然后依次循环移下，不可以吗？[Quote=引用:]
[解决办法]
- C# code
public int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements) { for (int i = numberOfElements; i < array.length; i++) { for (int j = i; j >i-numberOfElements ; j--) { int temp_move = array[j-1]; array[j-1] = array[j]; array[j] = temp_move; } } return array; }
[解决办法]
貌似我这个方法可行哦~
上代码，直接控制台测试，OK
- C# code
private static int[] MoveSubArrayToTheEnd(int[] array, int numberOfElements){ if (numberOfElements > array.Length - 1) throw new ArgumentOutOfRangeException("numberOfElements"); for (int i = 0; i < numberOfElements; i++) { int tmp = array[0]; for (int m = 0; m < array.Length - 1; m++) { array[m] = array[m + 1]; } array[array.Length - 1] = tmp; } return array;}
------解决方案--------------------
test:
- C# code
int[] array = { 1, 2, 3, 4, 5, 6, 7 };int[] result = MoveSubArrayToTheEnd(array, 3);Console.WriteLine(string.Join(", ", Array.ConvertAll(result, delegate(int i) { return i.ToString(); })));int[] array2 = { 1, 2, 3, 4, 5, 6, 7 };int[] result2 = MoveSubArrayToTheEnd(array2, 5);Console.WriteLine(string.Join(", ", Array.ConvertAll(result2, delegate(int i) { return i.ToString(); })));/* output4, 5, 6, 7, 1, 2, 36, 7, 1, 2, 3, 4, 5*/
[解决办法]
- C# code
// 假设^表示逆序// A = (1,2,3) A^ = (3,2,1)// B = (4,5,6,7) B^ = (7,6,5,4)// 则：// AB = (1,2,3)(4,5,6,7)// (A^B^)^ = BA = (4,5,6,7)(1,2,3)//void MoveSubArrayToTheEnd(int[] array, int numberOfElements){ Array.Reverse(array, 0, numberOfElements); Array.Reverse(array, numberOfElements, array.Length - numberOfElements); Array.Reverse(array);}
[解决办法]
[解决办法]
- C/C++ code
void MoveSubArrayToTheEnd(int *arr, int arrsize, int size){ int n = size*sizeof(*arr); int *b = malloc(n); memcpy(b, arr, n); memcpy(arr, arr + size, arrsize - n); memcpy(arr + size + 1, b, n); free(b);}
[解决办法]
void MoveSubArrayToTheEnd(int[] array, int numberOfElements)
{
int i;
int n = array.length - 1;
if(numberOfElements<=0 || numberOfElements>=n)
{
for(i=0;i<n;i++)
{
printf("%d\n",array[i]);
}
}
else
{
for(i>=numberOfElements;i<n;i++)
{
printf("%d",array[i]);
}
for(i=0;i<numberOfElements;i++)
{
printf("%d\n",array[i]);
}
}
}
[解决办法]
- C# code
static void MoveSubArrayToTheEnd(int[] array, int numberOfElements) { int temp = 0; while (temp < numberOfElements) { int a = array[0]; for (int i = 1; i < array.Length; i++) { array[i - 1] = array[i]; } array[array.Length - 1] = a; temp++; } } static void MoveSubArrayToTheEnd2(int[] array, int numberOfElements) { int i = 0, temp; for (; i < numberOfElements / 2; i++) { temp = array[i]; array[i] = array[numberOfElements - i - 1]; array[numberOfElements - i - 1] = temp; } for (i = numberOfElements; i < (array.Length - numberOfElements) / 2 + numberOfElements - 1; i++) { temp = array[i]; array[i] = array[array.Length - i - 1]; array[array.Length - i - 1] = temp; } for (i = 0; i < array.Length/2; i++) { temp = array[i]; array[i] = array[array.Length - 1 - i]; array[array.Length - 1 - i] = temp; } }
[解决办法]
MoveSubArrayToTheEnd(int[] array, int numberOfElements)
{
while(arrayLenth-numberofElement)
{
for(int i=0;i<numberofElement;i++)
{int chang=a[i];
a[i]=a[N-i+1];
a[N-i+1]=chang;
}
if(i>N-2i)
MoveSubArrayToTheEnd(int[] array, int numberOfElements)
[解决办法]
可以上机调试吗？。。。
有复杂性的要求么。。。。
- C# code
public static void MoveSubArrayToTheEnd(int[] array, int n) { int length = array.Length; int s; int move = n % length; for (int i = 1; i <= move; i++) { s = array[0]; for (int j = 1; j < length ; j++) { array[j - 1] = array[j]; } array[length - 1] = s; } }
[解决办法]
把数组分成两步分，两部分分别进行倒置，然后整个数组倒置。
倒置就是把第一个和最后一个交换，第二个和倒数第二个交换...
[解决办法]