关键词:贪心 排序 快速排序
题目:破解闯关密码
思路:
快排+自己制定快排规则
开辟一个vector存string,自己制定排序规则,然后用快排比较string大小。
排序规则:
sort(strs.begin(),strs.end(),[](string& a,string& b){return a+b<b+a;});
复杂度计算:
时间复杂度O(nlogn)
空间复杂度O(n) //字符串vector
代码:
class Solution {
public:
string crackPassword(vector<int>& password) {
vector<string> strs;
string res;
for(int i=0;i<password.size();++i)
{
strs.push_back(to_string(password[i]));
}
sort(strs.begin(),strs.end(),[](string& a,string& b){return a+b<b+a;});
for(int i=0;i<strs.size();++i)
{
res.append(strs[i]);
}
return res;
}
};