冰川网络2015春招笔试题第一题

昨天参加了在武大举行的深圳软件原管理中心宣讲会，公司较多且都是深圳的公司，这是其中一家（冰川网络）的笔试题，笔试题为四道编程题。

第一题

有一个长度为2n的数组将其分为两个长度相等的数组，要求两个数组和相差最小

// 有一个长度为2n的数组将其分为两个长度相等的数组
//要求两个数组和相差最小
#include <iostream>  
using namespace std;
void Divideonebytwo(const int *p, int*p1, int*p2, int n) //将数组分成两等分
{
 for (int i = 0; i < n / 2; i++)
 {
  p1[i] = p[i];
  p2[i] = p[i + n / 2];
 }
}

int Sum(int *p, int n) //求数组和
{
 int sum = 0;
 for (int i = 0; i < n; i++)
  sum += p[i];
 return sum;
}

int LeastAbsoluteValue(const int a, const int b) //最小绝对值
{
 int a1 = a;
 int b1 = b;
 if (a1 < 0)
  a1 = 0 - a1;
 if (b1 < 0)
  b1 = 0 - b1;
 return a1 <= b1 ? a : b;
}

void swap(int &a, int &b) //交换两个数组
{
 int d = a;
 a = b;
 b = d;
}

void TheMiniumValue(int *p1, int *p2, int n, int i, int &sum)  //将p1[i]与p2中数交换 使sum绝对值最小
{
 int k = -1;
 int Dvalue = sum;
 for (int d = 0; d < n; d++)
 {
  int thesum = sum + (p2[d] - p1[i]) * 2;  //注意是<span style="font-family: Arial, Helvetica, sans-serif;">p2[d] - p1[i]而不是p1[i]-p2[d]</span>
  int theDvalue = LeastAbsoluteValue(Dvalue, thesum);
  if (Dvalue != theDvalue)
  {
   Dvalue = theDvalue;
   k = d;
  }
 }
 if (k != -1)
 {
  swap(p1[i], p2[k]);
  sum = Dvalue;
 }
}

//输入:数组p长为n,数组p1、p2长为n/2
//函数功能：将数组p中元素不重复的分给p1、p2，使p1、p2和相差最小
void TheMainCode(const int *p, int*p1, int*p2, int n)
{
 if (n < 1 || n % 2 != 0)
  return;
 int k = n / 2;
 Divideonebytwo(p, p1, p2, n);
 int sum1 = Sum(p1, k);
 int sum2 = Sum(p2, k);
 int Dvalue = sum1 - sum2;
 for (int i = 0; i < k; i++)
 {
  if (Dvalue == 0)
   break;
  TheMiniumValue(p1, p2, k, i, Dvalue);
 }
}

void print(int *p, int n)
{
 for (int i = 0; i < n; i++)
  cout << p[i] << " ";
}

int main()
{ 
 int p[] = { 1, 1, 99, 81, 10, 8, 100, 8, 10, 100, 81, 99 };
 int n = sizeof(p)/sizeof(p[0]);
 int k = n / 2;
 int *p1 = new int[k];
 int *p2 = new int[k];
 TheMainCode(p, p1, p2, n);
 print(p, n);
 cout << endl;
 print(p1, k);
 cout << endl;
 print(p2, k);
 cout << endl;
}

结果：

与笔试时写的代码对比：

当拿到笔试题时已经5点半了，做题的时间有点紧。第一道题笔试的时候思路和上面的基本是一样的。

笔试时没有处理好的点有：（1）为了减少比较的次数对p1、p2中元素进行了排序，后来发现这是多余的，（2）一个很致命的错误，在TheMainCode函数中对p1、p2动态申请内存，函数TheMainCode中的p1、p2是由系统在栈里申请的指针，所指的内容与传人的p1、p2所指的内存一样，但已不是同一个指针了。后果p1、p2在函数前后没有变化且还会出现内存泄漏。

疑惑：会出现p1前面与p2交换的数，需要再次与p2中数进行交换的情况吗？通过多个例子还没有发现这种情况。（笔试时，这题做到一半时隐隐感觉要用动态规划来做，主函数调用的函数都没有写）

若出现这种情况解决方案：可用通过再次对TheMainCode函数进行调用，直到p1、p2没有进行元素交换为止。