leetcode 12. 整数转罗马数字

朱雀 2023-07-01 14:00 186阅读 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;
            }
        }
    }
};