leetcode 179. Largest Number 数组可以组成最大的数-蒲公英云

leetcode 179. Largest Number 数组可以组成最大的数

Bertha 。 2022-05-29 01:09 245阅读 0赞

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

这道题和剑指offer读书笔记：第五章，优化时间和空间效率：问题05 把数组排成最小的数的做法一模一样

不过需要注意的是字符串数组头部多余的0要去掉，嗯嗯就这样

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
bool cmp(int a, int b)
{
    string aa = to_string(a);
    string bb = to_string(b);
    return aa + bb > bb + aa;
}
class Solution 
{
public:
    string largestNumber(vector<int>& a)
    {
        sort(a.begin(), a.end(), cmp);
        string res;
        for (int i : a)
            res += to_string(i);
        while (res.size() >= 2 && res[0] == '0')
            res.erase(res.begin());
        return res;
    }
};