【LeetCode每日一题】12. 整数转罗马数字
【LeetCode每日一题】12. 整数转罗马数字题目：罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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:
输入: num = 3
输出: "III"
题解：
下面将会展示两种方法，而这两种方法都是基于右区间压缩方法，不断贪心，右边大的数使用过之后，不会再进行选择，因此每次查找的数据范围依次缩小，例如第一次13个数，第二次有可能就变成11个数，依次类推。
第一种思路是贪心策略+枚举模拟
实现如下，具体可以对应到第二种方法注释部分代码。
for (int i = nums.size() - 1; i >= 0; i--) {
while (num >= nums) {
num -= nums;
ans += m];
}
}
第二种思路是二分查找法去查找小于等于当前数的元素。
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, yu = num % nums;
for (int i = 0; i < chu; i++) {
ans += m];
}
num = yu;
r = l - 1;
}
// for (int i = nums.size() - 1; i >= 0; i--) {
// while (num >= nums) {
// num -= nums;
// ans += m];
// }
// }
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 <= target) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};
本节完~
文档来源：51CTO技术博客https://blog.51cto.com/u_12205414/3252067
页:
[1]