Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
[分析] 贪心思想,任两个数字字符串a, b, 若 a + b > b + a, 则a 应排在 b 前面。
注意点:
1.Arrays.sort()不支持给int数组传自定义比较器,因此需要转为String数组进行排序。
2.要判断并处理前缀为0的结果。
public class Solution {
Comparator<String> comparator = new Comparator<String>() {
public int compare(String a, String b) {
String result1 = a + b;
String result2 = b + a;
return result1.compareTo(result2);
}
};
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0)
return "";
int N = nums.length;
String[] numstrs = new String[N];
for (int i = 0; i < N; i++)
numstrs[i] = String.valueOf(nums[i]);
Arrays.sort(numstrs, comparator);
StringBuilder sb = new StringBuilder();
for (int i = N - 1; i >= 0; i--)
sb.append(numstrs[i]);
// truncate prefix 0
// style 1
/* if (sb.charAt(0) == '0' && N > 1) {
int j = 0;
while (j < sb.length() - 1 && sb.charAt(j) == '0')
j++;
sb.delete(0, j);
}
return sb.toString();*/
// style 2
int i = 0;
while (i < sb.length() && sb.charAt(i) == '0')
i++;
if (i == sb.length())
return "0";
else
return sb.substring(i, sb.length());
}
}
分享到:
相关推荐
java入门 java_leetcode题解之179_Largest_Number
python python_leetcode题解之179_Largest_Number.py
- **快速选择算法(Kth Largest Element)**: 选择一个无序数组中的第k大的元素。 #### 二分搜索扩展 - **二分搜索变体(First Position of Target)**: 在排序数组中寻找目标值的第一个位置。 - **查找插入位置(Search...
java java_leetcode题解之Largest Number.java
【字符串知识】 在编程面试中,字符串是常...例如《合并两个有序数组》(https://leetcode-cn.com/problems/merge-sorted-array/)、《最大数字》(https://leetcode-cn.com/problems/largest-number/)以及《最大间距》...
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 maxArea 26.删除排序数组中的重复项 removeDuplicates 33.搜索旋转排序数组 ...34.在排序数组中查找元素的第一个和最后一个...largestNumber 324.摆
c++ C++_leetcode题解之747. Largest Number At Least Twice of Others.cpp
191 |[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./C++/number-of-1-bits.cpp) [Python](./Python/number-of-1-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 201 | [Bitwise AND of ...
Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number of Islands:DFS My Calendar II:小空间匹配 My ...
leetcode寻找最近的 设计模式 ...随时随记 随记笔记 ...最大数(golang)](Alg/leetcode/largestNumber.go [190. 颠倒二进制位(golang)](Alg/leetcode/reverseBits.go Docker 面试题 GO面试题 Redis面试题
- **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的矩形。 - **Palindrome Number**:判断一个数字是否是回文数。 - **Search a 2D ...
leetcode 答案 easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the ...
print(largestNumber(nums)) # 输出:9534330 ``` 通过这个题目,我们可以深入理解Python的字符串操作、排序功能以及如何自定义排序规则。同时,这也是一个很好的练习,可以帮助开发者提升解决实际问题的能力,尤其...
largest element from an unsorted array in linear time. (1) If the number of elements in an array is large .Divide the array into arrays each with 5 elements. n/5 arrays. (2) Compute Median of these 5 ...
* Largest Rectangle in Histogram:给定一个直方图,返回直方图中的最大矩形面积。这个题目需要使用栈的思想,将直方图中的每个矩形分解成更小的矩形,并找到最大矩形。 * Maximal Rectangle:给定一个矩形,返回...
Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick Select)算法,面试中很常考 链表类(Linked ...
1. Introduction ... Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
- **直方图中的最大矩形(Largest Rectangle in Histogram)**: 给定直方图的高度,计算能够组成的矩形的最大面积。 - **最大矩形(Maximal Rectangle)**: 在由'0'和'1'组成的二维矩阵中,找到只包含'1'的最大矩形,并...
加油站 leetcode 力码 该文件夹不仅包含算法和数据库的leetcode问题,还包含其他公开...largest distance from the sum of any subarray to the average of subarray (sum(a[n])/(k+1)). Output: a number of the Im
例如,"Kth Largest Element in an Array"可以通过优先队列在O(n log k)的时间复杂度内找到答案。 五、Java特性的运用 Java的一些高级特性如泛型、枚举、接口、匿名内部类、Lambda表达式等也会在解题中发挥重要作用...