推 Jaka: 大師 10/21 02:51
推 JerryChungYC: 大師 10/21 02:52
推 pandix: 大師 10/21 02:56
推 amos0716: 大師 10/21 03:58
推 uglybaby: 大師 10/21 04:10
推 NTHUlagka: 大師 10/21 22:55
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 12. Integer to Roman
: 給予一個1到3999之間的整數，將這個整數轉成羅馬符號表示法
今天（昨天？）的題目感覺比較像是在考你怎麼寫得優雅
可惜我就專門寫麵條code
我一開始的作法是建四個陣列：
string _1000[] = {"", "M", "MM", "MMM"};
string _100[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string _10[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string _1[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
直接把各個位數對應到的字串列舉出來，所以例如輸入是 3412，就會是
_1000[3] + _100[4] + _10[1] + _1[2]
這個方法仔細想想好像也沒有不好，只怕會不小心打錯字而已
就程式的邏輯上來講還蠻清晰的
不過就這樣結束好像蠻無聊的
然後我想到，既然他輸入只在 [1, 3999] 之間
不知到能不能在編譯時期就建出一個大小是 4000 的陣列直接存答案
這樣應該執行速度就會超快的
第一種作法當然就是在本地算出 4000 個答案之後直接在程式碼中寫下像是
const char *ans[4000] = {
"", "I", "II", /* .... */
"MMMCMXCIX"
};
類似這種的。不過這樣程式碼會非常長，而且有點醜。
後來我想到可以用 constexpr 函式在編譯時期建出我們要的陣列
但因為我對 C++ 不是很熟，所以花了不少時間
查了一下發現好像都是要把陣列包起來，不管是在自定義的 struct
或是 std::array 之類的東西。接著再用 constexpr 的 constructor / lambda
來初始化好我們的陣列，像是：
static constexpr auto A = [] {
std::array<int, 10> ret = {};
for (int i = 0; i < 10; i++)
ret[i] = i * i;
return ret;
}();
像這樣就可以建出一個 [0, 1, 4, ..., 81] 的 std::array
不過要確定是 c++17 以後，才能在 constexpr 裡用 lambda
但有一個問題就是題目要回傳 string ，但在 constexpr 裡不能用 string
(c++20 好像可以了，但 LeetCode 還在17)，所以我改用 std::array<char, 21>
然後就照之前的方法建出一個
constexpr std::array<std::array<char, 21>, 4000> ans = /* ... */
之後要拿到答案就只要
string intToRoman(int num) {
return string(ans[num].data());
}
直接去 ans 裡拿就好了。
丟去 godbolt.org 確認一下 -O2 下生出來長怎樣
可以看到生出了超大一塊的 Solution::ans
之後的確就直接去 ans 裡拿一個 char 指標
雖然不知道轉成 string 快不快，不過我想不到更快的做法了
程式碼：
https://leetcode.com/submissions/detail/826324831/
時間： 0 ms (beats 100%)
空間： 5.8MB (beats 99.31%)
其實空間能贏 99% 蠻奇怪的吧
我多造了一個至少 4000 * 21 ~= 80KB 的陣列
不知道他是怎麼算的，很難想像其他人會用的比這個多
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666291585.A.273.html