Skip to content

Commit 66adda9

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0179
No.0179.Largest Number
1 parent 6c3ae56 commit 66adda9

File tree

6 files changed

+251
-43
lines changed

6 files changed

+251
-43
lines changed

‎solution/0100-0199/0179.Largest Number/README.md

Lines changed: 108 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,8 @@
3838

3939
<!-- 这里可写通用的实现逻辑 -->
4040

41+
**方法一：自定义排序**
42+
4143
先转成字符串列表，再对字符串列表进行字典序降序排列。最后将列表所有字符串拼接即可。
4244

4345
<!-- tabs:start -->
@@ -47,13 +49,11 @@
4749
<!-- 这里可写当前语言的特殊实现逻辑 -->
4850

4951
```python
50-
from functools import cmp_to_key
51-
5252
class Solution:
5353
def largestNumber(self, nums: List[int]) -> str:
54-
num_list = list(map(str, nums))
55-
num_list.sort(key=cmp_to_key(lambda x, y: int(y + x) - int(x + y)))
56-
return '0' if num_list[0] == '0' else ''.join(num_list)
54+
nums = [str(v) for v in nums]
55+
nums.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1))
56+
return "0" if nums[0] == "0" else "".join(nums)
5757
```
5858

5959
### **Java**
@@ -63,17 +63,111 @@ class Solution:
6363
```java
6464
class Solution {
6565
public String largestNumber(int[] nums) {
66-
List<String> numList = new ArrayList<>();
67-
for (int num : nums) {
68-
numList.add(String.valueOf(num));
66+
List<String> vs = new ArrayList<>();
67+
for (int v : nums) {
68+
vs.add(v + "");
6969
}
70-
numList.sort((a, b) -> (b + a).compareTo(a + b));
71-
if ("0".equals(numList.get(0))) return "0";
72-
StringBuilder sb = new StringBuilder();
73-
for (String s : numList) {
74-
sb.append(s);
70+
vs.sort((a, b) -> (b + a).compareTo(a + b));
71+
if ("0".equals(vs.get(0))) {
72+
return "0";
73+
}
74+
return String.join("", vs);
75+
}
76+
}
77+
```
78+
79+
### **C++**
80+
81+
```cpp
82+
class Solution {
83+
public:
84+
string largestNumber(vector<int>& nums) {
85+
vector<string> vs;
86+
for (int v : nums) vs.push_back(to_string(v));
87+
sort(vs.begin(), vs.end(), [](string& a, string& b) {
88+
return a + b > b + a;
89+
});
90+
if (vs[0] == "0") return "0";
91+
string ans;
92+
for (string v : vs) ans += v;
93+
return ans;
94+
}
95+
};
96+
```
97+
98+
### **Go**
99+
100+
```go
101+
func largestNumber(nums []int) string {
102+
vs := make([]string, len(nums))
103+
for i, v := range nums {
104+
vs[i] = strconv.Itoa(v)
105+
}
106+
sort.Slice(vs, func(i, j int) bool {
107+
return vs[i]+vs[j] > vs[j]+vs[i]
108+
})
109+
if vs[0] == "0" {
110+
return "0"
111+
}
112+
return strings.Join(vs, "")
113+
}
114+
```
115+
116+
### **C#**
117+
118+
```cs
119+
using System;
120+
using System.Globalization;
121+
using System.Collections.Generic;
122+
using System.Linq;
123+
using System.Text;
124+
125+
public class Comparer: IComparer<string>
126+
{
127+
public int Compare(string left, string right)
128+
{
129+
return Compare(left, right, 0, 0);
130+
}
131+
132+
private int Compare(string left, string right, int lBegin, int rBegin)
133+
{
134+
var len = Math.Min(left.Length - lBegin, right.Length - rBegin);
135+
for (var i = 0; i < len; ++i)
136+
{
137+
if (left[lBegin + i] != right[rBegin + i])
138+
{
139+
return left[lBegin + i] < right[rBegin + i] ? -1 : 1;
140+
}
141+
}
142+
143+
if (left.Length - lBegin == right.Length - rBegin)
144+
{
145+
return 0;
146+
}
147+
if (left.Length - lBegin > right.Length - rBegin)
148+
{
149+
return Compare(left, right, lBegin + len, rBegin);
150+
}
151+
else
152+
{
153+
return Compare(left, right, lBegin, rBegin + len);
154+
}
155+
}
156+
}
157+
158+
public class Solution {
159+
public string LargestNumber(int[] nums) {
160+
var sb = new StringBuilder();
161+
var strs = nums.Select(n => n.ToString(CultureInfo.InvariantCulture)).OrderByDescending(s => s, new Comparer());
162+
163+
var nonZeroOccurred = false;
164+
foreach (var str in strs)
165+
{
166+
if (!nonZeroOccurred && str == "0") continue;
167+
sb.Append(str);
168+
nonZeroOccurred = true;
75169
}
76-
return sb.toString();
170+
return sb.Length == 0 ? "0" : sb.ToString();
77171
}
78172
}
79173
```

‎solution/0100-0199/0179.Largest Number/README_EN.md

Lines changed: 106 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -38,31 +38,123 @@
3838
### **Python3**
3939

4040
```python
41-
from functools import cmp_to_key
42-
4341
class Solution:
4442
def largestNumber(self, nums: List[int]) -> str:
45-
num_list = list(map(str, nums))
46-
num_list.sort(key=cmp_to_key(lambda x, y: int(y + x) - int(x + y)))
47-
return '0' if num_list[0] == '0' else ''.join(num_list)
43+
nums = [str(v) for v in nums]
44+
nums.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1))
45+
return "0" if nums[0] == "0" else "".join(nums)
4846
```
4947

5048
### **Java**
5149

5250
```java
5351
class Solution {
5452
public String largestNumber(int[] nums) {
55-
List<String> numList = new ArrayList<>();
56-
for (int num : nums) {
57-
numList.add(String.valueOf(num));
53+
List<String> vs = new ArrayList<>();
54+
for (int v : nums) {
55+
vs.add(v + "");
56+
}
57+
vs.sort((a, b) -> (b + a).compareTo(a + b));
58+
if ("0".equals(vs.get(0))) {
59+
return "0";
60+
}
61+
return String.join("", vs);
62+
}
63+
}
64+
```
65+
66+
### **C++**
67+
68+
```cpp
69+
class Solution {
70+
public:
71+
string largestNumber(vector<int>& nums) {
72+
vector<string> vs;
73+
for (int v : nums) vs.push_back(to_string(v));
74+
sort(vs.begin(), vs.end(), [](string& a, string& b) {
75+
return a + b > b + a;
76+
});
77+
if (vs[0] == "0") return "0";
78+
string ans;
79+
for (string v : vs) ans += v;
80+
return ans;
81+
}
82+
};
83+
```
84+
85+
### **Go**
86+
87+
```go
88+
func largestNumber(nums []int) string {
89+
vs := make([]string, len(nums))
90+
for i, v := range nums {
91+
vs[i] = strconv.Itoa(v)
92+
}
93+
sort.Slice(vs, func(i, j int) bool {
94+
return vs[i]+vs[j] > vs[j]+vs[i]
95+
})
96+
if vs[0] == "0" {
97+
return "0"
98+
}
99+
return strings.Join(vs, "")
100+
}
101+
```
102+
103+
### **C#**
104+
105+
```cs
106+
using System;
107+
using System.Globalization;
108+
using System.Collections.Generic;
109+
using System.Linq;
110+
using System.Text;
111+
112+
public class Comparer: IComparer<string>
113+
{
114+
public int Compare(string left, string right)
115+
{
116+
return Compare(left, right, 0, 0);
117+
}
118+
119+
private int Compare(string left, string right, int lBegin, int rBegin)
120+
{
121+
var len = Math.Min(left.Length - lBegin, right.Length - rBegin);
122+
for (var i = 0; i < len; ++i)
123+
{
124+
if (left[lBegin + i] != right[rBegin + i])
125+
{
126+
return left[lBegin + i] < right[rBegin + i] ? -1 : 1;
127+
}
58128
}
59-
numList.sort((a, b) -> (b + a).compareTo(a + b));
60-
if ("0".equals(numList.get(0))) return "0";
61-
StringBuilder sb = new StringBuilder();
62-
for (String s : numList) {
63-
sb.append(s);
129+
130+
if (left.Length - lBegin == right.Length - rBegin)
131+
{
132+
return 0;
133+
}
134+
if (left.Length - lBegin > right.Length - rBegin)
135+
{
136+
return Compare(left, right, lBegin + len, rBegin);
137+
}
138+
else
139+
{
140+
return Compare(left, right, lBegin, rBegin + len);
141+
}
142+
}
143+
}
144+
145+
public class Solution {
146+
public string LargestNumber(int[] nums) {
147+
var sb = new StringBuilder();
148+
var strs = nums.Select(n => n.ToString(CultureInfo.InvariantCulture)).OrderByDescending(s => s, new Comparer());
149+
150+
var nonZeroOccurred = false;
151+
foreach (var str in strs)
152+
{
153+
if (!nonZeroOccurred && str == "0") continue;
154+
sb.Append(str);
155+
nonZeroOccurred = true;
64156
}
65-
return sb.toString();
157+
return sb.Length == 0 ? "0" : sb.ToString();
66158
}
67159
}
68160
```

