[演算法][JavaScript]演算法挑戰系列(6)-Integer to Roman

js javascript

神Q超人 2018-06-09 09:40:31 ‧ 7484 瀏覽

哈哈哈，先笑一下後開始文章，這次的題目雖然也是中級，不過就稍微簡單一點(說不定是我腦子變靈活了XD)，主要就是把數字轉換成字串而已，如果有時間的話可以試試看，也可以順便學一下關於羅馬數字的知識(其實我做過就忘了XD)！那以下正文：

題目名稱：Integer to Roman
難易度：中
題目內容：傳入一個0~3999之間的數字，並依規則將其轉為羅馬數字的格式。
規則：
(1)對照表：

羅馬數字	數字
I	1
V	5
X	10
L	50
C	100
D	500
M	1000
(2)羅馬數字由大排到小。
(3)2是由I+I所組成，875由D(500)+CCC(300)+L(50)+XX(20)+V(5)組成。
(4)如果遇到4的話，不是顯示為IIII，而是用5-1的方式寫作IV，所以48的話會由XL(40)+V(5)+III(3)組成。
(5)如果遇到9個話，不是顯示為VIIII或VIV，而是用10-1的方式寫作IX，所以496的話會由CD(400)+XC(90)+V(5)+I(1)組成。

PS.怕解釋得不清楚，如果有可以改進的麻煩各位大大在留言告訴我。

例如：
1.傳入1465會回傳MCDLXV
2.傳入3958會回傳MMMCMLVIII

那以下是這次的解法：

var intToRoman = function (num) {
    //用來裝要回答的羅馬字元
    let strRoman = "";
    //羅馬字元，從小排到大，代表1的和代表5的分開
    let arrRoman = ['I', 'X', 'C', 'M', 'V', 'L', 'D'];
    //判斷有幾位數
    let intLen = String(num).length-1;
    //每位數個別處理
    for (let i=intLen; i>=0 ; i--) {
        /*取目前處理的數字，從大位數處理到小位數
          String(num)[intLen-i]這個配合迴圈，
          會從數字的最左邊取到最右邊*/
        let nowNum = String(num)[intLen-i];
        //如果小於4的話就直接用迴圈跑目前位數的羅馬字元
        if(nowNum<4){
            for(let j=0; j<nowNum; j++){
                strRoman += arrRoman[i];
            };
            continue;
        };
        //如果等於4的話就把目前位數的羅馬字元和該位數代表5的羅馬字元擺在一起
        if(nowNum==4){
            strRoman += arrRoman[i] + arrRoman[i+4];    
            continue;
        };
        //如果等於9的話就把目前位數的羅馬字元和該位數再進位的羅馬字元擺在一起
        if(nowNum==9){
            strRoman += arrRoman[i] + arrRoman[i+1]; 
            continue;   
        };
        /*如果大於4的話，就先填上該位數代表5的羅馬字元，
          再跑迴圈填入剩下個數的羅馬字元*/
        if(nowNum>4){
            strRoman += arrRoman[i+4]; 
            for(let j=0; j<nowNum-5; j++){
                strRoman += arrRoman[i];
            }
        };
        /*以上的if內都加上continue是因為for迴圈內由4個不同的if做處理，
          所以就算他進入了第一個if也會跑其他3個判斷，
          因此考慮到效能問題，讓他處理完後就繼續下一次的迴圈，不再做多餘的if判斷，
          加上continue也可以避免掉處理9的時候進入“nowNum==9”後又進入“nowNum>4”中作多餘的處理*/
    };
    //處理完所有位數後回傳
    return strRoman;
};

接著也分享一下這次的成績，執行時間大概在152ms左右：

然後我在討論區中看到一個超級簡潔的寫法(怎麼當初沒有想到XD)，一樣我加上了註解，也讓大家看看：
原解答網址

//先把各種狀況存進陣列中
const ROMANS = [
    ["M", 1000],
    ["CM", 900],
    ["D", 500],
    ["CD", 400],
    ["C", 100],
    ["XC", 90],
    ["L", 50],
    ["XL", 40],
    ["X", 10],
    ["IX", 9],
    ["V", 5],
    ["IV", 4],
    ["I", 1]
]

var intToRoman = function(num) {
    let result = "";
    //直接去跑陣列的長度，從1000、900、500、400...處理到1
    for (let i = 0; i < ROMANS.length; i++) {
        //把這一次處理的數字放進變數中
        let [ roman, n ] = ROMANS[i];
        /*跑迴圈，如果num，比這次要處理的數字還大就繼續跑，
          如果num比較小就會跳出這次的迴圈，要處理的數字會慢慢變小，直到1*/
        while (num >= n) {
            //進入後先加上這次處理數字對應的羅馬字元
            result += roman;
            //之後num就減掉處理過的數字，所以num會越來越小
            num -= n;
        }
    }
    //跑完後num會剩0，result也會是處理對應完的羅馬字元
    return result;
};

看來我還是很難去解釋別人的程式碼，怎麼打註解都覺得很奇怪，還請各位大大包容，再給我幾次時間練習一定會進步的！這禮拜依然是熟悉的JavaScript，我也有在想下一次試著用別的語言解解看，不知道這樣會不會比較有新奇感，哈哈哈，下禮拜沒有意外的話，應該會分享SQL的題目轉換個心情XD，也請各位大大如果文章中有提的不清楚的地方、手誤或是哪裡可以改得更好，也請留言告訴我，我都會儘速修改的！謝謝大家！

