leetcode 12. 整数转罗马数字

朱雀 2023-07-01 14:00 106阅读 0赞

思路：一开始想用背包来做，后面发现完全没这个必要。

能用的数字只有 \{1,4,5,9,10,40,50,90,100,400,500,900,1000\}这13个，每次都从后面开始选出一个最大且小于等于当前值的数字即可。然后注意一下dfs的写法即可。

class Solution {
    public:
        int a[13]={1,4,5,9,10,40,50,90,100,400,500,900,1000};
        string intToRoman(int num) {
            map<int,string> mp;
            mp[1]="I";
            mp[5]="V";
            mp[4]="IV";
            mp[9]="IX";
            mp[10]="X";
            mp[50]="L";
            mp[40]="XL";
            mp[100]="C";
            mp[90]="XC";
            mp[500]="D";
            mp[1000]="M";
            mp[400]="CD";
            mp[900]="CM";
            vector<int> vec;
            string ans;
            dfs(num,vec);
            for(auto i:vec)
            {
                ans+=mp[i];
            }
            return ans;
            
        }
        void dfs(int val,vector<int> &vec)
        {
            if(val==0) return;
            for(int i=12;i>=0;i--)
            {
                if(val>=a[i])
                {
                    val-=a[i];
                    vec.push_back(a[i]);
                    dfs(val,vec);
                    break;
                }
            }
        }
    
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 12. 整数转罗马数字

思路：一开始想用背包来做，后面发现完全没这个必要。能用的数字只有 \{1,4,5,9,10,40,50,90,100,400,500,900,1000\}这13个，每次都从

朱雀/ 2023年07月01日 14:00/ 0 赞/ 107 阅读

相关 12. 整数转罗马数字

2021-05-14 LeetCode每日一题链接：[https://leetcode-cn.com/problems/integer-to-roman/][https

叁歲伎倆/ 2023年01月21日 06:20/ 0 赞/ 152 阅读

相关 12. 整数转罗马数字

[12. 整数转罗马数字][12.] 1、题目要求 > 题目描述 ![image-20201222211949695][] > 示例示例1：输入

港控/mmm°/ 2023年01月01日 02:57/ 0 赞/ 118 阅读

相关（js）leetcode 12. 整数转罗马数字

题目： > 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 > > 字符数值 > I 1 > V

痛定思痛。/ 2022年10月29日 01:59/ 0 赞/ 160 阅读

相关 leetcode12 整数转罗马数字

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

深藏阁楼爱情的钟/ 2022年10月09日 02:50/ 0 赞/ 146 阅读

相关 12. 整数转罗马数字

[https://leetcode-cn.com/problems/integer-to-roman/][https_leetcode-cn.com_problems_inte

电玩女神/ 2022年09月08日 10:25/ 0 赞/ 156 阅读

相关【LeetCode】12. 整数转罗马数字

题目链接：[https://leetcode-cn.com/problems/integer-to-roman/description/][https_leetcode-cn.

柔情只为你懂/ 2022年05月08日 15:40/ 0 赞/ 195 阅读

相关 leetcode:12.整数转罗马数字

题目描述：罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符数值 I 1 V

╰半夏微凉°/ 2022年03月02日 04:28/ 0 赞/ 189 阅读

相关 12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符数值 I 1 V 5

今天药忘吃喽~/ 2021年11月27日 02:12/ 0 赞/ 279 阅读

相关 12.整数转罗马数字

题目描述罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符数值 I

桃扇骨/ 2021年09月17日 01:08/ 0 赞/ 296 阅读