Article From:https://www.cnblogs.com/immiao0319/p/9064717.html

[Copy questions]

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

 [The act of violence:

Time analysis:

Spatial analysis:

 [After optimization]:

Time analysis:

Spatial analysis:

[Exotic flower condition:

[Exotic flower corner case]

When the number of digits is 0, you don’t have to say zero.English nameIt’s all right

So < the first place of the 10 array is “”

[Thinking problem]

I don’t know how to separate the figures. / k% k is OK, but the main point of this question is not to separate the numbers, but how to deal with them.10、20、100There are special numbers in English and hundred thousand million billion.

[Why not use other data structures or algorithms in English data structures or algorithms?

[A word of thought]

“English name “+”every timeAll new string’s helper function is connected.

[Input: Empty: normal condition: extra large: extra small: special case handled in the program: abnormal condition (illegal and unreasonable input):

[Drawing]

[A brush]

There may be a space string, so assign it to result first, and then unify string..trimOnce

[Two brush]

[Three brush]

[Four brush]

[Five brush]

  [Five minutes of naked eye debug results]:

[Summary:

Remember that there are special numbers in English names in 10, 20 and 100 and hundred thousand million billion in English.

helperEvery time in the functionNewly buildString, ability to connect with a general string with a + connection

[Complexity]: Time complexity: O (n) Space complexity: O(1)

[Algorithm thought: recursion / partition / greedy:

[Key template code]

[Other solutions]

[Follow Up]:

[LCThe subject changes and changes are given.

 [Code style]:

 [Is it the first time to write such driver funcion code]:

 

public class Solution {
    private final String[] belowTen = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    private final String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] belowHundred = new String[] {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        return helper(num); 
    }
    
    private String helper(int num) {
        String result = new String();
        if (num < 10) result = belowTen[num];
        else if (num < 20) result = belowTwenty[num -10];
        else if (num < 100) result = belowHundred[num/10] + " " + helper(num % 10);
        else if (num < 1000) result = helper(num/100) + " Hundred " +  helper(num % 100);
        else if (num < 1000000) result = helper(num/1000) + " Thousand " +  helper(num % 1000);
        else if (num < 1000000000) result = helper(num/1000000) + " Million " +  helper(num % 1000000);
        else result = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
        return result.trim();
    }
}

View Code

 

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *