leecode笔记-day03(算法12,13)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leecode笔记-day03(算法12,13)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2001字，纯文字阅读大概需要3分钟。

内容图文

1.算法12 整数转罗马数字

我自己的解法：

要做这一题首先得理解罗马数字的排列规则，看字符-数值的对照表其实很容易明白，总结起来就一句话“不够就向下取一个”。比如1934这个数字。 >=1000,那么取一个M，1934-1000 = 934 > 500 且 < 1000，不够一个M，那么取一个D，934-500 = 434.....最后我们得到MDCCCCXXXIIII，显然太长了不方便书写，我们把像DDDD,IIII这种四个并列的进行整合，但是这只是处理的数字4的情况，对于数字9，我们同样能发现规律：它们像“汉堡包”。

于是步骤就很明显了
1.我们需要先把1934转成MDCCCCXXXIIII，依赖字符-数值的对照表即可（可能需要用Map保存这张表。）
2.第一遍检查：把像DDDD,IIII这种四个并列的进行整合。
3.第二遍检查：把像DCD这种“汉堡包”进行整合。（这其实是在处理数字9的情况）

代码是可以实现的，但是这等于把一道题分成了三道题来解，代码太长，没脸展示。首先理解罗马数字的排列规律即可。

官方解法

接下来是官方解法，我尽量简单解释思路：
1.贪心：
回到题目，首先我们发现，罗马数字的规则：
规则一：是字符-数值表，如果只有这个那么问题十分简单。
规则二：但是还有4和9数字的特殊处理，因此显得比较头疼。
但是，二者结合发现一个关键点：可能性是有限、且数量不算特别多的。
将规则二结合到规则一，我们能得到一张更确切的表：

注意，还是那句话：“不够就向下取一个”，我们肯定是从1000,900,500....这样的顺序，从大到小分解我们的数字，那么第一层for循环肯定是遍历1000,900,500....，不够时就取下一个更小的数。这样，任何普通数字都能转化成罗马数字。

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};    
String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

public String intToRoman(int num) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < values.length && num >= 0; i++) {
        while (values[i] <= num) {
            num -= values[i];
            sb.append(symbols[i]);
        }
    }
    return sb.toString();
}

能学到什么？

我并不关心罗马数字到底是怎样。刷leecode并不是为了做各种脑筋急转弯，而是希望初步认识一些算法，锻炼我用计算机的思维方式想问题，并且写出更高效、更好的代码。

1.关于贪心算法：贪心是指一旦找到合适的解，就立刻输出，不追求找到最优解，或者说，明确知道找到的第一个解肯定是最优解/唯一解，那么这就符合“贪心”的场景。

内容总结

以上是互联网集市为您收集整理的leecode笔记-day03(算法12,13)全部内容，希望文章能够帮你解决leecode笔记-day03(算法12,13)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---