溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×

忘記密碼？

登錄注冊×

獲取短信驗(yàn)證碼

其他方式登錄

點(diǎn)擊登錄注冊即表示同意《億速云用戶服務(wù)條款》

用戶登錄×

賬戶密碼登錄

請使用微信掃描上方二維碼

使用幫助

請求超時(shí)！

請點(diǎn)擊重新獲取二維碼

一個(gè)整數(shù)數(shù)組，長度為n，將其分為m份，使各份的和相等，求m.(下)

發(fā)布時(shí)間：2020-07-12 22:37:29 來源：網(wǎng)絡(luò) 閱讀：534 作者：abc1550030776 欄目：編程語言

之前那篇說另外一種寫法的雛形出現(xiàn)在我的腦海中，現(xiàn)在終于都寫完并且調(diào)試完成了。現(xiàn)在放上來，以免到時(shí)候又忘記了寫過的東西。

現(xiàn)在又重構(gòu)了一下那段代碼，而且進(jìn)行了比較多的調(diào)試都沒問題了應(yīng)該是比較穩(wěn)定的這段程序。現(xiàn)在把重構(gòu)后的代碼把原代碼覆蓋，7月29日更新

今天面試的時(shí)候面試官有看過我這段代碼說我這段代碼當(dāng)中含有會讓系統(tǒng)宕機(jī)的可能，然后我回來之后灰常仔細(xì)的看終于都發(fā)現(xiàn)了那個(gè)可能了，那個(gè)erase那個(gè)函數(shù)那里如果firstElemIter==lastElemIter的時(shí)候，第一個(gè)if進(jìn)去了然后后面那個(gè)if進(jìn)去之后firstElemIter就會判斷不等于lastElemIter這個(gè)時(shí)候進(jìn)行循環(huán)減減的操作會導(dǎo)致在第一個(gè)元素--的操作然后就會宕機(jī)，然后我發(fā)現(xiàn)是必然的但是為什么之前的調(diào)試沒辦法調(diào)試出來呢？我在微軟的vs平臺上面調(diào)試的，然后拿一個(gè)比較小的數(shù)組進(jìn)去測試沒想到到了那個(gè)第一個(gè)元素的時(shí)候--操作不會進(jìn)行然后那個(gè)isDeleted()函數(shù)也不會調(diào)用循環(huán)直接退出了好奇怪啊，但是代碼明明跟到這里連個(gè)報(bào)錯(cuò)都沒有然后那個(gè)lastElemIter還是指向第一個(gè)元素，后來我把這段代碼改了從新調(diào)試發(fā)現(xiàn)也沒問題，現(xiàn)在就把那個(gè)改了的代碼放上來還有之前的有問題的代碼保留吧因?yàn)楹竺婢筒恢牢抑俺鰡栴}沒發(fā)現(xiàn)的地方了。8月12日更新。

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

using namespace std;

typedef vector<int> intArray_t;

class StrangeInt {
public:
	StrangeInt();
	StrangeInt(int value);
	StrangeInt(const StrangeInt &ref);
	bool isDeleted();
	void setDeleted(bool deleted);
	int getValue();
	int getRefCount();
	void incRefCount();
	void decRefCount();
	bool operator < (const StrangeInt &ref);
private:
	int refCount;
	bool deleted;
	int value;
};

class StrangeIter {
public:
	StrangeIter(list<StrangeInt>::iterator &iter, list<StrangeInt> *array, list<StrangeInt>::iterator &firstElemIter, list<StrangeInt>::iterator &lastElemIter);
	list<StrangeInt>::iterator incIter();
	list<StrangeInt>::iterator decIter();
	list<StrangeInt>::iterator firstElem();
	list<StrangeInt>::iterator lastElem();
	void erase();
	void insert(int value);
	bool isFirstElem();
	list<StrangeInt>::iterator getCurIter();
	void incItsRefCount();
	void decItsRefCount();
	bool isEmpty();
private:
	list<StrangeInt>::iterator &iter;
	list<StrangeInt> *array;
	list<StrangeInt>::iterator lastDelPos;
	bool lastHadDel;
	bool isFirst;
	list<StrangeInt>::iterator &firstElemIter;
	list<StrangeInt>::iterator &lastElemIter;
	bool hadDelFirst;
	bool hadDelLast;
};

StrangeInt::StrangeInt(){
}
StrangeInt::StrangeInt(int value) : value(value), refCount(0), deleted(false){
}

StrangeInt::StrangeInt(const StrangeInt& ref) : value(ref.value), refCount(ref.refCount), deleted(ref.deleted) {
}

