iT邦幫忙

8

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

  • 分享至 

  • xImage
  •  

哈哈哈,先笑一下後開始文章,這次的題目雖然也是中級,不過就稍微簡單一點(說不定是我腦子變靈活了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左右:
https://ithelp.ithome.com.tw/upload/images/20180609/201069354FwNMgvjhh.jpg
然後我在討論區中看到一個超級簡潔的寫法(怎麼當初沒有想到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;
};

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

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


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
1
小魚
iT邦大師 1 級 ‧ 2018-06-09 17:38:57

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

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

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

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

處理時間是我分享的這個網站內的一個功能,可以先從下圖右上角辦個會員:
https://ithelp.ithome.com.tw/upload/images/20180609/20106935QnhV3YB4gy.jpg
之後在下方選好題目,並進行解題的時候會有個藍色的提交按鈕:
https://ithelp.ithome.com.tw/upload/images/20180609/20106935OEWHgSDOSw.jpg
提交後下方就會出現運行結果,如果失敗的話他會告訴你說他輸入的值和你輸出的值是什麼,也會告訴你答案,以下是成功的樣子,點擊More Details就可以進入到那個圖表畫面了:
https://ithelp.ithome.com.tw/upload/images/20180609/201069358rzLIOQqLQ.jpg
然後大大常做的C#模式也在裡面~可以選擇各種語言方式去解:
https://ithelp.ithome.com.tw/upload/images/20180609/20106935c2l6Z91kuX.png
解完的題目前面就會出現一個勾勾,所以大大之前如果有分享的,就可以一起來收集勾勾XD
https://ithelp.ithome.com.tw/upload/images/20180609/2010693545Lo8uoSVD.jpg

1
小碼農米爾
iT邦高手 1 級 ‧ 2018-06-09 18:48:54

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

https://ithelp.ithome.com.tw/upload/images/20180609/20106865mQdRHJQy4b.jpg

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;
    }
};
小魚 iT邦大師 1 級 ‧ 2018-06-09 21:14:56 檢舉

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

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

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

1
小魚
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;
        }
    }
}

測試結果:
https://ithelp.ithome.com.tw/upload/images/20180610/201056942llXDS0Q6U.jpg

看更多先前的回應...收起先前的回應...
神Q超人 iT邦研究生 5 級 ‧ 2018-06-12 13:31:40 檢舉

不好意思一直沒有時間看!
我今天下班再來回覆!

神Q超人 iT邦研究生 5 級 ‧ 2018-06-12 22:05:55 檢舉

我第一次看到C#原來也可以寫成像C++這種方式耶!
我是指運行的互動式視窗,
我還以為C#只能用在網頁上面.../images/emoticon/emoticon20.gif

小魚 iT邦大師 1 級 ‧ 2018-06-12 22:45:52 檢舉

C#本來就有WebForm跟WinForm啊,
而且WinForm用得還很廣...
單機有分WinForm跟WPF兩大類...

神Q超人 iT邦研究生 5 級 ‧ 2018-06-13 21:08:19 檢舉

哈哈哈,對耶!我完全忘記WinForm了/images/emoticon/emoticon25.gif
不過WPF我就沒有碰過了/images/emoticon/emoticon16.gif
話說小魚大大都在寫哪方面的軟體啊?

小魚 iT邦大師 1 級 ‧ 2018-06-13 23:00:10 檢舉

C# WinForm, WPF, ASP.NET(含 MVC)
VB(用C#的頭腦轉過去)
C++

神Q超人 iT邦研究生 5 級 ‧ 2018-06-14 21:13:04 檢舉

感覺好萬能哦XD

小魚 iT邦大師 1 級 ‧ 2018-06-14 23:03:47 檢舉

還好啦,
我覺得不會的還很多,
還在學習中...

神Q超人 iT邦研究生 5 級 ‧ 2018-06-15 20:06:48 檢舉

也太謙虛了!
感覺大大已經行走業界多年了XD

我要留言

立即登入留言