Jamzen的技术博客
0%

LeetCode.整数转罗马数字

发表于 分类于 Valine：

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符:数值 -> I:1, V:5, X:10, L:50, C:100, D:500, M:1000
例如,罗马数字2写做II,即为两个并列的1。12写做XII,即为X+II。27写做XXVII, 即为XX+V+II.通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，

而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：

  1. I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  2. X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
  3. C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
  4. 给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
  • 示例 1:输入3，输出”III”
  • 示例 2:输入4，输出”IV”
  • 示例 3:输入9，输出”IX”
  • 示例 4:输入58，输出”LVIII”
  • 示例 5:输入1994，输出”MCMXCIV”

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
object RomaToNum {
     def main(args: Array[String]): Unit = {
          println(solution1(3))
          println(solution1(4))
          println(solution1(9))
          println(solution1(58))
          println(solution1(1994))

          println(solution2(3))
          println(solution2(4))
          println(solution2(9))
          println(solution2(58))
          println(solution2(1994))
     }

     /**
      * 按位提取数字转为罗马数字
      */
     def solution1(num: Int): String = {
          val map = Map(1 -> "I", 4 -> "IV", 5 -> "V", 9 -> "IX", 10 -> "X", 50 -> "L", 40 -> "XL", 90 -> "XC", 100 -> "C", 400 -> "CD", 500 -> "D", 900 -> "CM", 1000 -> "M")
          var res = ""
          if (num < 1 || num > 3999) {
               return null
          }

          var numT = num
          var i = 0
          while (numT != 0) {
               val bit = numT % 10
               if (bit != 0) {
                    val factor = Math.pow(10, i).toInt
                    val target = bit * factor
                    val base = map.get(factor).get
                    val transTarget = bit match {
                         case 1 => base
                         case 2 => base + base
                         case 3 => base + base + base
                         case 4 => map.get(target).get
                         case 5 => map.get(target).get
                         case 6 => map.get(factor * 5).get + base
                         case 7 => map.get(factor * 5).get + base + base
                         case 8 => map.get(factor * 5).get + base + base + base
                         case 9 => map.get(target).get
                    }
                    res = transTarget + res
               }
               i += 1
               numT = numT / 10
          }
          res
     }

     /**
      * 直接按位转换
      */
     def solution2(num: Int): String = {
          val first = List("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")
          val second = List("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
          val third = List("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
          val fourth = List("", "M", "MM", "MMM")

          fourth(num / 1000) + third((num / 100) % 10) + second((num / 10) % 10) + first(num % 10)
     }

}