bool StrangeInt::isDeleted() {
	return deleted;
}

void StrangeInt::setDeleted(bool deleted) {
	this->deleted = deleted;
}

int StrangeInt::getValue() {
	return value;
}

int StrangeInt::getRefCount() {
	return refCount;
}

void StrangeInt::incRefCount() {
	refCount++;
}

void StrangeInt::decRefCount() {
	refCount--;
}

bool StrangeInt::operator < (const StrangeInt &ref) {
	return value < ref.value;
}

StrangeIter::StrangeIter(list<StrangeInt>::iterator &iter, list<StrangeInt> *array, list<StrangeInt>::iterator &firstElemIter, list<StrangeInt>::iterator &lastElemIter) : iter(iter), array(array), lastHadDel(false), isFirst(false), firstElemIter(firstElemIter), lastElemIter(lastElemIter){
}

list<StrangeInt>::iterator StrangeIter::incIter() {
	
	if (iter == lastElemIter) {
		iter = array->end();
	}
	else {
		while ((++iter)->isDeleted());
	}
	return iter;
}

list<StrangeInt>::iterator StrangeIter::decIter() {
	if (!isFirstElem()) {
		while ((--iter)->isDeleted());
	}
	return iter;
}

list<StrangeInt>::iterator StrangeIter::firstElem() {
	return firstElemIter;
}

list<StrangeInt>::iterator StrangeIter::lastElem() {
	return lastElemIter;
}

bool StrangeIter::isFirstElem() {
	if (firstElem() == iter)
		return true;
	return false;
}

void StrangeIter::erase() {

	hadDelFirst = false;
	hadDelLast = false;
	if (lastElemIter == firstElemIter) {
		hadDelFirst = true;
		hadDelLast = true;
		firstElemIter = array->end();
		lastElemIter = array->end();
	}
	else if (iter == firstElemIter) {
		hadDelFirst = true;
		while ((++firstElemIter)->isDeleted());
	}
	else if (iter == lastElemIter) {
		hadDelLast = true;
		while ((--lastElemIter)->isDeleted());
	}
	
/*	if (iter == firstElemIter) {
		hadDelFirst = true;
		if (lastElemIter == firstElemIter) {
			firstElemIter = array->end();
		}
		else {
			while ((++firstElemIter)->isDeleted());
		}
	}
	else
		hadDelFirst = false;
	if (iter == lastElemIter) {
		hadDelLast = true;
		if (lastElemIter == firstElemIter) {
			lastElemIter = array->end();
		}
		else {
			while ((--lastElemIter)->isDeleted());
		}
	}
	else
		hadDelLast = false;
*/
	if (iter->getRefCount() > 0) {
		iter->setDeleted(true);
		lastDelPos = iter;
		lastHadDel = false;
		if (hadDelLast)
			iter = array->end();
		else
			while((++iter)->isDeleted());
	}
	else {
		if (iter == array->begin()) {
			isFirst = true;
			array->erase(iter++);
			if (hadDelLast)
				iter = array->end();
			else
				if (iter->isDeleted())
					while((++iter)->isDeleted());
		}
		else {
			array->erase(iter--);
			lastDelPos = iter;
			if (!iter->isDeleted()) {
				iter->incRefCount();
			}
			if (hadDelLast)
				iter = array->end();
			else
				while((++iter)->isDeleted());
		}
		lastHadDel = true;
	}
}

void StrangeIter::insert(int value) {
	if (lastHadDel) {
		if (isFirst) {
			iter = array->begin();
			array->insert(iter, value);
		}
		else {
			iter = lastDelPos;
			if (!iter->isDeleted()) {
				iter->decRefCount();
			}
			array->insert(++iter, value);
		}
		iter--;
	}
	else {
		lastDelPos->setDeleted(false);
		iter = lastDelPos;
	}
	if (hadDelFirst) {
		firstElemIter = iter;
	}
	if (hadDelLast) {
		lastElemIter = iter;
	}
	incIter();
}

list<StrangeInt>::iterator StrangeIter::getCurIter() {
	return iter;
}

void StrangeIter::incItsRefCount() {
	iter->incRefCount();
}

void StrangeIter::decItsRefCount() {
	iter->decRefCount();
}

bool StrangeIter::isEmpty() {
	return firstElem() == array->end();
}

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;
}

class MaxDivHelper{
public:
	MaxDivHelper(list<StrangeInt> &array, vector<intArray_t> &result, int groupSize, list<StrangeInt>::iterator &iter);
	bool maxDivFun(int preSize, vector<int> &preArray);
	void setGroupSize(int groupSize);
	void setStart();
private:
	list<StrangeInt> &array;
	vector<intArray_t> &result;
	int groupSize;
	list<StrangeInt>::iterator &iter;
	list<StrangeInt>::iterator firstElemIter;
	list<StrangeInt>::iterator lastElemIter;
};

MaxDivHelper::MaxDivHelper(list<StrangeInt> &array, vector<intArray_t> &result, int groupSize, list<StrangeInt>::iterator &iter) : array(array), result(result), groupSize(groupSize), iter(iter) , firstElemIter(array.begin()), lastElemIter(array.end()){
	lastElemIter--;
}

void MaxDivHelper::setGroupSize(int groupSize) {
	this->groupSize = groupSize;
	iter = array.begin();
}

void MaxDivHelper::setStart() {
	iter = firstElemIter;
}

bool MaxDivHelper::maxDivFun(int preSize, vector<int> &preArray) {
	while (iter != array.end()) {
		if ((preSize + iter->getValue()) <= groupSize) {
			preArray.push_back(iter->getValue());
			StrangeIter autoInsertIter(iter, &array, firstElemIter, lastElemIter);
			autoInsertIter.erase();
			if ((preSize + preArray.back()) == groupSize) {
				if (autoInsertIter.isEmpty()) {
					result.push_back(preArray);
					return true;
				}
				else {

					list<StrangeInt>::iterator retIter = lastElemIter;
					while ((--lastElemIter)->isDeleted());
					vector<int> grpArray(1, retIter->getValue());
					bool hadDel = false;
					if (retIter->getRefCount() > 0) {
						retIter->setDeleted(true);
					}
					else {
						hadDel = true;
						array.erase(retIter++);
					}
					setStart();
					if (this->maxDivFun(grpArray.at(0), grpArray)) {
						result.push_back(preArray);
						return true;
					}
					if (hadDel) {
						array.insert(retIter, grpArray.at(0));
						lastElemIter = --retIter;
					}
					else {
						retIter->setDeleted(false);
						lastElemIter = retIter;
					}
				}
			}
			else {
				if (maxDivFun(preSize + preArray.back(), preArray))
					return true;
			}
			autoInsertIter.insert(preArray.back());
			preArray.pop_back();
		}
		else
			break;
	}
	return false;
}

void maxDiv(const vector<int> &array, vector<intArray_t> &result) {
	if (array.empty())
		return;
	list<StrangeInt> retList(array.begin(), array.end());
	retList.sort();
	int maxNum = retList.back().getValue();
	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().getValue() == maxNum) {
			result.push_back(preArray);
			retList.pop_back();
			if (retList.empty())
				return;
			n++;
		}
		preArray.at(0) = retList.back().getValue();
		retList.pop_back();
		MaxDivHelper maxDivHelper(retList, result, maxNum, retList.begin());
		if (maxDivHelper.maxDivFun(preArray.at(0), preArray)) {
			return;
		}
		retList.push_back(preArray.at(0));
		for (; n != 0; n--) {
			retList.push_back(maxNum);
		}
		preArray.at(0) = maxNum;
		result.clear();
	}
	MaxDivHelper maxDivHelper(retList, result, maxNum, retList.begin());
	for (int m = sum/maxNum; m > 0; m--) {
		if (sum % m == 0 ) {
			maxDivHelper.setGroupSize(sum / m);
			if (maxDivHelper.maxDivFun(preArray.at(0), preArray))
				break;
		}
	}
}

我的測試代碼還是和以前一樣很簡單，現(xiàn)在暫時(shí)想不到什么比較好的測試代碼。

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 };
	//rand();
	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++) {
	//	a[i] = i + 1;
		if (i % 2 != 0)
			a[i] = 1000 - a[i - 1];
		else
			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;
}

好像跑完上面這段代碼花了幾毫秒的時(shí)間吧。數(shù)據(jù)再大就堆棧溢出了。

向AI問一下細(xì)節(jié)

推薦閱讀：

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

上一篇新聞：
nagios passive 被動監(jiān)控安裝
下一篇新聞：
輕量級高性能多維分析套件

猜你喜歡

AI
助
手

產(chǎn)品服務(wù)

地區(qū)劃分

專題活動

幫助支持

關(guān)于我們

售后咨詢

7*24小時(shí)在線電話：400-100-2938

7*24小時(shí)在線 QQ：800811969

關(guān)注億速云

億速云公眾號

手機(jī)網(wǎng)站二維碼