Zhiwei Zhang included in Algorithm

2021-12-09 2021-12-09 144 words One minute

Contents

https://leetcode-cn.com/problems/largest-number/

Description

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

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

Solution

将数字全部转为字符串，进行逐个比较，比较规则为：

从最高位开始比较，如果第一个数字较大，则把较大的排在前面
比较后续数字，将出现更大数字的数排在前面
若数字a为数字b的前缀，或相反，则返回a+b>b+a，判断如何构造可以使得数字更大

注意数字全为0的情况

sort里用lambda很香

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> nums_str;
        bool zero_flag = false;
        nums_str.clear();
        for (auto num : nums) {
            if (num != 0) zero_flag = true;
            nums_str.push_back(to_string(num));
        }
        if (!zero_flag) return "0";
        sort(nums_str.begin(), nums_str.end(), [](const string &a, const string &b) -> bool {
            if (a[0] != b[0]) {
                return a[0] > b[0];
            } 
            for (int i = 1; i < min(a.size(), b.size()); i++) {
                if (a[i] == b[i]) continue;
                return a[i] > b[i];
            }
            return a + b > b + a;
        });
        string ans = "";
        for (auto str : nums_str) {
            ans += str;
        }
        return ans;
    }
};