剑指offer45-把数组排成最小的数

原题(来源Leetcode)

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2] 输出: "102"

示例 2:

输入: [3,30,34,5,9] 输出: "3033459"

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

解法

思想

将数组排序,类似于动态规划的思想,两个数之间相互连接比较一下。

代码

class Solution {
    public String minNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for(int i = 0;i<nums.length;i++){
            strings[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(strings,(s1,s2)->{
            String link1 = s1+s2;
            String link2 = s2+s1;
            for(int i = 0;i<link1.length();i++){
                if(link1.charAt(i)!=link2.charAt(i)) return link1.charAt(i)-link2.charAt(i);
            }
            return 0;
        });

        StringBuilder sb = new StringBuilder();
        for(String i:strings){
            sb.append(i);
        }
        return sb.toString();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer45-%e6%8a%8a%e6%95%b0%e7%bb%84%e6%8e%92%e6%88%90%e6%9c%80%e5%b0%8f%e7%9a%84%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月10日
下一篇 2020年6月12日

相关推荐

  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    060
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0110
  • leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates …

    2020年5月1日
    02720
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    090
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0170
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    080
  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0160
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0150
  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0150

发表回复

登录后才能评论