題目：給定一個整數(shù)數(shù)組，要求放回最大值的組合字符串.

例如 12， 345， 6789. 返回678934512

第一印象想用動態(tài)規(guī)劃，后來覺得不太合適，窮舉組合：

123456789

126789345

345126789

345678912

678912345

678934512

一共有N！種組合，時間復(fù)雜度也是N！。

換一種思路，用排序，快排的話時間復(fù)雜度為nlogn,空間復(fù)雜度為n,但注意的是不應(yīng)該按整形值的大小來排序

例如：554，55，5. 返回555554.

??????? 556，55，5. 返回556555.

所以在快速排序的基礎(chǔ)上比較方法要做一些處理。

bool Comp(string A, string B) {if(A.length == B.length)return int(A) > int(B);int i = 0;while(i<A.length&&i<B.length){if(A[i]>B[i]) return true;else if(A[i]<B[i]) return false;i++;}if(A.length>i){if(A[i]>B[0]) return true;else return false;}else{if(B[i]>A[0]) return false;else return true;} }

好了，我們來寫快速排序函數(shù)吧，先構(gòu)造一個單遍排序函數(shù)Piv

int Piv(ref Uint[] L, int low, int high) {int p = L[low];while(low<high){while(low<high&&Comp(L[high].tostring(),p.tostring())) high --;L[low]=L[high];while(low<high&&Comp(p.tostring(), L[low].tostring())) low++;L[high]=L[low];}L[low] = p;
reutnr low; }

在寫一個遞歸函數(shù)來執(zhí)行多遍遍歷Qsort

void Qsort(ref Uint[] L, int low, int high) {if(low < high){int p = Piv(L,low,high);Qsort(L,low,p-1);Qsort(L,p+1,high);} }

最后一個調(diào)用Maxbuild

string Maxbuild(Uint L) {Qsort(L,0,L.length-1);Buildstring MaxString = new Buildstring();L.each(a => Maxstring.app(a.tostring()));return MaxString; }

題目出處：https://leetcode.com/problems/largest-number/

AC的代碼

class Solution { public:string largestNumber(vector<int> &num) {if(num.size()<1) return "0";string largestString;vector<string> numstr;for(int i=0;i<num.size();i++){string a=intToString(num[i]);numstr.push_back(a);for(int j =numstr.size()-1;j>0;j--){string aa=numstr[j-1]+numstr[j];string bb=numstr[j]+numstr[j-1];if(aa.compare(bb)<0){string b=numstr[j-1];numstr[j-1]=numstr[j];numstr[j]=b;}}}if(numstr[0]=="0")return "0";for(int i=0;i<numstr.size();i++){largestString+=numstr[i];}return largestString;}string intToString(int a){if(a<=0)return "0";string astr;while(a!=0){astr=char(a%10+'0')+astr;a/=10;}return astr;} };

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/wuchenglong/p/5732358.html

總結(jié)

以上是生活随笔為你收集整理的面试算法：Maxbuild的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。