对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。 给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。 测试样例： [“abc”,”de”],2 “abcde”
这道题目不能直接对字符串进行排序输出，比如 b ,ba,若按照字典序为 bba 实际的最小输出为bab，所以这个需要重新定义两个字符串的大小若str1+str2
class PRior {public: string findSmallest(vector<string> strs, int n) { if(strs.empty()) return string{}; quicksort(strs,0,n-1); string res{}; for(auto c:strs) res+=c; return res; } void quicksort(vector<string> &strs,int begin,int end) { if(begin<end) { int mid=quicksortmove(strs,begin,end); quicksort(strs,begin,mid-1); quicksort(strs,mid+1,end); } } int quicksortmove(vector<string> &strs,int begin,int end) { int l=begin; int r=end; string x=strs[l]; while(l<r){ while(l<r&&!comparestrless(strs[r],x)) --r; strs[l]=strs[r]; while(l<r&&!comparestrmore(strs[l],x)) ++l; strs[r]=strs[l]; } strs[l]=x; return l; } bool comparestrless(string a,string b) { if(a+b<b+a) return true; return false; } bool comparestrmore(string a,string b){ if(a+b>b+a) return true; return false; }};新闻热点
疑难解答
