LeetCode:Integer to Roman解題レポート
7965 ワード
Integer to Roman
Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.
SOLUTION 1:
大きいものから小さいものまで欲張りな書き方.大きいから小さいまでマッチし、現在の文字をできるだけ多くマッチさせます.
ローマ数字対照表:
http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm
View Code
2015.1.12 redo:
View Code
ホームページ君GITHUBへどうぞ:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/IntToRoman.java
Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.
SOLUTION 1:
大きいものから小さいものまで欲張りな書き方.大きいから小さいまでマッチし、現在の文字をできるだけ多くマッチさせます.
ローマ数字対照表:
http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm
1 package Algorithms.string;
2
3 public class IntToRoman {
4 public String intToRoman(int num) {
5 int nums[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
6 String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
7
8 StringBuilder sb = new StringBuilder();
9
10 int i = 0;
11 // 。
12 while (i < nums.length) {
13 if (num >= nums[i]) {
14 sb.append(romans[i]);
15 num -= nums[i];
16 } else {
17 i++;
18 }
19 }
20
21 return sb.toString();
22 }
23 }View Code
2015.1.12 redo:
1 public String intToRoman(int num) {
2 int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
3
4 /*
5 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
6 "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X" IX V, IV, I
7 */
8 String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
9
10 int i = 0;
11 StringBuilder sb = new StringBuilder();
12 // greedy.
13 while (i < nums.length) {
14 // bug 1: should use ">="
15 if (num >= nums[i]) {
16 sb.append(strs[i]);
17 // bug 2: should remember to reduce the nums[i].
18 num -= nums[i];
19 } else {
20 i++;
21 }
22 }
23
24 return sb.toString();
25 }View Code
ホームページ君GITHUBへどうぞ:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/IntToRoman.java