首页 > 试题广场 >

牛牛和罗马数字智力游戏

[编程题]牛牛和罗马数字智力游戏
  • 热度指数:256 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛和朋友在玩耍时发现了一款关于罗马数字的智力游戏。在这个游戏中,他们首先需要将一个给定的整数 num 转换为对应的罗马数字。但是,他们发现,当他们每次转换后的结果字符串长度达到了一个阈值 limit 时,他们需要将字符串反转。请编写一个函数,将给定的整数 num 转换为对应的罗马数字,并按照上述规则进行反转操作。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
通常字符可以拼接,相同的字符并列就是几倍,同时小的数字在大的数字的右边表示相加,大的数字在小的数字右边表示大数减小数。例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

示例1

输入

3,4

输出

"III"

说明

长度不超过4,不用反转
示例2

输入

4,2

输出

"VI"

说明

"IV"长度达到2,进行反转

备注:

1 <= num <= 3999
1 <= limit <= 15

哈希表+数学理解
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @param limit int整型 
     * @return string字符串
     */
    string integerToRomanWithReverse(int num, int limit) {
        // write code here
        // 哈希表+数学
        unordered_map<int, string> um;
        um[1] = "I";
        um[4] = "IV";
        um[5] = "V";
        um[9] = "IX";
        um[10] = "X";
        um[40] = "XL";
        um[50] = "L";
        um[90] = "XC";
        um[100] = "C";
        um[400] = "CD";
        um[500] = "D";
        um[900] = "CM";
        um[1000] = "M";

        // 如何将阿拉伯数字转成罗马数字呢?
        string str = "";
        while(num)
        {
            if(um.count(num))
            {
                str += um[num];
                break;
            }

            if(num>1000)
            {
                str += um[1000];
                num -= 1000;
            }
            else if(num>900)
            {
                str += um[900];
                num -= 900;
            }
            else if(num>500)
            {
                str += um[500];
                num -= 500;
            }
            else if(num>400)
            {
                str += um[400];
                num -= 400;
            }
            else if(num>100)
            {
                str += um[100];
                num -= 100;
            }
            else if(num>90)
            {
                str += um[90];
                num -= 90;
            }
            else if(num>50)
            {
                str += um[50];
                num -= 50;
            }
            else if(num>40)
            {
                str += um[40];
                num -= 40;
            }
            else if(num>10)
            {
                str += um[10];
                num -= 10;
            }
            else if(num>9)
            {
                str += um[9];
                num -= 9;
            }
            else if(num>5)
            {
                str += um[5];
                num -= 5;
            }
            else if(num>4)
            {
                str += um[4];
                num -= 4;
            }
            else
            {
                str += um[1];
                num -= 1;
            }
        }

        // 反转字符串
        if((int)str.size()>=limit)
            reverse(str.begin(),str.end());
        
        return str;
    }
};

发表于 2024-05-21 23:01:15 回复(0)