Skip to content

Commit cf7ad9f

Browse files
fishercoder1534fishercoder1534
committed
add 273
1 parent 1d5ef79 commit cf7ad9f

File tree

4 files changed

+67
-25
lines changed

4 files changed

+67
-25
lines changed

‎README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -111,7 +111,7 @@ Your ideas/fixes/algorithms are more than welcome!
111111
|422|[Valid Word Square](https://leetcode.com/problems/valid-word-square/)|[Solution](../master/src/main/java/com/stevesun/solutions/ValidWordSquare.java)| O(n) | O(1) | Easy|
112112
|421|[Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)|[Solution](../master/src/main/java/com/stevesun/solutions/_421.java)| O(n) | O(1) | Medium | Bit Manipulation, Trie
113113
|420|[Strong Password Checker](https://leetcode.com/problems/strong-password-checker/)|[Solution](../master/src/main/java/com/stevesun/solutions/StrongPasswordChecker.java)| ? | ? | Hard|
114-
|419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../master/src/main/java/com/stevesun/solutions/BattleshipsinaBoard.java) | O(n^2) |O(1) | Medium| DFS
114+
|419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../master/src/main/java/com/stevesun/solutions/_419.java) | O(m*n) |O(1) | Medium| DFS
115115
|417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../master/src/main/java/com/stevesun/solutions/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
116116
|415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../master/src/main/java/com/stevesun/solutions/AddStrings.java)| O(n)|O(1) | Easy|
117117
|414|[Third Maximum Number](https://leetcode.com/problems/third-maximum-number/)|[Solution](../master/src/main/java/com/stevesun/solutions/ThirdMaximumNumber.java)| O(n)|O(1) | Easy|
@@ -213,7 +213,7 @@ Your ideas/fixes/algorithms are more than welcome!
213213
|277|[Find the Celebrity](https://leetcode.com/problems/find-the-celebrity/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindtheCelebrity.java)| O(n)|O(1) | Medium|
214214
|276|[Paint Fence](https://leetcode.com/problems/paint-fence/)|[Solution](../master/src/main/java/com/stevesun/solutions/PaintFence.java)| O(n)|O(1) | Easy| DP
215215
|274|[H-Index](https://leetcode.com/problems/h-index/)|[Solution](../master/src/main/java/com/stevesun/solutions/HIndex.java)| O(nlogn)|O(1) | Medium|
216-
|273|[Integer to English Words](https://leetcode.com/problems/integer-to-english-words/)|[Solution](../master/src/main/java/com/stevesun/solutions/IntegertoEnglishWords.java)| O(n)|O(1) | Hard|
216+
|273|[Integer to English Words](https://leetcode.com/problems/integer-to-english-words/)|[Solution](../master/src/main/java/com/stevesun/solutions/_273.java)| O(n)|O(1) | Hard| Math, String
217217
|272|[Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/ClosestBinarySearchTreeValueII.java)| O(h+k)|O(h) | Hard| Stack
218218
|271|[Encode and Decode Strings](https://leetcode.com/problems/encode-and-decode-strings/)|[Solution](../master/src/main/java/com/stevesun/solutions/EncodeandDecodeStrings.java)| O(n)|O(1) | Medium|
219219
|270|[Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)|[Solution](../master/src/main/java/com/stevesun/solutions/ClosestBinarySearchTreeValue.java)| O(h)|O(1) | Easy| DFS

‎src/main/java/com/stevesun/solutions/IntegertoEnglishWords.java renamed to ‎src/main/java/com/stevesun/solutions/_273.java

Lines changed: 21 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -13,46 +13,48 @@
1313
Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
1414
There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)
1515
*/
16-
public class IntegertoEnglishWords {
16+
public class _273 {
1717

18-
private String[] digit = new String[] {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
19-
private String[] teen = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
20-
private String[] ten = new String[] {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
21-
private String[] thousand = new String[] {"Thousand", "Million", "Billion"};
18+
private String[] belowTen = new String[] {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
19+
private String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
20+
private String[] belowHundred = new String[] {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
21+
private String[] overThousand = new String[] {"Thousand", "Million", "Billion"};
2222

2323
public String numberToWords(int num) {
24-
String ans;
25-
if (num == 0)
26-
return digit[num];
24+
String result;
25+
if (num == 0) return belowTen[num];
2726

28-
ans = hundredHelper(num%1000);
27+
result = hundredHelper(num%1000);
2928
num = num/1000;
3029
int i = 0;
3130
while (i < 3 && num > 0) {
32-
if (num % 1000 > 0)
33-
ans = hundredHelper(num%1000) + thousand[i] + " " + ans;
31+
if (num % 1000 > 0) {
32+
result = hundredHelper(num % 1000) + overThousand[i] + " " + result;
33+
}
3434
num = num/1000;
3535
i++;
3636
}
3737

38-
return ans.trim();
38+
return result.trim();
3939
}
4040

4141
public String hundredHelper(int num) {
4242
String nstr = "";
4343
if (num >= 100) {
44-
nstr = digit[num/100] + " Hundred ";
44+
nstr = belowTen[num/100] + " Hundred ";
4545
}
4646
num = num%100;
4747
if (num >= 20) {
48-
if (num % 10 != 0)
49-
nstr = nstr + ten[num/10 - 2] + " " + digit[num%10] + " ";
50-
else
51-
nstr = nstr + ten[num/10 - 2] + " ";
48+
if (num % 10 != 0) {
49+
nstr = nstr + belowHundred[num / 10 - 2] + " " + belowTen[num % 10] + " ";
50+
}
51+
else {
52+
nstr = nstr + belowHundred[num / 10 - 2] + " ";
53+
}
5254
} else if (num >= 10) {
53-
nstr = nstr + teen[num%10] + " ";
55+
nstr = nstr + belowTwenty[num%10] + " ";
5456
} else if (num > 0){
55-
nstr = nstr + digit[num] + " ";
57+
nstr = nstr + belowTen[num] + " ";
5658
}
5759
return nstr;
5860
}

‎src/main/java/com/stevesun/solutions/BattleshipsinaBoard.java renamed to ‎src/main/java/com/stevesun/solutions/_419.java

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -25,10 +25,12 @@
2525
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
2626
2727
*/
28-
public class BattleshipsinaBoard {
28+
public class _419 {
2929

30-
/**Then I turned to Discuss and found this solution from the contributor of this problem: https://discuss.leetcode.com/topic/62970/simple-java-solution,
31-
* basically, it only counts the top-left one while ignoring all other parts of one battleship.*/
30+
/**credit: https://discuss.leetcode.com/topic/62970/simple-java-solution,
31+
* basically, it only counts the top-left one while ignoring all other parts of one battleship,
32+
* using the top-left one as a representative for one battle.
33+
* This is achieved by counting cells that don't have 'X' to the left and above them.*/
3234
public int countBattleships_no_modify_original_input(char[][] board) {
3335
if(board == null || board.length == 0) return 0;
3436
int count = 0, m = board.length, n = board[0].length;
@@ -80,7 +82,7 @@ public static void main(String...strings){
8082
{'.', '.', '.', 'X'},
8183
};
8284

83-
BattleshipsinaBoard test = new BattleshipsinaBoard();
85+
_419 test = new _419();
8486
System.out.println(test.countBattleships(board));
8587
}
8688
}

‎src/test/java/com/stevesun/_273Test.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._273;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
/**
10+
* Created by stevesun on 5/13/17.
11+
*/
12+
public class _273Test {
13+
private static _273 test;
14+
private static int num;
15+
16+
@BeforeClass
17+
public static void setup(){
18+
test = new _273();
19+
}
20+
21+
@Test
22+
public void test1(){
23+
num = 123;
24+
assertEquals("One Hundred Twenty Three", test.numberToWords(num));
25+
}
26+
27+
@Test
28+
public void test2(){
29+
num = 12345;
30+
assertEquals("Twelve Thousand Three Hundred Forty Five", test.numberToWords(num));
31+
}
32+
33+
@Test
34+
public void test3(){
35+
num = 1234567;
36+
assertEquals("One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven", test.numberToWords(num));
37+
}
38+
}

0 commit comments

Comments
 (0)