[C++] 【LeetCode每日一题】12. 整数转罗马数字

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

输入: num = 3
输出: "III"

for (int i = nums.size() - 1; i >= 0; i--) {
    while (num >= nums[i]) {
        num -= nums[i];
        ans += m[nums[i]];
    }
}

class Solution {
public:
    string intToRoman(int num) {
        map<int, string> m{
            {4, "IV"},{9, "IX"},{40, "XL"},{90, "XC"},{400, "CD"},{900, "CM"},
            {1, "I"}, {5, "V"}, {10, "X"}, {50, "L"}, {100, "C"}, {500, "D"}, {1000, "M"}
        };
        string ans;
        vector<int> nums{1,4,5,9,10,40,50,90,100,400,500,900,1000};
        int r = nums.size() - 1;
        while (num) {
            int l = bs(nums, num, r);
            int chu = num / nums[l], yu = num % nums[l];
            for (int i = 0; i < chu; i++) {
                ans += m[nums[l]];
            }
            num = yu;
            r = l - 1;
        }
        // for (int i = nums.size() - 1; i >= 0; i--) {
        //     while (num >= nums[i]) {
        //         num -= nums[i];
        //         ans += m[nums[i]];
        //     }
        // }
        return ans;
    }
    // 查找第一个小于等于x的数
    int bs(vector<int>& nums, int target, int r) {
        int l = 0;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

本节完~