之前那篇說另外一種寫法的雛形出現(xiàn)在我的腦海中,現(xiàn)在終于都寫完并且調試完成了。現(xiàn)在放上來,以免到時候又忘記了寫過的東西。
耿馬網站建設公司創(chuàng)新互聯(lián)建站,耿馬網站設計制作,有大型網站制作公司豐富經驗。已為耿馬近千家提供企業(yè)網站建設服務。企業(yè)網站搭建\外貿網站制作要多少錢,請找那個售后服務好的耿馬做網站的公司定做!
現(xiàn)在又重構了一下那段代碼,而且進行了比較多的調試都沒問題了應該是比較穩(wěn)定的這段程序?,F(xiàn)在把重構后的代碼把原代碼覆蓋,7月29日更新
今天面試的時候面試官有看過我這段代碼說我這段代碼當中含有會讓系統(tǒng)宕機的可能,然后我回來之后灰常仔細的看終于都發(fā)現(xiàn)了那個可能了,那個erase那個函數(shù)那里如果firstElemIter==lastElemIter的時候,第一個if進去了然后后面那個if進去之后firstElemIter就會判斷不等于lastElemIter這個時候進行循環(huán)減減的操作會導致在第一個元素--的操作然后就會宕機,然后我發(fā)現(xiàn)是必然的但是為什么之前的調試沒辦法調試出來呢?我在微軟的vs平臺上面調試的,然后拿一個比較小的數(shù)組進去測試沒想到到了那個第一個元素的時候--操作不會進行然后那個isDeleted()函數(shù)也不會調用循環(huán)直接退出了好奇怪啊,但是代碼明明跟到這里連個報錯都沒有然后那個lastElemIter還是指向第一個元素,后來我把這段代碼改了從新調試發(fā)現(xiàn)也沒問題,現(xià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)在暫時想不到什么比較好的測試代碼。
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ù)據(jù)再大就堆棧溢出了。
文章名稱:一個整數(shù)數(shù)組,長度為n,將其分為m份,使各份的和相等,求m.(下)
文章地址:http://muchs.cn/article48/ihdeep.html
成都網站建設公司_創(chuàng)新互聯(lián),為您提供靜態(tài)網站、響應式網站、全網營銷推廣、面包屑導航、移動網站建設、動態(tài)網站
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)