面试算法：Maxbuild

题目：给定一个整数数组，要求放回最大值的组合字符串.

例如 12， 345， 6789. 返回678934512

第一印象想用动态规划，后来觉得不太合适，穷举组合：

123456789

126789345

345126789

345678912

678912345

678934512

一共有N！种组合，时间复杂度也是N！。

换一种思路，用排序，快排的话时间复杂度为nlogn,空间复杂度为n,但注意的是不应该按整形值的大小来排序

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

        556，55，5. 返回556555.

所以在快速排序的基础上比较方法要做一些处理。

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

好了，我们来写快速排序函数吧，先构造一个单遍排序函数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; }

在写一个递归函数来执行多遍遍历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);} }

最后一个调用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;} };

　　

 

转载于:https://www.cnblogs.com/wuchenglong/p/5732358.html

总结

以上是生活随笔为你收集整理的面试算法：Maxbuild的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。