{"id":3940,"date":"2018-09-12T20:18:07","date_gmt":"2018-09-13T03:18:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3940"},"modified":"2018-09-12T20:26:50","modified_gmt":"2018-09-13T03:26:50","slug":"leetcode-12-integer-to-roman","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-12-integer-to-roman\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 12. Integer to Roman"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Roman numerals are represented by seven different symbols:\u00a0I<\/code>,\u00a0V<\/code>,\u00a0X<\/code>,\u00a0L<\/code>,\u00a0C<\/code>,\u00a0D<\/code>\u00a0and\u00a0M<\/code>.<\/p>\n

Symbol<\/strong>       Value<\/strong>\r\nI             1\r\nV             5\r\nX             10\r\nL             50\r\nC             100\r\nD             500\r\nM             1000<\/pre>\n
For example,\u00a0two is written as\u00a0II<\/code>\u00a0in Roman numeral, just two one’s added together. Twelve is written as,\u00a0XII<\/code>, which is simply\u00a0X<\/code>\u00a0+\u00a0II<\/code>. The number twenty seven is written as\u00a0XXVII<\/code>, which is\u00a0XX<\/code>\u00a0+\u00a0V<\/code>\u00a0+\u00a0II<\/code>.<\/p>\n
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not\u00a0IIII<\/code>. Instead, the number four is written as\u00a0IV<\/code>. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as\u00a0IX<\/code>. There are six instances where subtraction is used:<\/p>\n
    \n
  • I<\/code>\u00a0can be placed before\u00a0V<\/code>\u00a0(5) and\u00a0X<\/code>\u00a0(10) to make 4 and 9.<\/li>\n
  • X<\/code>\u00a0can be placed before\u00a0L<\/code>\u00a0(50) and\u00a0C<\/code>\u00a0(100) to make 40 and 90.<\/li>\n
  • C<\/code>\u00a0can be placed before\u00a0D<\/code>\u00a0(500) and\u00a0M<\/code>\u00a0(1000) to make 400 and 900.<\/li>\n<\/ul>\n
    Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.<\/p>\n
    Example 1:<\/strong><\/p>\n
    Input:<\/strong>\u00a03\r\nOutput:<\/strong> \"III\"<\/pre>\n
    Example 2:<\/strong><\/p>\n
    Input:<\/strong>\u00a04\r\nOutput:<\/strong> \"IV\"<\/pre>\n
    Example 3:<\/strong><\/p>\n
    Input:<\/strong>\u00a09\r\nOutput:<\/strong> \"IX\"<\/pre>\n
    Example 4:<\/strong><\/p>\n
    Input:<\/strong>\u00a058\r\nOutput:<\/strong> \"LVIII\"\r\nExplanation:<\/strong> C = 100, L = 50, XXX = 30 and III = 3.\r\n<\/pre>\n
    Example 5:<\/strong><\/p>\n
    Input:<\/strong>\u00a01994\r\nOutput:<\/strong> \"MCMXCIV\"\r\nExplanation:<\/strong> M = 1000, CM = 900, XC = 90 and IV = 4.<\/pre>\n
    Solution: HashTable + Simulation<\/strong><\/h1>\n
    Map integer 1,4,5,9,10,40,50,90, …, 1000 to Romain<\/p>\n
    Start from the largest number y,<\/p>\n
    if x >= y:
    \nans += Roman[y]
    \nx -= y<\/p>\n
    Time complexity: O(x)<\/p>\n
    Space complexity: O(x)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  string intToRoman(int num) {\r\n    vector<pair<int,string>> v{{1000, \"M\"}, {900, \"CM\"}, {500, \"D\"}, {400, \"CD\"},\r\n                               { 100, \"C\"}, { 90, \"XC\"}, { 50, \"L\"}, { 40, \"XL\"}, \r\n                               {  10, \"X\"}, {  9, \"IX\"}, {  5, \"V\"}, {  4, \"IV\"}, \r\n                               {   1, \"I\"}};\r\n    string ans;\r\n    auto it = cbegin(v);\r\n    while (num) {\r\n      if (num >= it->first) {\r\n        num -= it->first;\r\n        ans += it->second;\r\n      } else {\r\n        ++it;\r\n      }\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    # Author: Huahua\r\nclass Solution:\r\n  def intToRoman(self, num):\r\n    m = [[1000, \"M\"], [900, \"CM\"], [500, \"D\"], [400, \"CD\"],\r\n         [ 100, \"C\"], [ 90, \"XC\"], [ 50, \"L\"], [ 40, \"XL\"], \r\n         [  10, \"X\"], [  9, \"IX\"], [  5, \"V\"], [  4, \"IV\"], \r\n         [   1, \"I\"]]    \r\n    index = 0\r\n    ans = ''\r\n    while num > 0:\r\n      if num >= m[index][0]:\r\n        ans += m[index][1]\r\n        num -= m[index][0]\r\n      else:\r\n        index += 1\r\n    return ans<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Roman numerals are represented by seven different symbols:\u00a0I,\u00a0V,\u00a0X,\u00a0L,\u00a0C,\u00a0D\u00a0and\u00a0M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[93,177,404,179],"class_list":["post-3940","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-conversion","tag-medium","tag-roman","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3940"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3940\/revisions"}],"predecessor-version":[{"id":3945,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3940\/revisions\/3945"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}