最後讓我題外話推坑一下，最近看到還不錯的活動：The F2E - 前端修練精神時光屋，主要是在練習前端和切版，每個禮拜都會出一道題目，讓我們試著去做出相同的功能，當然如果沒時間的話，最低標準就是完成單一頁面就可以提交了！像這禮拜的題目是做個「todolist」，弱弱的我只來得及完成畫面操作而已，還沒有功能XD(以後有機會再分享)，那這個活動會持續九個禮拜，也就是有九個題目，有興趣的大大都可以進去看看！最後一個禮拜前都來得及哦！

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

3 則留言

小魚

iT邦大師 1 級 ‧ 2018-06-09 17:38:57

看起來這次是比較簡單一點，
不過正在趕東西，再找時間來參一腳...

問一個問題，
你是怎麼判斷執行的時間的，
可以分享一下嗎?
感恩~

回應 1
檢舉

神Q超人 iT邦研究生 5 級 ‧ 2018-06-09 22:27:26 檢舉

大大辛苦了！有時間再來參一腳就好了，希望不會對你們造成壓力XD

處理時間是我分享的這個網站內的一個功能，可以先從下圖右上角辦個會員：

之後在下方選好題目，並進行解題的時候會有個藍色的提交按鈕：

提交後下方就會出現運行結果，如果失敗的話他會告訴你說他輸入的值和你輸出的值是什麼，也會告訴你答案，以下是成功的樣子，點擊More Details就可以進入到那個圖表畫面了：

然後大大常做的C#模式也在裡面~可以選擇各種語言方式去解：

解完的題目前面就會出現一個勾勾，所以大大之前如果有分享的，就可以一起來收集勾勾XD

登入發表回應

小碼農米爾

iT邦高手 1 級 ‧ 2018-06-09 18:48:54

和大大分享的簡潔寫法有點像。

class Solution
{
  public:
    string intToRoman(int num)
    {
        string text[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int value[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int index = 0;

        string output;
        output.reserve(10);

        while (true)
        {
            //如果 num 為零離開迴圈
            if (num == 0)
            {
                break;
            }
            int val = value[index];
            //如果 num 比羅馬數字大繼續跑
            if (val <= num)
            {
                //num 除以羅馬數字的商為要寫入羅馬數字的個數
                int n = num / val;
                for (int i = 0; i < n; i++)
                {
                    //加入羅馬數字
                    output += text[index];
                }
                //取 num 除以羅馬數字的餘數
                num = num - (val * n);
            }
            //往下一個羅馬數字
            index++;
        }
        return output;
    }
};

回應 2
檢舉

小魚 iT邦大師 1 級 ‧ 2018-06-09 21:14:56 檢舉

我的想法跟你比較接近，改天來寫C#版的...

神Q超人 iT邦研究生 5 級 ‧ 2018-06-09 22:28:24 檢舉

一開始沒想到這個方式XD
真想把那些思考的時間都抓回來，哈哈哈。

登入發表回應

小魚

iT邦大師 1 級 ‧ 2018-06-10 11:50:43

花了十幾分鐘完成，
另外留言一篇好了...
這是C#版本

程式碼:

namespace ConsoleTest
{
    class Demo
    {
        private static List<Tuple<int, string>> romanList = new List<Tuple<int, string>>()
            {
                new Tuple<int, string>(1000, "M"),
                new Tuple<int, string>(900, "CM"),
                new Tuple<int, string>(500, "D"),
                new Tuple<int, string>(400, "CD"),
                new Tuple<int, string>(100, "C"),
                new Tuple<int, string>(90, "XC"),
                new Tuple<int, string>(50, "L"),
                new Tuple<int, string>(40, "XL"),
                new Tuple<int, string>(10, "X"),
                new Tuple<int, string>(9, "IX"),
                new Tuple<int, string>(5, "V"),
                new Tuple<int, string>(4, "IV"),
                new Tuple<int, string>(1, "I")
            };
        static void Main(string[] args)
        {
            string text = "";

            Console.WriteLine("將數字轉為羅馬數字，直接按Enter結束...");
            while (true)
            {
                Console.Write("請輸入數字:");
                text = Console.ReadLine();
                if (string.IsNullOrWhiteSpace(text))
                    break;
                int number = 0;
                if(!Int32.TryParse(text, out number))
                {
                    Console.WriteLine("輸入數字錯誤，請重新輸入...");
                    continue;
                }
                if (number > 3999 || number <= 0)
                {
                    Console.WriteLine("輸入數字過大或過小，請輸入1~3999的數字...");
                    continue;
                }
                string ans = GetRomanNumber(number);
                Console.WriteLine($"轉換成羅馬數字: {ans}");
                Console.WriteLine();
            }

            Console.WriteLine("按下任意鍵結束...");
            Console.ReadKey();
        }

        static string GetRomanNumber(int number)
        {
            string text = "";
            int index = 0;
            while(number > 0)
            {
                if (number >= romanList[index].Item1)
                {
                    text += romanList[index].Item2;
                    number -= romanList[index].Item1;
                }
                else
                    index++;
            }
            return text;
        }
    }
}

測試結果: