我現(xiàn)在在做一個叫《leetbook》的開源書項目康震，把解題思路都同步更新到github上了妙黍，需要的同學(xué)可以去看看
地址：https://github.com/hk029/leetcode
這個是書的地址：https://hk029.gitbooks.io/leetbook/
這里寫圖片描述
- Integer to Roman[M]
問題
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
思路
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1,000 |
分析羅馬數(shù)字的規(guī)律：
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1,000 |
上面是羅馬數(shù)字所有的符號作媚。
羅馬數(shù)字的規(guī)則：
一般情況下随珠，從左到右從大到小排补疑，字母代表的數(shù)字累加瘦馍。
比如：
XII = 12
MDCCLXVI= 1000+500+100+100+50+10+5+1
但是有特殊情況，就是腌零，如果數(shù)字的范圍在大數(shù)減小數(shù)的范圍內(nèi)梯找，則會出現(xiàn)小數(shù)在大數(shù)前面的情況，代表（大數(shù)-小數(shù)）
IV = 5-1
IX= 10 - 1 = 9
XL = 50-10 = 40
| Symbol | Value |
|---|---|
| IV | 4 |
| IX | 9 |
| XL | 40 |
| XC | 90 |
| CD | 400 |
| CM | 900 |
思路1——循環(huán)
一旦把所有可能的情況符號情況都列舉出來了益涧，就好做了锈锤。
我們現(xiàn)在拿到一個數(shù)N
- 我們就去表里面找不超過它的最大的數(shù)x，
- 然后把它入我們的輸出字符串中闲询，然后將數(shù)N-=x久免，
- 繼續(xù)執(zhí)行這個操作，直到N=0
public class Solution {
public String intToRoman(int num) {
int list[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String chars[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int i = 0;
String out="";
while(num > 0)
{
for(;i < list.length;i++)
if(num >= list[i])
break;
out+=chars[i];
num -= list[i];
}
return out;
}
}
思路2——查表
還有個更極端的方案扭弧，就是阎姥，把每位上可能出現(xiàn)的情況都列舉出來，剩下的鸽捻，只用查表就行了呼巴。
public class Solution {
public static String intToRoman(int num) {
String M[] = {"", "M", "MM", "MMM"};
String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}
}
