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

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

    現在又重構了一下那段代碼，而且進行了比較多的調試都沒問題了應該是比較穩定的這段程序。現在把重構后的代碼把原代碼覆蓋，7月29日更新

    今天面試的時候面試官有看過我這段代碼說我這段代碼當中含有會讓系統宕機的可能，然后我回來之后灰常仔細的看終于都發現了那個可能了，那個erase那個函數那里如果firstElemIter==lastElemIter的時候，第一個if進去了然后后面那個if進去之后firstElemIter就會判斷不等于lastElemIter這個時候進行循環減減的操作會導致在第一個元素--的操作然后就會宕機，然后我發現是必然的但是為什么之前的調試沒辦法調試出來呢？我在微軟的vs平臺上面調試的，然后拿一個比較小的數組進去測試沒想到到了那個第一個元素的時候--操作不會進行然后那個isDeleted()函數也不會調用循環直接退出了好奇怪啊，但是代碼明明跟到這里連個報錯都沒有然后那個lastElemIter還是指向第一個元素，后來我把這段代碼改了從新調試發現也沒問題，現在就把那個改了的代碼放上來還有之前的有問題的代碼保留吧因為后面就不知道我之前出問題沒發現的地方了。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;
		}
	}
}

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

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

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