對于一個給定的字符串數組，請找到一種拼接順序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。 給定一個字符串數組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; }};新聞熱點
疑難解答
