专栏首页小浩算法漫画:臭长臭长的高频贪心面试题

漫画:臭长臭长的高频贪心面试题

今天是小浩算法 “365刷题计划” 第90天 。穿插为大家讲解一道臭长臭长的经典题目。我把字体加大了,加大了,加大了。

01

PART

Integer to Roman

本题是leetcode第12题,意为整数转罗马数字,题目难度中等,代码通过九万次,建议掌握。

第12题:罗马数字包含以下七种字符: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:

输入: 3

输出: "III"

示例 2:

输入: 4

输出: "IV"

示例 3:

输入: 9

输出: "IX"

示例 4:

输入: 58

输出: "LVIII"

解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994

输出: "MCMXCIV"

解释: M = 1000, CM = 900, XC = 90, IV = 4.

02

PART

题解分析

看见长长的题目,别怂。

因为题目很长,所以读懂题意很重要。这道题说是让我们转换罗马数字,其实说白了就是让我们用特殊的规则凑数。罗马数字本身就可以理解为一种特殊的数学规则。

那如何来凑数?自然就需要读懂题意,比如 2 就是通过 1+1 凑;3 通过 1+1+1 凑;6 通过 5+1 凑。同时,在凑的过程中,又加入了一些奇怪的规则。比如说,4 不允许 1+1+1+1 凑,而是得 5-1 凑;而 9 不能 5+1+1+1+1 凑,而是得 10-1 凑;这个分析怎么出来的?题目中说的:

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

看到这里,估计熟悉的小伙伴,能找到那么点感觉。凑数,凑数,凑钱。有一道很经典的题目 “硬币找零” 不也是一样的玩法吗。

然后,我们把题目中所有的字符列出来:

当然,除了这些还不够。因为上面我们还分析出了一些特殊的规则,也得列出来:

然后我们利用这张表格,对给出的数字进行转化(拼凑)。假设我们要找的数为2834,大概的流程如下(其实是一种类似贪心的思想):

对比着代码看更为明朗:

//java
class Solution {
    public String intToRoman(int num) {
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int index = 0;
        StringBuilder result = new StringBuilder();
        while (index < 13) {
            if (num >= nums[index]) {
                result.append(romans[index]);
                num -= nums[index];
            } else {
                index ++;
            }
        }
        return result.toString();
    }
}

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

啰嗦一下

这道题目限制了最大数为 3999,时间复杂度也就被限制成了O(1)。

我还看到了一个西PP很骚的解法,拿出来大家瞅瞅:

//cpp
class Solution {
public:
    string intToRoman(int num)
    {
        char* c[4][10] = {
            {"","I","II","III","IV","V","VI","VII","VIII","IX"},
            {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},
            {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
            {"","M","MM","MMM"}
        };
        string roman;
        roman.append(c[3][num / 1000]);
        roman.append(c[2][num / 100 % 10]);
        roman.append(c[1][num / 10 % 10]);
        roman.append(c[0][num % 10]);

        return roman;
    }
};

这个解法应该没什么解释的,就是把每一位 0-10 的情况枚举出来。这道题目稍微长了点,但是分析下来并没有什么难度。有的同学一看到题目很长,直接就怂了,这种其实就很不好。唔,再放一张女神照片:

今天的题目到这里就结束了。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

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

原始发表时间:2020-04-28

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:脑筋急转弯题目(尼姆问题求解)

    你和你的朋友,两个人一起玩 Nim 游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

    程序员小浩
  • 漫画:六九式是一道简单有趣的算法题(开车...)

    今天是小浩算法 “365刷题计划” 第94天 。69式是一种。。。咳咳,六九问题是一道很有趣的算法题。嗯,不服来辩。

    程序员小浩
  • 面试超级爱问的全排列!!!

    假如我们不是做算法题,而是做数学题。我们会一个位置一个位置的来考虑,先写出以1开头的排列,再写出以2开头的排列,最后写出以3开头的排列。

    程序员小浩
  • RS Meet DL(59)-FM家族的新朋友FAT-DeepFFM

    今天给大家介绍的文章标题是:《FAT-DeepFFM: Field Attentive Deep Field-aware Factorization Machi...

    石晓文
  • SpringMVC注解完全解析(下)

    尽管SpringMVC的注解注入十分强大,但在实际的开发过程中难免会用到Servlet的原生API。而实际上,SpringMVC可以在目标方法的参数中传入很多类...

    wangweijun
  • 【前端笔试系列】:0x02

    WEBJ2EE
  • 使用 RMI + ZooKeeper 实现远程调用框架

    在 Java 世界里,有一种技术可以实现“跨虚拟机”的调用,它就是 RMI(Remote Method Invocation,远程方法调用)。例如,服务A 在 ...

    哲洛不闹
  • JS-Date对象

    xing.org1^
  • 原型图+交互设计+UI图,到底啥关系

    其实一直以来都纳闷,产品经理要做原型图,然后UI设计师要画UI 图,这两个之间貌似有许多重复的地方,而且还是大多时候还是并行进行,实在不知道二者之间的关系是什么...

    公众号php_pachong
  • NLP之——Word2Vec详解

    2013年,Google开源了一款用于词向量计算的工具——word2vec,引起了工业界和学术界的关注。首先,word2vec可以在百万数量级的词典和上亿的数据...

    郭耀华

扫码关注云+社区

领取腾讯云代金券