歡迎來到李耶的頻道【LeetCode面試題】。羅馬數(shù)字轉(zhuǎn)整數(shù) LeetCode 原題鏈接題目羅馬數(shù)字包含以下七種字符IVXLCD和M。字符 數(shù)值I 1V 5X 10L 50C 100D 500M 1000例如羅馬數(shù)字 2 寫做II即為兩個(gè)并列的 1。12 寫做XII即為XII。27 寫做XXVII即為XXVII。通常情況下羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例例如 4 不寫做IIII而是IV。數(shù)字 1 在數(shù)字 5 的左邊所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4。同樣地?cái)?shù)字 9 表示為IX。這個(gè)特殊的規(guī)則只適用于以下六種情況I可以放在V(5) 和X(10) 的左邊來表示 4 和 9。X可以放在L(50) 和C(100) 的左邊來表示 40 和 90。C可以放在D(500) 和M(1000) 的左邊來表示 400 和 900。給定一個(gè)羅馬數(shù)字將其轉(zhuǎn)換成整數(shù)。輸入s III 輸出3 輸入s IV 輸出4 輸入s IX 輸出9 輸入s LVIII 輸出58 解釋L 50, V 5, III 3 輸入s MCMXCIV 輸出1994 解釋M 1000, CM 900, XC 90, IV 4解法一直接遍歷哈希表 減法規(guī)則思路建立一個(gè)哈希表存儲(chǔ)字符到數(shù)值的映射。遍歷字符串中的每個(gè)字符如果當(dāng)前字符代表的數(shù)值小于下一個(gè)字符代表的數(shù)值說明遇到了減法規(guī)則如 IV此時(shí)從結(jié)果中減去當(dāng)前字符的數(shù)值否則加上當(dāng)前字符的數(shù)值。functionromanToInt(s){constmap{I:1,V:5,X:10,L:50,C:100,D:500,M:1000};letresult0;for(leti0;is.length;i){constcurrentmap[s[i]];constnexti1s.length?map[s[i1]]:0;if(currentnext){result-current;}else{resultcurrent;}}returnresult;}時(shí)間復(fù)雜度 / 空間復(fù)雜度O(n) / O(1)優(yōu)勢(shì)只需一次遍歷代碼簡(jiǎn)潔是面試中最推薦的寫法解法二字符串替換法思路先將特殊的六種減法規(guī)則替換為對(duì)應(yīng)的數(shù)值表示如 IV 替換為 “IIII”但數(shù)值上替換為特定標(biāo)識(shí)然后統(tǒng)一處理。functionromanToInt(s){constmap{I:1,V:5,X:10,L:50,C:100,D:500,M:1000};// 將減法規(guī)則的兩位字符替換為可處理的格式ss.replace(IV,IIII);ss.replace(IX,VIIII);ss.replace(XL,XXXX);ss.replace(XC,LXXXX);ss.replace(CD,CCCC);ss.replace(CM,DCCCC);letresult0;for(constcharofs){resultmap[char];}returnresult;}時(shí)間復(fù)雜度 / 空間復(fù)雜度O(n) / O(n)字符串替換創(chuàng)建新字符串優(yōu)勢(shì)將復(fù)雜的特殊規(guī)則轉(zhuǎn)化為統(tǒng)一處理思路獨(dú)特劣勢(shì)字符串替換效率較低面試中不推薦解法對(duì)比解法時(shí)間 / 空間復(fù)雜度優(yōu)勢(shì)推薦指數(shù)直接遍歷哈希表 減法規(guī)則O(n) / O(1)一次遍歷空間最優(yōu)?????字符串替換法O(n) / O(n)思路獨(dú)特易于理解特殊規(guī)則處理???擴(kuò)展題整數(shù)轉(zhuǎn)羅馬數(shù)字給定一個(gè)整數(shù)將其轉(zhuǎn)換為羅馬數(shù)字。Excel 表列序號(hào)給定一個(gè) Excel 表格中的列名稱返回其對(duì)應(yīng)的列序號(hào)如 A - 1, Z - 26, AA - 27。Excel 表列名稱給定一個(gè)正整數(shù)返回它在 Excel 表格中對(duì)應(yīng)的列名稱?！岸嘁娬卟┒嗦?wù)咧??！?—— 桓寬《鹽鐵論》關(guān)注李耶每天一道面試題一起卷起來