LeetCode 12 整數(shù)轉(zhuǎn)羅馬數(shù)字用貪心思想能減大的先減大的。 整數(shù)轉(zhuǎn)羅馬數(shù)字整數(shù)轉(zhuǎn)成羅馬數(shù)字。值對應(yīng)I1, V5, X10, L50, C100, D500, M1000。特殊規(guī)則4→IV, 9→IX, 40→XL, 90→XC, 400→CD, 900→CM。就是換零錢——把 1994 拆成 1000900904 M CM XC IV。把面值和符號從大到小排好能減就減換個符號繼續(xù)減。publicStringintToRoman(intnum){int[]values{1000,900,500,400,100,90,50,40,10,9,5,4,1};String[]symbols{M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I};StringBuildersbnewStringBuilder();for(inti0;ivalues.length;i){while(numvalues[i]){num-values[i];sb.append(symbols[i]);}}returnsb.toString();}為什么貪心一定對因為羅馬數(shù)字的規(guī)則保證了每個值對應(yīng)的符號是獨立的、不會出現(xiàn)用了大的導(dǎo)致小的湊不出來。這跟人民幣的 100、50、20 不一樣——羅馬數(shù)字沒有用了 1 個 C 就等于鎖死了 10 個 X這種約束它們之間就是純線性加法。這道題你踩過什么坑或者你用別的語言實現(xiàn)過嗎評論區(qū)聊聊回頭復(fù)習(xí)也方便翻。