温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值

发布时间:2020-07-24 08:59:01 来源:网络 阅读:872 作者:abc1550030776 栏目:编程语言

    前几天去面试的时候,有家公司好奇怪进行机试,然后我就见到这道题,然后我当时好像做了一天了才做出来。中途的时候好像到2点多的时候以为做出来了。然后给了一组数据给我,然后发现有两组数据是异常的,然后就打断点在那里跟后来改了一些东西之后发先运行时报错和那个死循环,后来想到另外一种相似的思路,把之前的代码都注析掉了然后再来写,到7点钟的时候写完,但是调试还是出现运行时错误和死循环,到8点左右把程序调通,我想拍照回去研究研究的时候被拒绝了说公司规矩,然后我觉得那么短的题目很容易就能记住,回来进行构思另外一种写法然后写出来了,结果速度很慢一个21长度的数组要几秒钟才能算出结果,30个长度已经看不到停止的时候了。后来昨天有时间研究了下,改进了代码最终做一个随机数组好像能在几百毫秒算出分组情况吧,然后我又怕忘记之前写的代码所以就把这些代码记下来吧。

#include<vector>
#include<list>
#include<iostream>

using namespace std;

typedef vector<int> intArray_t;

int sumOfArray(const vector<int> &array) {
	int sum = 0;
	int size = array.size();
	for (int i = 0; i < size; i++) {
		sum += array.at(i);
	}
	return sum;
}

bool maxDivFun(list<int> &array, vector<intArray_t> &result, int groupSize, int preSize, vector<int> &preArray, list<int>::iterator iter) {
	while (iter != array.end()) {
		if ((preSize + *iter) <= groupSize) {
			preArray.push_back(*iter);
			bool isFirst = false;
			if (iter == array.begin()) {
				isFirst = true;
			}
			array.erase(iter++);
			if ((preSize + preArray.back()) == groupSize) {
				if (array.empty()) {
					result.push_back(preArray);
					return true;
				}
				else {

					
					list<int> retList(array.begin(), array.end());
					vector<int> grpArray(1, retList.back());
					retList.pop_back();
					if (maxDivFun(retList, result, groupSize, grpArray.at(0), grpArray, retList.begin())) {
						result.push_back(preArray);
						return true;
					}
					
					if (!isFirst)
						iter--;
				}
			}
			else if (isFirst) {
				if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter))
					return true;
			}
			else if (maxDivFun(array, result, groupSize, preSize + preArray.back(), preArray, iter--))
				return true;
			if (isFirst) {
				iter = array.begin();
				array.insert(iter, preArray.back());
			}
			else
				array.insert(++iter, preArray.back());
			preArray.pop_back();
		}
		else
			break;
	}
	return false;
}

void maxDiv(const vector<int> &array, vector<intArray_t> &result) {
	if (array.empty())
		return;
	list<int> retList(array.begin(), array.end());
	retList.sort();
	int maxNum = retList.back();
	vector<int> preArray(1, maxNum);
	if (retList.size() == 1) {
		result.push_back(preArray);
		return;
	}
	retList.pop_back();
	int sum = sumOfArray(array);
	if (sum % maxNum == 0) {
		result.push_back(preArray);
		int n = 0;
		while (retList.back() == maxNum) {
			result.push_back(preArray);
			retList.pop_back();
			if (retList.empty())
				return;
			n++;
		}
		preArray.at(0) = retList.back();
		retList.pop_back();
		if (maxDivFun(retList, result, maxNum, preArray.at(0), preArray, retList.begin())) {
			return;
		}
		retList.push_back(preArray.at(0));
		for (; n != 0; n--) {
			retList.push_back(maxNum);
		}
		preArray.at(0) = maxNum;
		result.clear();
	}
	for (int i = maxNum + 1; i <= sum; i++) {
		if (sum % i == 0 && maxDivFun(retList, result, i, preArray.at(0), preArray, retList.begin())) {
			break;
		}
	}
}

    然后我的测试代码很简单跑完下面这段程序我的电脑要两秒多的时间吧。

int main() {
	int a[10000];
	//int a[] = { 1, 2, 4, 5, 100 };
	//int a[] = { 1, 1, 1, 1, 1, 1 };
	//int a[] = { 3, 3, 4, 6, 2 };
	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++) {
		a[i] = i + 1;
	//	while ((a[i] = (rand() % 1000)) == 0);
	}
	vector<int> array(a, a + (sizeof(a)/sizeof(int)));
	vector<intArray_t> result;
	maxDiv(array, result);
	cout << "{";
	int resultSize = result.size();
	for (int i = 0; i < resultSize; i++) {
		if (i != 0)
			cout << ", ";
		cout << "{";
		vector<int> group = result.at(i);
		int groupSize = group.size();
		for (int j = 0; j < groupSize; j++) {
			if (j != 0)
				cout << ", ";
			cout << group.at(j);
		}
		cout << "}";
	}
	cout << "}";
	cout << "\n";
	cout << "The max group num that can divide to have same sum group is: " << resultSize;
	return 0;
}

    但是我又想了很久,一种改进的方法的雏形已经出现在我的脑海中,有时间再改,到时候调试没问题的话也放上来。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI