Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit b362c92

Browse files
fishercoder1534fishercoder1534
committedNov 29, 2021
add a solution for 179
1 parent 8bc172c commit b362c92

File tree

2 files changed

+133
-79
lines changed

2 files changed

+133
-79
lines changed
 

‎src/main/java/com/fishercoder/solutions/_179.java

Lines changed: 80 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -1,89 +1,90 @@
11
package com.fishercoder.solutions;
22

3-
import java.util.Arrays;
4-
import java.util.Comparator;
3+
import java.util.*;
54

6-
/**
7-
* 179. Largest Number
8-
9-
Given a list of non negative integers, arrange them such that they form the largest number.
10-
11-
Example 1:
12-
13-
Input: [10,2]
14-
Output: "210"
15-
16-
Example 2:
17-
18-
Input: [3,30,34,5,9]
19-
Output: "9534330"
20-
21-
Note: The result may be very large, so you need to return a string instead of an integer.
22-
*/
235
public class _179 {
246

25-
public static class Solution1 {
26-
public String largestNumber(int[] num) {
27-
if (num.length == 0) {
28-
return "";
29-
}
30-
if (num.length == 1) {
31-
return Integer.toString(num[0]);
32-
}
33-
String[] str = new String[num.length];
34-
for (int i = 0; i < num.length; i++) {
35-
str[i] = Integer.toString(num[i]);
36-
}
37-
Arrays.sort(str, new StringComparator());
38-
StringBuilder sb = new StringBuilder("");
39-
for (int i = num.length - 1; i >= 0; i--) {
40-
sb.append(str[i]);
41-
}
42-
if (sb.charAt(0) == '0') {
43-
return "0";
44-
}
45-
return sb.toString();
46-
}
47-
48-
class StringComparator implements Comparator<String> {
49-
public int compare(String s1, String s2) {
50-
if (s1.length() == 0 && s2.length() == 0) {
51-
return 0;
52-
}
53-
if (s2.length() == 0) {
54-
return 1;
55-
}
56-
if (s1.length() == 0) {
57-
return -1;
58-
}
59-
for (int i = 0; i < s1.length() && i < s2.length(); i++) {
60-
if (s1.charAt(i) > s2.charAt(i)) {
61-
return 1;
62-
} else if (s1.charAt(i) < s2.charAt(i)) {
63-
return -1;
64-
}
7+
public static class Solution1 {
8+
public String largestNumber(int[] num) {
9+
if (num.length == 0) {
10+
return "";
11+
}
12+
if (num.length == 1) {
13+
return Integer.toString(num[0]);
14+
}
15+
String[] str = new String[num.length];
16+
for (int i = 0; i < num.length; i++) {
17+
str[i] = Integer.toString(num[i]);
18+
}
19+
Arrays.sort(str, new StringComparator());
20+
StringBuilder sb = new StringBuilder("");
21+
for (int i = num.length - 1; i >= 0; i--) {
22+
sb.append(str[i]);
23+
}
24+
if (sb.charAt(0) == '0') {
25+
return "0";
26+
}
27+
return sb.toString();
6528
}
66-
if (s1.length() == s2.length()) {
67-
return 0;
29+
30+
class StringComparator implements Comparator<String> {
31+
public int compare(String s1, String s2) {
32+
if (s1.length() == 0 && s2.length() == 0) {
33+
return 0;
34+
}
35+
if (s2.length() == 0) {
36+
return 1;
37+
}
38+
if (s1.length() == 0) {
39+
return -1;
40+
}
41+
for (int i = 0; i < s1.length() && i < s2.length(); i++) {
42+
if (s1.charAt(i) > s2.charAt(i)) {
43+
return 1;
44+
} else if (s1.charAt(i) < s2.charAt(i)) {
45+
return -1;
46+
}
47+
}
48+
if (s1.length() == s2.length()) {
49+
return 0;
50+
}
51+
if (s1.length() > s2.length()) {
52+
if (s1.charAt(0) < s1.charAt(s2.length())) {
53+
return 1;
54+
} else if (s1.charAt(0) > s1.charAt(s2.length())) {
55+
return -1;
56+
} else {
57+
return compare(s1.substring(s2.length()), s2);
58+
}
59+
} else {
60+
if (s2.charAt(0) < s2.charAt(s1.length())) {
61+
return -1;
62+
} else if (s2.charAt(0) > s2.charAt(s1.length())) {
63+
return 1;
64+
} else {
65+
return compare(s1, s2.substring(s1.length()));
66+
}
67+
}
68+
}
6869
}
69-
if (s1.length() > s2.length()) {
70-
if (s1.charAt(0) < s1.charAt(s2.length())) {
71-
return 1;
72-
} else if (s1.charAt(0) > s1.charAt(s2.length())) {
73-
return -1;
74-
} else {
75-
return compare(s1.substring(s2.length()), s2);
76-
}
77-
} else {
78-
if (s2.charAt(0) < s2.charAt(s1.length())) {
79-
return -1;
80-
} else if (s2.charAt(0) > s2.charAt(s1.length())) {
81-
return 1;
82-
} else {
83-
return compare(s1, s2.substring(s1.length()));
84-
}
70+
}
71+
72+
public static class Solution2 {
73+
/**
74+
* My completely original solution on 11/29/2021:
75+
* we'll just sort these numbers as if they are strings.
76+
*/
77+
public String largestNumber(int[] nums) {
78+
List<String> strings = new ArrayList<>();
79+
for (int num : nums) {
80+
strings.add(Integer.toString(num));
81+
}
82+
Collections.sort(strings, (a, b) -> (b + a).compareToIgnoreCase(a + b));
83+
StringBuilder sb = new StringBuilder();
84+
for (int i = 0; i < strings.size(); i++) {
85+
sb.append(strings.get(i));
86+
}
87+
return sb.charAt(0) == '0' ? "0" : sb.toString();
8588
}
86-
}
8789
}
88-
}
8990
}

‎src/test/java/com/fishercoder/_179Test.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._179;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _179Test {
10+
private static _179.Solution1 solution1;
11+
private static _179.Solution2 solution2;
12+
private static int[] nums;
13+
private static String expected;
14+
15+
@BeforeClass
16+
public static void setup() {
17+
solution1 = new _179.Solution1();
18+
solution2 = new _179.Solution2();
19+
}
20+
21+
@Test
22+
public void test1() {
23+
nums = new int[]{34323, 3432};
24+
expected = "343234323";
25+
assertEquals(expected, solution1.largestNumber(nums));
26+
assertEquals(expected, solution2.largestNumber(nums));
27+
}
28+
29+
@Test
30+
public void test2() {
31+
nums = new int[]{111311, 1113};
32+
expected = "1113111311";
33+
assertEquals(expected, solution1.largestNumber(nums));
34+
assertEquals(expected, solution2.largestNumber(nums));
35+
}
36+
37+
@Test
38+
public void test3() {
39+
nums = new int[]{3, 30, 34, 5, 9};
40+
expected = "9534330";
41+
assertEquals(expected, solution1.largestNumber(nums));
42+
assertEquals(expected, solution2.largestNumber(nums));
43+
}
44+
45+
@Test
46+
public void test4() {
47+
nums = new int[]{0, 0};
48+
expected = "0";
49+
assertEquals(expected, solution1.largestNumber(nums));
50+
assertEquals(expected, solution2.largestNumber(nums));
51+
}
52+
53+
}

0 commit comments

Comments
 (0)
Failed to load comments.