12. Integer to Roman**
https://leetcode.com/problems/integer-to-roman/
题目描述
Roman numerals are represented by seven different symbols: I
, V
, X
, L
, C
, D
and M
.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II
in Roman numeral, just two one’s added together. Twelve is written as, XII
, which is simply X + II
. The number twenty seven is written as XXVII
, which is XX + V + II
.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII
. Instead, the number four is written as IV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX
. There are six instances where subtraction is used:
-
I
can be placed beforeV
(5) andX
(10) to make 4 and 9. -
X
can be placed beforeL
(50) andC
(100) to make 40 and 90. -
C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: 3
Output: "III"
Example 2:
Input: 4
Output: "IV"
Example 3:
Input: 9
Output: "IX"
Example 4:
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
C++ 实现 1
这道题最直观的思路其实是:
class Solution {
public:
string intToRoman(int num) {
string res;
while (num > 0) {
if (num >= 1000) {
res += "M"
num -= 1000;
} else if (num >= 900) {
res += "CM";
num -= 900;
} else if (num >= 500) {
res += "D";
num -= 500;
}
....
}
}
};
但是写成上面这种形式, 浪费时间和精力. 使用二分法是个不错的选择.
class Solution {
public:
string intToRoman(int num) {
vector<int> choices = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
vector<string> symbols = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
string res;
while (num > 0) {
// 找到 choices 中第一个大于 num 的数
auto idx = std::upper_bound(choices.begin(), choices.end(), num);
num -= choices[idx - choices.begin() - 1];
res += symbols[idx - choices.begin() - 1];
}
return res;
}
};
珍妮的选择
发布了244 篇原创文章 · 获赞 6 · 访问量 1万+
私信
关注