[LintCode/LeetCode] Largest Number [Comparator的使用]

xietao3 发布于2019-08-14 15:21 / 250人阅读

摘要：先将转化为，否则无法使用，其实转为也可以，这里用为例。然后就是最关键的一步创造一个，用以从大到小排列所有的元素。注意这里的顺序不能变。再将排列好的元素放入一个里，然后将转化为。

Problem

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

Example

Given [1, 20, 23, 4, 8], the largest formed number is 8423201.

Note

先将nums[]转化为String[]，否则无法使用Comparator，其实转为Integer[]也可以，这里用String为例。
然后就是最关键的一步：创造一个Comparator，用以从大到小排列所有的strs[]元素。注意：return (s2+s1).compareTo(s1+s2); 这里的顺序不能变。
再将排列好的str[i]元素放入一个StringBuilder sb里，然后将sb转化为String result。

如果这个result的第一个字符是0，那么我们不希望看到返回一个类似“000000000”的字符串，只要返回单字符的字符串"0"就可以了。
否则，返回result。

Solution

public class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = Integer.toString(nums[i]);
        }
        Arrays.sort(strs, new Comparator(){
            public int compare(String s1, String s2) {
                return (s2 + s1).compareTo(s1 + s2);
            }
            });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            sb.append(strs[i]);
        }
        String result = sb.toString();
        if (result.charAt(0) == "0") return "0";
        return result;
    }
}

海外云主机云服务器 Comparator Largest js的number数据类型 number

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65658.html

[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

摘要：这是一道简单的动规题目，同步更新数组解决了为负数的问题。即使是求最小乘积子序列，也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

meteor199 2019-08-14 15:21 评论0 收藏0
[LintCode/LeetCode] Maximal Square

摘要：类似这种需要遍历矩阵或数组来判断，或者计算最优解最短步数，最大距离，的题目，都可以使用递归。 Problem Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. Example For example, given t...

Drinkey 2019-08-14 15:14 评论0 收藏0
[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

dinfer 2019-08-14 15:33 评论0 收藏0
[Leetcode] Largest Number 最大整数

摘要：拼接比较法复杂度时间空间思路要拼成最大数，我们只要让较大的数排在前面，较小的数排在后面就行。注意如果排序后第一个数是，则直接返回，因为后面的数只有可能是了。 Largest Number Given a list of non negative integers, arrange them such that they form the largest number. For exa...

wuyumin 2019-08-14 12:40 评论0 收藏0