剑指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日

相关推荐

  • leetcode125-验证回文串

    原题 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明: 本题中,我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a …

    算法 2020年5月21日
    0140
  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0300
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0210
  • leetcode150-逆波兰表达式求值

    原题 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰…

    2019年12月12日
    090
  • leetcode19-删除链表的倒数第N个节点

    原题 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为…

    算法 2019年12月15日
    090
  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04530
  • leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月20日
    080
  • leetcode1028-从先序遍历还原二叉树

    原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,…

    2020年6月18日
    02370
  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0160
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    060

发表回复

登录后才能评论