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

怼烎@ 2022-08-05 14:25 204阅读 0赞

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

第一题

有一个长度为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;
    }

结果：

![Center][]

与笔试时写的代码对比：

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

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

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

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

[Center]: /images/20220805/f0a1a3e0b2ce46019d0644a5b28689f4.png