当前位置：首页 > ds >正文

LeetCode 刷题【12. 整数转罗马数字】

ds 2025/7/25 9:51:55

12. 整数转罗马数字

自己做

解：逐步相减

class Solution {
public:string intToRoman(int num) {string s = "";while(num / 1000 > 0){     //能否减1000s += 'M';num -= 1000;}while(num / 900 > 0){     //能否减900s += "CM";num -= 900;}while(num / 500 > 0){     //能否减500s += 'D';num -= 500;}while(num / 400 > 0){     //能否减400s += "CD";num -= 400;}while(num / 100 > 0){     //能否减100s += 'C';num -= 100;}while(num / 90 > 0){     //能否减90s += "XC";num -= 90;}while(num / 50 > 0){     //能否减50s += 'L';num -= 50;}while(num / 40 > 0){     //能否减40s += "XL";num -= 40;}while(num / 10 > 0){     //能否减10s += 'X';num -= 10;}while(num / 9 > 0){     //能否减9s += "IX";num -= 9;}while(num / 5 > 0){     //能否减5s += 'V';num -= 5;}while(num / 4 > 0){     //能否减4s += "IV";num -= 4;}while(num > 0){         //剩余的s += "I";num--;}return s;}
};

看题解

看思路自己敲

class Solution {
public:string intToRoman(int num) {string s = "";vector<vector<string>> v(10, vector<string>(4));            //建立二维数组，存储罗马数字//最初提供的罗马数字v[1][0] = "M";v[1][1] = "C";v[1][2] = "X";v[1][3] = "I";v[5][1] = "D";v[5][2] = "L";v[5][3] = "V";//建立罗马数字的组合v[2][0] = "MM";v[2][1] = "CC";v[2][2] = "XX";v[2][3] = "II";v[3][0] = "MMM";v[3][1] = "CCC";v[3][2] = "XXX";v[3][3] = "III";v[4][1] = "CD";v[4][2] = "XL";v[4][3] = "IV";v[6][1] = "DC";v[6][2] = "LX";v[6][3] = "VI";v[7][1] = "DCC";v[7][2] = "LXX";v[7][3] = "VII";v[8][1] = "DCCC";v[8][2] = "LXXX";v[8][3] = "VIII";v[9][1] = "CM";v[9][2] = "XC";v[9][3] = "IX";if (num / 1000 > 0) {           //千位s += v[num / 1000][0];num %= 1000;}if (num / 100 > 0) {            //百位s += v[num / 100][1];num %= 100;}if (num / 10 > 0) {             //十位s += v[num / 10][2];num %= 10;}if (num > 0) {                  //个位s += v[num][3];}return s;}
};

显然浪费时间在输入建立表上了

这次看了官方代码，再来

class Solution {
public:string intToRoman(int num) {const string thousands[] = {"", "M", "MM", "MMM"};const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};const string ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10];}
};

还是慢了。。。

官方代码

const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};class Solution {
public:string intToRoman(int num) {return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];}
};