文档章节

整数转换为罗马数字 Integer to Roman

叶枫啦啦
 叶枫啦啦
发布于 2017/08/25 19:09
字数 678
阅读 14
收藏 0

问题:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

解决:

【注】

基本字符

I

V

X

L

C

D

M

相应的阿拉伯数字表示为

1

5

10

50

100

500

1000

例如整数 1437 的罗马数字为 MCDXXXVII, 我们不难发现,千位,百位,十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字,然后分别表示出来:
【罗马数字】
1~9: {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
10~90: {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
100~900: {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
1000~3000: {"M", "MM", "MMM"}.

设数字与罗马数字之间的对应关系:roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
以100~900为例,我们可以分为四类:100到300一类res += roman[n],400一类res += roman[n]+roman[n-1],500到800一类res += roman[n - 1] + roman[n],900最后一类res+=roman[n] + roman[n-2]。每一位上的情况都是类似的,代码如下:

① 使用代码实现转换。

class Solution { //91ms
    public static String intToRoman(int num) {
        String res = "";
        char[] roman = {'M','D','C','L','X','V','I'};
        int[] value = {1000,500,100,50,10,5,1};
        for (int i = 0;i < 7;i += 2){//遍历roman数组
            int val = num / value[i];
            if (val < 4){
                for (int j = 1;j <= val;j ++){
                    res = res + roman[i];
                }
            }else if(val == 4){
                res = res + roman[i] + roman[i - 1];
            }else if (val > 4 && val < 9){
                res = res + roman[i - 1];
                for (int j = 6;j <= val;j ++){
                    res += roman[i];
                }
            }else if (val == 9){
                res = res + roman[i] + roman[i - 2];//若使用res += res + roman[i] + roman[i - 2]结果为161,变为了整数相加
            }
            num %= value[i];
        }
        return res;
    }
}

② 本题由于限制了输入数字范围这一特殊性,故而还有一种利用贪心算法的解法,建立一个数表,每次通过查表找出当前最大的数,减去再继续查表。

public class Solution { //93ms
    private static final String[] ROMAN = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    private static final int[] INTEGERS = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        while (num > 0) {
            while (num >= INTEGERS[index]) {
                sb.append(ROMAN[index]);
                num -= INTEGERS[index];
            }
            index ++;
        }
        return sb.toString();
    }
}

③一种讨巧的做法,将所有的可能都列出来。

public class Solution {//95ms
    public String intToRoman(int num) {
        String M[] = {"", "M", "MM", "MMM"};
        String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode:Integer to Roman - 阿拉伯数字到罗马数字的转换

1、题目名称 Integer to Roman (阿拉伯数字到罗马数字的转换) 2、题目地址 https://leetcode.com/problems/integer-to-roman 3、题目内容 英文:Given an integer, convert it to a roman...

北风其凉
2015/08/02
2.5K
0
LeetCode:Roman to Integer - 罗马数字到阿拉伯数字的转换

1、题目名称 Roman to Integer (罗马数字到阿拉伯数字的转换) 2、题目地址 https://leetcode.com/problems/roman-to-integer/ 3、题目内容 英文:Given a roman numeral, convert it to an...

北风其凉
2015/08/04
1K
0
罗马数字转成整数

原题   Given a roman numeral, convert it to an integer.   Input is guaranteed to be within the range from 1 to 3999. 题目大意   给定一个罗马数字,将其转换成对应的整数。  ...

一贱书生
2016/12/12
4
0
Leetcode PHP题解--D82 13. Roman to Integer

D82 13. Roman to Integer 题目链接 13. Roman to Integer 题目分析 将给定的罗马数字转换成阿拉伯数字。 思路 用替换法。 要注意,先替换连续出现的那些。例如,比先替换,要先替换。 最终代...

skys215
06/08
9
0
Leetcode#13. Roman to Integer(罗马数字转整数)

题目描述 罗马数字包含以下七种字符:I, V, X, L,C,D 和 M。 例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情...

武培轩
2018/09/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

视频如何加水印?

很多视频制作者的视频都被他人盗用过,为了防止自己的劳动成果被他人窃取,给视频加水印对于视频制作者来说,是一件非常重要的事情。那么下面分享一个手机给视频加水印的方法,一起来看看吧!...

白米稀饭2019
39分钟前
5
0
004-Envelop-基于Blockstack的文件传输dapp

本篇文章主要介绍基于Blockstack的文件传输工具; ####A-链接地址 官网地址:https://envelop.app/ Github地址:https://github.com/envelop-app ####B-特性: 1: Share private files easil...

Riverzhou
41分钟前
9
0
SpringCloud——声明式调用Feign

Feign声明式调用 一、Feign简介 使用Ribbon和RestTemplate消费服务的时候,有一个最麻烦的点在于,每次都要拼接URL,组织参数,所以有了Feign声明式调用,Feign的首要目标是将Java HTTP客户端...

devils_os
47分钟前
9
0
《JAVA核心知识》学习笔记 (22. 数据结构)

22.1.1. 栈(stack) 栈( stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶 (top)。它是后进先出(LIFO)的。对栈的基本操作只有 push(进栈)和 pop(出栈...

Shingfi
52分钟前
8
0
你对AJAX认知有多少(1)?

AJAX(一) AJAX技术对于前段或者后端工程师来说,都是必不可缺的 那我们这几期都来细细品味一下AJAX的相关知识,直接上干货喽~ 1、什么是AJAX,为什么要使用Ajax(请谈一下你对Ajax的认识) 什么...

理性思考
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部