之前那篇说另外一种写法的雏形出现在我的脑海中，现在终于都写完并且调试完成了。现在放上来，以免到时候又忘记了写过的东西。

现在又重构了一下那段代码，而且进行了比较多的调试都没问题了应该是比较稳定的这段程序。现在把重构后的代码把原代码覆盖，7月29日更新

今天面试的时候面试官有看过我这段代码说我这段代码当中含有会让系统宕机的可能，然后我回来之后灰常仔细的看终于都发现了那个可能了，那个erase那个函数那里如果firstElemIter==lastElemIter的时候，第一个if进去了然后后面那个if进去之后firstElemIter就会判断不等于lastElemIter这个时候进行循环减减的操作会导致在第一个元素--的操作然后就会宕机，然后我发现是必然的但是为什么之前的调试没办法调试出来呢？我在微软的vs平台上面调试的，然后拿一个比较小的数组进去测试没想到到了那个第一个元素的时候--操作不会进行然后那个isDeleted()函数也不会调用循环直接退出了好奇怪啊，但是代码明明跟到这里连个报错都没有然后那个lastElemIter还是指向第一个元素，后来我把这段代码改了从新调试发现也没问题，现在就把那个改了的代码放上来还有之前的有问题的代码保留吧因为后面就不知道我之前出问题没发现的地方了。8月12日更新。

