闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

一个拥有密码所有元素的非负整数数组 password

密码是 password 中所有元素拼接后得到的最小的一个数

请编写一个程序返回这个密码。

示例 1：

**输入：**password = [15, 8, 7]
输出：“1578”

示例 2：

**输入：**password = [0, 3, 30, 34, 5, 9]
输出：“03033459”

提示：

0 < password.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数

拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

只要保证最小的数在高位就行，很容易想到转成string后排序

排序其实就是两两比较，那a与b比较怎么判断谁在前，一开始想到a<b就行，但是会出现短字符串是长字符串前缀的问题如3和30，想到比较时结果就两种情况，ab与ba（330，303），那就可以直接比较字符串拼接a+b<b+a则a应该在前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    struct cmp {
        bool operator()(const string &a, const string &b) {
            return a + b < b + a;
        }
    };
    string crackPassword(vector<int> &password) {
        vector<string> strs;
        for (int i : password) {
            strs.push_back(to_string(i));
        }
        sort(strs.begin(), strs.end(), cmp());
        string ans;
        for (string i : strs) {
            ans += i;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void qsort(vector<string> &strs, int l, int r) {
    if (l >= r)
        return;
    int i = l;
    int j = r;
    while (i < j) {
        while (i < j && strs[l] + strs[j] <= strs[j] + strs[l])
            j--;
        while (i < j && strs[l] + strs[i] >= strs[i] + strs[l])
            i++;
        swap(strs[i], strs[j]);
    }
    swap(strs[l], strs[i]);
    qsort(strs, l, i - 1);
    qsort(strs, i + 1, r);
}