LeetCode 12 整數(shù)轉(zhuǎn)羅馬數(shù)字用貪心思想能減大的先減大的。 整數(shù)轉(zhuǎn)羅馬數(shù)字整數(shù)轉(zhuǎn)成羅馬數(shù)字。值對(duì)應(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。把面值和符號(hào)從大到小排好能減就減換個(gè)符號(hào)繼續(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();}為什么貪心一定對(duì)因?yàn)榱_馬數(shù)字的規(guī)則保證了每個(gè)值對(duì)應(yīng)的符號(hào)是獨(dú)立的、不會(huì)出現(xiàn)用了大的導(dǎo)致小的湊不出來(lái)。這跟人民幣的 100、50、20 不一樣——羅馬數(shù)字沒(méi)有用了 1 個(gè) C 就等于鎖死了 10 個(gè) X這種約束它們之間就是純線性加法。這道題你踩過(guò)什么坑或者你用別的語(yǔ)言實(shí)現(xiàn)過(guò)嗎評(píng)論區(qū)聊聊回頭復(fù)習(xí)也方便翻。