#include<vector>#include<list>#include<iostream>usingnamespacestd;typedefvector<int>intArray_t;classStrangeInt{public:StrangeInt();StrangeInt(intvalue);StrangeInt(constStrangeInt&ref);boolisDeleted();voidsetDeleted(booldeleted);intgetValue();intgetRefCount();voidincRefCount();voiddecRefCount();booloperator<(constStrangeInt&ref);private:intrefCount;booldeleted;intvalue;};classStrangeIter{public:StrangeIter(list<StrangeInt>::iterator&iter,list<StrangeInt>*array,list<StrangeInt>::iterator&firstElemIter,list<StrangeInt>::iterator&lastElemIter);list<StrangeInt>::iteratorincIter();list<StrangeInt>::iteratordecIter();list<StrangeInt>::iteratorfirstElem();list<StrangeInt>::iteratorlastElem();voiderase();voidinsert(intvalue);boolisFirstElem();list<StrangeInt>::iteratorgetCurIter();voidincItsRefCount();voiddecItsRefCount();boolisEmpty();private:list<StrangeInt>::iterator&iter;list<StrangeInt>*array;list<StrangeInt>::iteratorlastDelPos;boollastHadDel;boolisFirst;list<StrangeInt>::iterator&firstElemIter;list<StrangeInt>::iterator&lastElemIter;boolhadDelFirst;boolhadDelLast;};StrangeInt::StrangeInt(){}StrangeInt::StrangeInt(intvalue):value(value),refCount(0),deleted(false){}StrangeInt::StrangeInt(constStrangeInt&ref):value(ref.value),refCount(ref.refCount),deleted(ref.deleted){}boolStrangeInt::isDeleted(){returndeleted;}voidStrangeInt::setDeleted(booldeleted){this->deleted=deleted;}intStrangeInt::getValue(){returnvalue;}intStrangeInt::getRefCount(){returnrefCount;}voidStrangeInt::incRefCount(){refCount++;}voidStrangeInt::decRefCount(){refCount--;}boolStrangeInt::operator<(constStrangeInt&ref){returnvalue<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>::iteratorStrangeIter::incIter(){if(iter==lastElemIter){iter=array->end();}else{while((++iter)->isDeleted());}returniter;}list<StrangeInt>::iteratorStrangeIter::decIter(){if(!isFirstElem()){while((--iter)->isDeleted());}returniter;}list<StrangeInt>::iteratorStrangeIter::firstElem(){returnfirstElemIter;}list<StrangeInt>::iteratorStrangeIter::lastElem(){returnlastElemIter;}boolStrangeIter::isFirstElem(){if(firstElem()==iter)returntrue;returnfalse;}voidStrangeIter::erase(){hadDelFirst=false;hadDelLast=false;if(lastElemIter==firstElemIter){hadDelFirst=true;hadDelLast=true;firstElemIter=array->end();lastElemIter=array->end();}elseif(iter==firstElemIter){hadDelFirst=true;while((++firstElemIter)->isDeleted());}elseif(iter==lastElemIter){hadDelLast=true;while((--lastElemIter)->isDeleted());}/*if(iter==firstElemIter){hadDelFirst=true;if(lastElemIter==firstElemIter){firstElemIter=array->end();}else{while((++firstElemIter)->isDeleted());}}elsehadDelFirst=false;if(iter==lastElemIter){hadDelLast=true;if(lastElemIter==firstElemIter){lastElemIter=array->end();}else{while((--lastElemIter)->isDeleted());}}elsehadDelLast=false;*/if(iter->getRefCount()>0){iter->setDeleted(true);lastDelPos=iter;lastHadDel=false;if(hadDelLast)iter=array->end();elsewhile((++iter)->isDeleted());}else{if(iter==array->begin()){isFirst=true;array->erase(iter++);if(hadDelLast)iter=array->end();elseif(iter->isDeleted())while((++iter)->isDeleted());}else{array->erase(iter--);lastDelPos=iter;if(!iter->isDeleted()){iter->incRefCount();}if(hadDelLast)iter=array->end();elsewhile((++iter)->isDeleted());}lastHadDel=true;}}voidStrangeIter::insert(intvalue){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>::iteratorStrangeIter::getCurIter(){returniter;}voidStrangeIter::incItsRefCount(){iter->incRefCount();}voidStrangeIter::decItsRefCount(){iter->decRefCount();}boolStrangeIter::isEmpty(){returnfirstElem()==array->end();}intsumOfArray(constvector<int>&array){intsum=0;intsize=array.size();for(inti=0;i<size;i++){sum+=array.at(i);}returnsum;}classMaxDivHelper{public:MaxDivHelper(list<StrangeInt>&array,vector<intArray_t>&result,intgroupSize,list<StrangeInt>::iterator&iter);boolmaxDivFun(intpreSize,vector<int>&preArray);voidsetGroupSize(intgroupSize);voidsetStart();private:list<StrangeInt>&array;vector<intArray_t>&result;intgroupSize;list<StrangeInt>::iterator&iter;list<StrangeInt>::iteratorfirstElemIter;list<StrangeInt>::iteratorlastElemIter;};MaxDivHelper::MaxDivHelper(list<StrangeInt>&array,vector<intArray_t>&result,intgroupSize,list<StrangeInt>::iterator&iter):array(array),result(result),groupSize(groupSize),iter(iter),firstElemIter(array.begin()),lastElemIter(array.end()){lastElemIter--;}voidMaxDivHelper::setGroupSize(intgroupSize){this->groupSize=groupSize;iter=array.begin();}voidMaxDivHelper::setStart(){iter=firstElemIter;}boolMaxDivHelper::maxDivFun(intpreSize,vector<int>&preArray){while(iter!=array.end()){if((preSize+iter->getValue())<=groupSize){preArray.push_back(iter->getValue());StrangeIterautoInsertIter(iter,&array,firstElemIter,lastElemIter);autoInsertIter.erase();if((preSize+preArray.back())==groupSize){if(autoInsertIter.isEmpty()){result.push_back(preArray);returntrue;}else{list<StrangeInt>::iteratorretIter=lastElemIter;while((--lastElemIter)->isDeleted());vector<int>grpArray(1,retIter->getValue());boolhadDel=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);returntrue;}if(hadDel){array.insert(retIter,grpArray.at(0));lastElemIter=--retIter;}else{retIter->setDeleted(false);lastElemIter=retIter;}}}else{if(maxDivFun(preSize+preArray.back(),preArray))returntrue;}autoInsertIter.insert(preArray.back());preArray.pop_back();}elsebreak;}returnfalse;}voidmaxDiv(constvector<int>&array,vector<intArray_t>&result){if(array.empty())return;list<StrangeInt>retList(array.begin(),array.end());retList.sort();intmaxNum=retList.back().getValue();vector<int>preArray(1,maxNum);if(retList.size()==1){result.push_back(preArray);return;}retList.pop_back();intsum=sumOfArray(array);if(sum%maxNum==0){result.push_back(preArray);intn=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();MaxDivHelpermaxDivHelper(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();}MaxDivHelpermaxDivHelper(retList,result,maxNum,retList.begin());for(intm=sum/maxNum;m>0;m--){if(sum%m==0){maxDivHelper.setGroupSize(sum/m);if(maxDivHelper.maxDivFun(preArray.at(0),preArray))break;}}}

我的测试代码还是和以前一样很简单，现在暂时想不到什么比较好的测试代码。

intmain(){inta[10000];//inta[]={1,2,4,5,100};//inta[]={1,1,1,1,1,1};//inta[]={3,3,4,6,2};//rand();for(inti=0;i<(sizeof(a)/sizeof(int));i++){//a[i]=i+1;if(i%2!=0)a[i]=1000-a[i-1];elsewhile((a[i]=(rand()%1000))<=0);}vector<int>array(a,a+(sizeof(a)/sizeof(int)));vector<intArray_t>result;maxDiv(array,result);cout<<"{";intresultSize=result.size();for(inti=0;i<resultSize;i++){if(i!=0)cout<<",";cout<<"{";vector<int>group=result.at(i);intgroupSize=group.size();for(intj=0;j<groupSize;j++){if(j!=0)cout<<",";cout<<group.at(j);}cout<<"}";}cout<<"}";cout<<"\n";cout<<"Themaxgroupnumthatcandividetohavesamesumgroupis:"<<resultSize;return0;}

好像跑完上面这段代码花了几毫秒的时间吧。数据再大就堆栈溢出了。