歡迎來到李耶的頻道【LeetCode面試題】。羅馬數(shù)字轉(zhuǎn)整數(shù) LeetCode 原題鏈接題目羅馬數(shù)字包含以下七種字符IVXLCD和M。字符 數(shù)值I 1V 5X 10L 50C 100D 500M 1000例如羅馬數(shù)字 2 寫做II即為兩個并列的 1。12 寫做XII即為XII。27 寫做XXVII即為XXVII。通常情況下羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例例如 4 不寫做IIII而是IV。數(shù)字 1 在數(shù)字 5 的左邊所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4。同樣地數(shù)字 9 表示為IX。這個特殊的規(guī)則只適用于以下六種情況I可以放在V(5) 和X(10) 的左邊來表示 4 和 9。X可以放在L(50) 和C(100) 的左邊來表示 40 和 90。C可以放在D(500) 和M(1000) 的左邊來表示 400 和 900。給定一個羅馬數(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ī)則思路建立一個哈希表存儲字符到數(shù)值的映射。遍歷字符串中的每個字符如果當(dāng)前字符代表的數(shù)值小于下一個字符代表的數(shù)值說明遇到了減法規(guī)則如 IV此時從結(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;}時間復(fù)雜度 / 空間復(fù)雜度O(n) / O(1)優(yōu)勢只需一次遍歷代碼簡潔是面試中最推薦的寫法解法二字符串替換法思路先將特殊的六種減法規(guī)則替換為對應(yīng)的數(shù)值表示如 IV 替換為 “IIII”但數(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;}時間復(fù)雜度 / 空間復(fù)雜度O(n) / O(n)字符串替換創(chuàng)建新字符串優(yōu)勢將復(fù)雜的特殊規(guī)則轉(zhuǎn)化為統(tǒng)一處理思路獨特劣勢字符串替換效率較低面試中不推薦解法對比解法時間 / 空間復(fù)雜度優(yōu)勢推薦指數(shù)直接遍歷哈希表 減法規(guī)則O(n) / O(1)一次遍歷空間最優(yōu)?????字符串替換法O(n) / O(n)思路獨特易于理解特殊規(guī)則處理???擴展題整數(shù)轉(zhuǎn)羅馬數(shù)字給定一個整數(shù)將其轉(zhuǎn)換為羅馬數(shù)字。Excel 表列序號給定一個 Excel 表格中的列名稱返回其對應(yīng)的列序號如 A - 1, Z - 26, AA - 27。Excel 表列名稱給定一個正整數(shù)返回它在 Excel 表格中對應(yīng)的列名稱。“多見者博多聞?wù)咧?。?—— 桓寬《鹽鐵論》關(guān)注李耶每天一道面試題一起卷起來