‎solution/0100-0199/0179.Largest Number/Solution.cpp

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution {
2+
public:
3+
string largestNumber(vector<int>& nums) {
4+
vector<string> vs;
5+
for (int v : nums) vs.push_back(to_string(v));
6+
sort(vs.begin(), vs.end(), [](string& a, string& b) {
7+
return a + b > b + a;
8+
});
9+
if (vs[0] == "0") return "0";
10+
string ans;
11+
for (string v : vs) ans += v;
12+
return ans;
13+
}
14+
};

‎solution/0100-0199/0179.Largest Number/Solution.go

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
func largestNumber(nums []int) string {
2+
vs := make([]string, len(nums))
3+
for i, v := range nums {
4+
vs[i] = strconv.Itoa(v)
5+
}
6+
sort.Slice(vs, func(i, j int) bool {
7+
return vs[i]+vs[j] > vs[j]+vs[i]
8+
})
9+
if vs[0] == "0" {
10+
return "0"
11+
}
12+
return strings.Join(vs, "")
13+
}

‎solution/0100-0199/0179.Largest Number/Solution.java

Lines changed: 7 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,13 @@
11
class Solution {
22
public String largestNumber(int[] nums) {
3-
List<String> numList = new ArrayList<>();
4-
for (int num : nums) {
5-
numList.add(String.valueOf(num));
3+
List<String> vs = new ArrayList<>();
4+
for (int v : nums) {
5+
vs.add(v + "");
66
}
7-
numList.sort((a, b) -> (b + a).compareTo(a + b));
8-
if ("0".equals(numList.get(0))) return "0";
9-
StringBuilder sb = new StringBuilder();
10-
for (String s : numList) {
11-
sb.append(s);
7+
vs.sort((a, b) -> (b + a).compareTo(a + b));
8+
if ("0".equals(vs.get(0))) {
9+
return "0";
1210
}
13-
return sb.toString();
11+
return String.join("", vs);
1412
}
1513
}

‎solution/0100-0199/0179.Largest Number/Solution.py

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,5 @@
1-
from functools import cmp_to_key
2-
3-
41
class Solution:
52
def largestNumber(self, nums: List[int]) -> str:
6-
num_list = list(map(str, nums))
7-
num_list.sort(key=cmp_to_key(lambda x, y: int(y + x) - int(x + y)))
8-
return '0' if num_list[0] == '0' else ''.join(num_list)
3+
nums = [str(v) for v in nums]
4+
nums.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1))
5+
return "0" if nums[0] == "0" else "".join(nums)

0 commit comments

Comments
 (0)