算法创作|罗马数字的转化

前言力扣（LeetCode）是一个全球挚爱的计算成长平台。问题描述罗马数字包含以下七种字符：I，V，X，L，C，D和M。字符          数值I             1V             5X             10L             50C             100D             500M             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和9X可以放在L(50)和C(100)的左边，来表示40和90。C可以放在D(500)和M(1000)的左边，来表示400和900示例1：输入：3输出："III"解释：有三个"I"加在一起示例2：输入：4输出："IV"示例3：输入：58输出："LVIII"解决方案当题目中出现了罗马数字列表，首先要想到的便是字典，因为字典中的value和key的条件关系正好可以对于罗马数字字符的转化，这里就可以得到一组字典，那么再回到题目，仔细观察可以发现，每一个罗马字符所对应的数值都是正整数而且可以被5整除(1除外),那么就可以思考，当输入一个数值过后，去把转化字符的过程中，是否可以通过整除的方式来进行转化，例如，当输入一个数值:21，自然它的罗马字符为XXI,仔细观察和思考，可以这么去思考它是被10整除得到2,2也就是两个XX，剩下的1可以被I整除得到一个I，两个互相合并，得到的XXI，这么一想，就可以得到一个结论，用数值去除以字典中能够被整除的最大数值，得到的数就是相对应的多少个罗马字符，那么此题也便迎刃而解。罗马数字的转化Python代码num=int(input())dict_hs={1000:'M',900:'CM',500:'D',400:'CD',100:'C',90:'XC',50:'L',40:'XL',10:'X',9:'IX',5:'V',4:'IV',1:'I'}res=''forkeyindict_hs:ifnum//key!=0:count=num//keyres+=dict_hs[key]*countnum-=key*countprint(res)上面代码的解题思路主要是以哈希表来进行解答，这也是绝大多数学者的解题思路，但是在力扣此题评论区的大佬却让我刮目相看，对此题又有了不同的想法，一位大佬说到用列表可以替换哈希表，大体的思路就是创建两个列表，列表内的元素与罗马字符一一对应，运用for循环遍历长度，再通过下标解决，解题思路非常奇妙。num=int(input())N=['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I']n=[1000,900,500,400,100,90,50,40,10,9,5,4,1]ans=''foriinrange(len(n)):ifnum>=n[i]:count=num//n[i]num-=n[i]*countans+=N[i]*countprint(ans)运行示例:

结语在解决此题的过程中，小编首先拿到题目自己思考，寻找自己的解决方案，同时在得到自己的解题思路后，其次便是和自己组内的队员进行深入的探讨，去讨论他们对此题的理解及其解题思路，当我们都看到罗马字符有其对应的阿拉伯数字过后，都会联想到去用哈希表解决，但我们也同时在思考有没有简便的，时间复杂度（On）小的，或者空间复杂度小的，我们尝试去创新新的解题技巧，学习新的解题思路，在此我非常感谢我的队友，同时感谢力扣能提供一个我们学习的平台。实习编辑：衡辉作者：吴合力 齐华军 黄曰标