LeetCode OJ-- Integer to Roman @

@表示有更优解法

https://oj.leetcode.com/problems/integer-to-roman/

将自然数，转换成罗马数字，输入范围为 1 ~ 3999，因为罗马数没有0.

用一个map，表示 1 ~ 9， 10 ~ 90， 100 ~ 900， 1000 ~ 3000，然后，把相应的罗马字母存起来。

之后，求出输入有几个 1000 ，几个 100 ，几个1来。

#include <iostream>

#include <map>

#include <string>

using namespace std;

class Solution {

public:

    string intToRoman(int num) {

        map<int,string> I2R;

        I2R.insert(make_pair( ,"I"));

        I2R.insert(make_pair( ,"II"));

        I2R.insert(make_pair( ,"III"));

        I2R.insert(make_pair( ,"IV"));

        I2R.insert(make_pair( ,"V"));

        I2R.insert(make_pair( ,"VI"));

        I2R.insert(make_pair( ,"VII"));

        I2R.insert(make_pair( ,"VIII"));

        I2R.insert(make_pair( ,"IX"));

        I2R.insert(make_pair( ,"X"));

        I2R.insert(make_pair( ,"XX"));

        I2R.insert(make_pair( ,"XXX"));

        I2R.insert(make_pair( ,"XL"));

        I2R.insert(make_pair( ,"L"));

        I2R.insert(make_pair( ,"LX"));

        I2R.insert(make_pair( ,"LXX"));

        I2R.insert(make_pair( ,"LXXX"));

        I2R.insert(make_pair( ,"XC"));

        I2R.insert(make_pair( ,"C"));

        I2R.insert(make_pair( ,"CC"));

        I2R.insert(make_pair( ,"CCC"));

        I2R.insert(make_pair( ,"CD"));

        I2R.insert(make_pair( ,"D"));

        I2R.insert(make_pair( ,"DC"));

        I2R.insert(make_pair( ,"DCC"));

        I2R.insert(make_pair( ,"DCCC"));

        I2R.insert(make_pair( ,"CM"));

        I2R.insert(make_pair( ,"M"));

        I2R.insert(make_pair( ,"MM"));

        I2R.insert(make_pair( ,"MMM"));

        string ans;

        int this_time = ;

        for(int jinzhi = ; jinzhi > ; jinzhi = jinzhi / )

        {

            this_time = num / jinzhi;

            this_time = this_time * jinzhi;

            if(this_time > )

                ans = ans + I2R[this_time];

            num = num % jinzhi;

        }

        return ans;

    }

};

更优解法，来自九章。

/**

 * Copyright: NineChapter

 * - Algorithm Course, Mock Interview, Interview Questions

 * - More details on: http://www.ninechapter.com/

 */

public class Solution {

    public String intToRoman(int num) {

        if(num <= ) {

            return "";

        }

        int[] nums = {, , , , , , , , , , , , };

        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder res = new StringBuilder();

        int digit=;

        while (num > ) {

            int times = num / nums[digit];

            num -= nums[digit] * times;

            for ( ; times > ; times--) {

                res.append(symbols[digit]);

            }

            digit++;

        }

        return res.toString();

    }

}

巴特西

LeetCode OJ-- Integer to Roman @

最新文章

热门文章