原题（来源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/
相关推荐
-
程序员面试金典01.07-旋转矩阵
原题（来源Leetcode） 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。 不占用额外内存空间能否做到？ 示例 ...
-
leetcode435-无重叠区间
原题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没...
-
leetcode1095-山脉数组中查找目标值
原题 （这是一个 交互式问题 ） 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in...
-
leetcode485-最大连续1的个数
原题 给定一个二进制数组， 计算其中最大连续1的个数。 示例 1: 输入： [1,1,0,1,1,1] 输出： 3 解释： 开头的两位和最后的三位都是连续1，所以最大连续1的个数是...
-
leetcode76-最小覆盖子串
原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
leetcode122-买卖股票的最佳时机II
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意： 你不能同...
-
leetcode1014-最佳观光组合
原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
leetcode1162-地图分析
原题 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域...
