专栏首页石璞东 | haha数据结构与算法 -2 :罗马数字与整数的相互转换

数据结构与算法 -2 :罗马数字与整数的相互转换

【Leetcode】题目描述

罗马数字包含以下七种字符: 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。这个特殊的规则只适用于以下三种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例:

  • 整数转罗马数字[1]
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
  • 罗马数字转整数[2]
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

说下规则

四个规则:

  1. 相同的数字连写, 所表示的数等于这些数字相加得到的数。如 XXX表示 30
  2. 小的数字在大的数字的右边, 所表示的数等于这些数字相加得到的数 如VIII 表示8
  3. 小的数字(限于I, X, C)在大的数字的左边, 所表示的数等于大数减去小的数:如IV 表示4
  4. 在一个数的上面画一条横线, 表示这个数增值1000倍(由于题目只考虑4000以内的数,所以这条规则不用考虑。)

五个组数规则:

  1. I, X, C:最多只能连用3个, 如果放在大数的左边,只能用1个
  2. V, L, D: 不能放在大数的左边,只能使用一个
  3. I 只能用在V和X的左边。IV表示4, IX表示9
  4. X只能放在L,C左边。XL 表示40, XC表示90
  5. C只能用在D,M左边。CD 表示400, CM表示900

解题思路

  • 整数转罗马数字[1]

此种题目较为复杂,因为不知道大数在左边还是右边,所以存在两种情况,需要判断一下:

  • 小的数在左边,大的数字在右边(例:IV,参照上述6种特殊情况)
  • 小的数在右边,大的数字在左边(例:VI表示6,即所有数字相加之和)

  • 罗马数字转整数[2]

通过组合数字来拆分,使程序能够实现连加的方法。举个栗子:给定一个已知数字,假设为10,然后再给定一组数字(即数组[15,8,4,2,1]),组合数字的意思就是:使用当前所给值10与所给数组中所有元素进行比较,找出第一个小于或等于所给当前值10的数组元素,即8,然后从所给已知值中减去该值,用余数与数组中的下一个元素继续进行比较,同理找到小于或者等于该余数的值,然后继续循环往复,直到找不到满足该条件(当前余数不小于等于数组元素的时候)时,给定数字即为所有被减掉的数字之和。

画个图更简单:

图1.1 图解转换过程

代码展示

  • 整数转罗马数字[1]
class Solution {
  public:
      int romanToInt(string s) {
          int tagVal[256];
          tagVal['I']=1;
          tagVal['V']=5;
          tagVal['X']=10;
          tagVal['L']=50;
          tagVal['C']=100;
          tagVal['D']=500;
          tagVal['M']=1000;
          int val=0;
          for(int i=0;i<s.length();i++){
              if(i+1>=s.length()||tagVal[s[i+1]]<=tagVal[s[i]]){
                  val += tagVal[s[i]];
              }else{
                  val -= tagVal[s[i]];
              }
          }
          return val;
      }
  };
  • 罗马数字转整数[2]
class Solution {
  public:
      string intToRoman(int num) {
          if(num<=0) return "";
          string ret = "";
          static int number[13]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
          static string flags[13]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
          for (int i=0;i<13&&num>0;i++){
              if (num<number[i]) continue;
              while(num>=number[i]){
                  num -= number[i];
                  ret += flags[i];
              }
          }
          return ret;
      }
  };

本文总结

在本文中,我们实际上讲解了Leetcode上的两个题目(即整数转罗马数字[1]罗马数字转整数[2]),我们给出了本题详细的解题思路,并通过一个简单的图示对其做了更为透彻清晰的说明,在最后我们通过C++对这两个题目进行了代码实现,小伙伴们学会了吗?快去实现一下吧!

参考资料

[1]

【Leetcode】整数转罗马数字: https://leetcode-cn.com/problems/integer-to-roman/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china

[2]

【Leetcode】罗马数字转整数: https://leetcode-cn.com/problems/roman-to-integer/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china

本文分享自微信公众号 - hahaCoder(hahaCoder),作者:石璞东

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【玩转腾讯云】个人网站搭建详解

    在这个互联网时代,人人都谈网络,杂家也不能落后不是,就在这时,小编又适时的出来教你装逼了,今天我们来唠一唠如何拥有一个属于自己的网站,网站上线运行前期操作流程是...

    石璞东
  • TensorFlow 2.0 概述

    在本文中将介绍与我的毕设论文演示案例相关的TensorFlow的一些基础知识,包括张量、计算图、操作、数据类型和维度以及模型的保存,接着在第二部分,本文将介绍演...

    石璞东
  • POWER BI系统使用之数据集构建器

    昨天周六,下午回学校有种是周日的错觉,以至于觉得今天是多出来的休息日,开心~hahaha~ 今天要写的内容是临时想到的,原计划写的文我就不立f...

    石璞东
  • Python小技巧:3个处理文件路径的简单方法

    如果希望你的Python代码能够同时在Windows和Mac/Linux上运行,你需要解决这类平台的特定问题。幸运的是,Python3的新模块pathlib可以...

    加米谷大数据
  • 18.1.29日报

    1,修复http://sandbox.runjs.cn/show/pcohsrh0绘制的时候,tile边界有一像素多余线条的...

    龙泉寺扫地僧
  • 可视化队列管理工具 Laravel Horizon 来了

    overtrue
  • Python3网络爬虫实战-7、APP爬

    MitmProxy 是一个支持 HTTP 和 HTTPS 的抓包程序,类似 Fiddler、Charles 的功能,只不过它是一个控制台的形式操作。 同时 Mi...

    py3study
  • 视频 | NIPS 2017线上分享第二期:利用价值网络改进神经机器翻译

    在 NIPS 2017 大会正式开始前,机器之心将选出数篇优质论文,邀请论文作者来做线上分享,聊聊理论、技术和研究方法。上周,我们进行了线上分享的第二期,邀请到...

    机器之心
  • iOS中UITableViewController自带的刷新控件

            在iOS开发中,使用tableView的界面,大多会用到一个下拉刷新的的控件,第三方库中,我们一般会选择比较好用的MJRefresh,其实,在i...

    珲少
  • Android 黑科技保活实现原理揭秘

    一直以来,App 进程保活都是各大厂商,特别是头部应用开发商永恒的追求。毕竟App 进程死了,就什么也干不了了;一旦 App 进程死亡,那就再也无法在用户的手机...

    weishu

扫码关注云+社区

领取腾讯云代金券