[DLdigest-14] 罗马的转世

2017 年 11 月 29 日 深度学习每日摘要 DLdigest

罗马的转世

在上一期[DLdigest-13] 每日一道算法Integer to Roman中，算法题目是要将罗马数字转换成整数，这与我们上一期中解答的将整数转换成罗马数字是一个相反的过程，关于罗马数字的具体规则，这一期就不再重复说明了，需要了解的朋友可以查看[DLdigest-13] 每日一道算法Integer to Roman进行详细了解。

其实这道题比起将整数转化成罗马字符要简单很多，我解决这道题的思路是遍历罗马字符串，对相邻的罗马字符的“大小”进行比较，首先我们把所有罗马字符存在romans字符串中，即romans="IVXLCDM"，把每个字符对应的整数存在一个整数数组a中，即a={1, 5, 10, 50, 100, 500, 1000}，定义初始求和值result为0，根据左减右加的规则，如果左边的字符在romans的索引小于右边字符在romans的索引，那么就把result减去左边字符对应的整数得到新的result，反之，则把result加上左边字符对应的整数得到新的result，注意，遍历之后还要把result加上最后一个字符对应的整数，最终的result就是该罗马字符串对应的整数。

为了与上一期中将整数转换成罗马数字形成呼应，这里我用的测试样本与上一期中完全对应，代码以及运行结果如下。

#include<iostream>
using namespace std;

class Solution {
public:    
    int romanToInt(string s) {        
        /*         'I': 1         'V': 5         'X': 10         'L': 50         'C': 100         'D': 500         'M': 1000        */
        string romans="IVXLCDM";
        int a[]={1, 5, 10, 50, 100, 500, 1000};
        if(s.size()==1)
            return a[romans.find(s[0])];
        char prev=' ';
        int result=0;
        int index_p, index_c;
        for(char& ch: s) {
            if(prev!=' ') {
                index_p=romans.find(prev);
                index_c=romans.find(ch);
                if(index_p<index_c)
                    result-=a[index_p];
                else
                    result+=a[index_p];
            }
            prev = ch;
        }
        result+=a[index_c];
        return result; 
    }
};
        
int main()
{
    Solution s;
    string s1="I";
    string s2="IV";
    string s3="IX";
    string s4="LXXXV";
    string s5="DXLI";
    string s6="MDXLI";
    cout<<"Int of "<<s1<<" is "<<s.romanToInt(s1)<<endl;
    cout<<"Int of "<<s2<<" is "<<s.romanToInt(s2)<<endl;
    cout<<"Int of "<<s3<<" is "<<s.romanToInt(s3)<<endl;
    cout<<"Int of "<<s4<<" is "<<s.romanToInt(s4)<<endl;
    cout<<"Int of "<<s5<<" is "<<s.romanToInt(s5)<<endl;
    cout<<"Int of "<<s6<<" is "<<s.romanToInt(s6)<<endl;
    return 0;
}

程序运行结果:
Int of I is 1
Int of IV is 4
Int of IX is 9
Int of LXXXV is 85
Int of DXLI is 541
Int of MDXLI is 1541

每日一道算法——Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.

近期将以NLP领域语音合成、机器阅读理解的论文分享以及代码实践为主，每天一道算法专栏会继续保持更新。欢迎大家留言分享深度学习知识或交流每日一道算法的思路，本期算法的解决方法将在下一期中讲解。另外，我们的机器学习与量化投资学习社区已经开通，欢迎阅读《技术交流社区已上线》进入社区交流讨论。

题图：Celebrating the 100th anniversary of the birth of Kim Il-sung

你可能会感兴趣的文章有：

[DLdigest-13] 每日一道算法Integer to Roman

[DLdigest-12] 每日一道算法Container With Most Water