20181208

Overview:

Algorithm: 整数转罗马数字

题目

罗马数字包含以下七种字符：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.

思路

题目本身并不难，只需要将给定的数字中找出可以转换的最大值，然后减去这个值，继续循环即可。但对特别边界条件需要考虑一下。但因为限制了输入的范围为 1~3999，因此不用考虑超过 4000 的情况，同时也限定需要考虑的特殊情况只有 6 种。可将整数和对应罗马数字字符串的关系统一考虑，查表即可。

测试用例及代码实现

Review: How to understand your program's memory

这篇文章从整体角度描述了一个进程的内存布局，尤其是堆和栈。并分析了堆栈的相关原理及可能出现的问题，最后给出了这些问题的解决办法。总体上比较简单，我做一下大体翻译：

作为一个 C/C++ 程序员，是需要和内存直接打交道的。经常会出现的错误就是 segfaults。就是访问一个已经被释放的内存，这块内存已经被你通过 free 释放掉了，或者被系统自动释放了，比如栈。

理解这些问题特别简单，而且也能帮你写出更好的程序。

内存是如何分布的?

内存被分为多个段，其中最重要的两个就是堆和栈。栈是线性读写的，而堆是随机的。

栈上保存了寄存器信息、函数调用信息、变量分配信息等。并且栈内存是由程序管理而非程序员。而堆通常被用来分配一块大内存来存放那些根据程序员意愿存在与否的数据，也就是说，控制堆内存的用法是程序员自己的事情。我们也称堆为动态内存。你可以使用 malloc 来分配内存，并且使用 free 释放。

理解栈

每个本地变量、函数调用都被存放到栈上。基于此，你可以做很多事情--大多数都是你不希望发生的--比如缓冲溢出和访问错误内存。

所以，栈是怎么工作的？

栈是一个先进后出的数据结构。你可以将其理解为一个装书的箱子--最先拿出来的书只能是最后装进去的。通过这种数据结构，程序可以很容易地使用 push 和 pop 管理自己的所有操作。这两个操作是相反的，push 操作插入数据到栈顶，而 pop从栈顶弹出数据；

为了记录当下的内存位置，有一个特殊的寄存器叫栈顶指针寄存器（Stack Pointer）。你需要保存数据时，向上移动栈顶指针寄存器并 push 数据，需要退出函数时，向下移动栈顶指针寄存器即可，很简单！

理解堆

和栈相反，当您希望某些东西存在一段时间而不依赖于函数和作用域时，就需要使用到堆。C 语言库 stdlib 提供了两个函数：malloc 和 free。malloc 向操作系统请求一块空间，并返回起始地址的指针。free 告诉系统我们请求的内存不再使用了，可以释放以供其他任务使用。

但随之而来的问题是：内存泄漏！

内存泄漏是我们申请了一块内存，在没有指针指向它之前，这块内存还没有被释放。这导致程序使用了过多的内存，超出了总共的可用内存。为了避免内存泄漏，每次我们不再需要堆内存的时候，记得释放它。

对堆内存的管理是必要的。但也需要注意如何使用。像栈一样，堆内存释放后也就不能再访问了。

结构体和堆

使用结构体时通常犯的一个错误是释放结构体。如果在结构体内分配了堆上的内存，我们需要首先释放，然后再释放实际的结构体。

我是如何解决内存泄漏问题的

我用 C 语言的大多数时候都在使用结构体。因此我总是强制使用两个函数：构造函数和析构函数来避免内存泄漏的问题。即在构造函数中申请空间，并在析构函数中释放空间，很容易解决了这个问题。

ARTS project is a learning project initiated by Hao Chen. A means learning a Algorithm on LeetCode,R means Reviewing an English article about programer,T means learning a Technique skill,and S means doing a Share with others that influence people. Adhere to every week at least one year!

This article was posted on my blog and Github using the MIT Open Source License.