​LeetCode刷题实战179：最大数

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 最大数  ，我们先来看题面：

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

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

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

题意

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

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

示例

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"
           

解题

组成最大数应使得高位数字尽量大，所以首先按照高位数字从大到小对数组排序，然后一次从高位到低位组成最大数。注意若数组全为0，则直接返回一个0. 另外要注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

class Solution {
    public String largestNumber(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length - i - 1; j++){
                String s1 = nums[j] + "" + nums[j + 1];
                String s2 = nums[j + 1] + "" + nums[j];
                if(s1.compareTo(s2) < 0){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        String res = "";
        for(int i = 0; i < nums.length; i++){
            res += nums[i];
        }
        if(res.charAt(0) == '0'){
            return "0";
        }
        return res;
    }
}
           

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-160题汇总，希望对你有点帮助！

LeetCode刷题实战161：相隔为1的编辑距离

LeetCode刷题实战162：寻找峰值

LeetCode刷题实战163：缺失的区间

LeetCode刷题实战164：最大间距

LeetCode刷题实战165：比较版本号

LeetCode刷题实战166：分数到小数

LeetCode刷题实战167：两数之和 II - 输入有序数组

LeetCode刷题实战168：Excel表列名称

LeetCode刷题实战169：多数元素

LeetCode刷题实战170：两数之和 III - 数据结构设计

LeetCode刷题实战171：Excel表列序号

LeetCode刷题实战172：阶乘后的零

LeetCode刷题实战173：二叉搜索树迭代器

LeetCode刷题实战174：地下城游戏

LeetCode刷题实战175：组合两个表

LeetCode刷题实战176：第二高的薪水

LeetCode刷题实战177：第N高的薪水

LeetCode刷题实战178：分数排名