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

耿馬網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)建站,耿馬網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為耿馬近千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的耿馬做網(wǎng)站的公司定做！

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

    今天面試的時(shí)候面試官有看過我這段代碼說我這段代碼當(dāng)中含有會(huì)讓系統(tǒng)宕機(jī)的可能，然后我回來之后灰常仔細(xì)的看終于都發(fā)現(xiàn)了那個(gè)可能了，那個(gè)erase那個(gè)函數(shù)那里如果firstElemIter==lastElemIter的時(shí)候，第一個(gè)if進(jìn)去了然后后面那個(gè)if進(jìn)去之后firstElemIter就會(huì)判斷不等于lastElemIter這個(gè)時(shí)候進(jìn)行循環(huán)減減的操作會(huì)導(dǎo)致在第一個(gè)元素--的操作然后就會(huì)宕機(jī)，然后我發(fā)現(xiàn)是必然的但是為什么之前的調(diào)試沒辦法調(diào)試出來呢？我在微軟的vs平臺(tái)上面調(diào)試的，然后拿一個(gè)比較小的數(shù)組進(jìn)去測(cè)試沒想到到了那個(gè)第一個(gè)元素的時(shí)候--操作不會(huì)進(jìn)行然后那個(gè)isDeleted()函數(shù)也不會(huì)調(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
#include
#include

using namespace std;

typedef vector 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::iterator &iter, list *array, list::iterator &firstElemIter, list::iterator &lastElemIter);
	list::iterator incIter();
	list::iterator decIter();
	list::iterator firstElem();
	list::iterator lastElem();
	void erase();
	void insert(int value);
	bool isFirstElem();
	list::iterator getCurIter();
	void incItsRefCount();
	void decItsRefCount();
	bool isEmpty();
private:
	list::iterator &iter;
	list *array;
	list::iterator lastDelPos;
	bool lastHadDel;
	bool isFirst;
	list::iterator &firstElemIter;
	list::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::iterator &iter, list *array, list::iterator &firstElemIter, list::iterator &lastElemIter) : iter(iter), array(array), lastHadDel(false), isFirst(false), firstElemIter(firstElemIter), lastElemIter(lastElemIter){
}

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

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

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

list::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::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 &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 &array, vector &result, int groupSize, list::iterator &iter);
	bool maxDivFun(int preSize, vector &preArray);
	void setGroupSize(int groupSize);
	void setStart();
private:
	list &array;
	vector &result;
	int groupSize;
	list::iterator &iter;
	list::iterator firstElemIter;
	list::iterator lastElemIter;
};

MaxDivHelper::MaxDivHelper(list &array, vector &result, int groupSize, list::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 &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::iterator retIter = lastElemIter;
					while ((--lastElemIter)->isDeleted());
					vector 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 &array, vector &result) {
	if (array.empty())
		return;
	list retList(array.begin(), array.end());
	retList.sort();
	int maxNum = retList.back().getValue();
	vector 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;
		}
	}
}

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

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 array(a, a + (sizeof(a)/sizeof(int)));
	vector result;
	maxDiv(array, result);
	cout << "{";
	int resultSize = result.size();
	for (int i = 0; i < resultSize; i++) {
		if (i != 0)
			cout << ", ";
		cout << "{";
		vector 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ù)再大就堆棧溢出了。