This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Roman numerals contain the following seven characters: I, V, X, L, C, D and M.

Character values I 1 V 5 X 10 L 50 C 100 D 500 M 1000Copy the code

For example, the Roman numeral 2 is written as II, which is two ones side by side. Write XII as X + II. Write XXVII as XX + V + II.

Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions, for example, 4 is not written as IIII, it’s written as IV. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Similarly, the number 9 represents IX. This particular rule applies only to the following six situations:

I can be put to the left of V (5) and X (10) to represent 4 and 9. X can be placed to the left of L (50) and C (100) to represent 40 and 90. C can be put to the left of D (500) and M (1000) to represent 400 and 900. Give you an integer and convert it to Roman numerals.

Example 1: Input: num = 3 Output: "III" Source: LeetCode Link: https://leetcode-cn.com/problems/integer-to-roman All rights reserved. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

• Today’s algorithm topic is character conversion topic, the meaning of the topic is easy to understand, according to the requirements of the code can complete the topic.
• We haven’t done this problem before, so we can use the initial force method, and we can use AC. But the code is too redundant. The brute force method is important, and the intuition helps to discover it

Redundant parts to find optimized space.

• The idea of cache is adopted to optimize the code structure and enhance the readability of the code.

Through the code

Violence law

    public String intToRoman(int num) {
        StringBuilder ans = new StringBuilder();

        if (num / 1000 > 0) {
            ans.append(getNumberRoman(num / 1000));
            num %= 1000;
        }
        if (num / 100 > 0) {
            ans.append(getNumberRoman1(num / 100));
            num %= 100;
        }
        if (num / 10 > 0) {
            ans.append(getNumberRoman2(num / 10));
            num %= 10;
        }
        if (num > 0 ) {
            ans.append(getNumberRoman3(num));
        }

        return ans.toString();
    }

    public String getNumberRoman(int num) {
        String ans = "";
        switch (num) {
            case 1:
                ans = "M";
                break;
            case 2:
                ans = "MM";
                break;
            case 3:
                ans = "MMM";
                break;
            default:
                break;
        }

        return ans;
    }

    public String getNumberRoman1(int num) {
        String ans = "";
        switch (num) {
            case 1:
                ans = "C";
                break;
            case 2:
                ans = "CC";
                break;
            case 3:
                ans = "CCC";
                break;            
            case 4:
                ans = "CD";
                break;
            case 5:
                ans = "D";
                break;                                
            case 6:
                ans = "DC";
                break;
            case 7:
                ans = "DCC";
                break;                                
            case 8:
                ans = "DCCC";
                break;
            case 9:
                ans = "CM";
                break;                               
            default:
                break;
        }

        return ans;
    }


    public String getNumberRoman2(int num) {
        String ans = "";
        switch (num) {
            case 1:
                ans = "X";
                break;
            case 2:
                ans = "XX";
                break;
            case 3:
                ans = "XXX";
                break;            
            case 4:
                ans = "XL";
                break;
            case 5:
                ans = "L";
                break;                                
            case 6:
                ans = "LX";
                break;
            case 7:
                ans = "LXX";
                break;                                
            case 8:
                ans = "LXXX";
                break;
            case 9:
                ans = "XC";
                break;                               
            default:
                break;
        }

        return ans;
    }


    public String getNumberRoman3(int num) {
        String ans = "";
        switch (num) {
            case 1:
                ans = "I";
                break;
            case 2:
                ans = "II";
                break;
            case 3:
                ans = "III";
                break;            
            case 4:
                ans = "IV";
                break;
            case 5:
                ans = "V";
                break;                                
            case 6:
                ans = "VI";
                break;
            case 7:
                ans = "VII";
                break;                                
            case 8:
                ans = "VIII";
                break;
            case 9:
                ans = "IX";
                break;                               
            default:
                break;
        }

        return ans;
    }

Copy the code

Cache optimization

    public String intToRoman(int num) {
        int[] nums = {1000.900.500.400.100.90.50.40.10.9.5.4.1};
        String[] romans = {"M"."CM"."D"."CD"."C"."XC"."L"."XL"."X"."IX"."V"."IV"."I"};

        StringBuilder ans = new StringBuilder();

        int idx = 0;
        while (idx < 13) {
            while (num >= nums[idx]) {
                ans.append(romans[idx]);
                num -= nums[idx];
            }
            idx++;
        }

        return ans.toString();
    }
Copy the code

conclusion

• Violence is O(n) in time, O(1) in space.
• The time complexity of the optimization method is O(n) and the space complexity is O(1).
• Although the time complexity of the two is the same, it is better to use cache optimization method!
• Stick to the daily question, come on!