在上一期[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
[DLdigest-3] Python中让你无法预测的“是”
动态层归一化(Dynamic Layer Normalization)
详述DeepMind wavenet原理及其TensorFlow实现
Layer Normalization原理及其TensorFlow实现
Batch Normalization原理及其TensorFlow实现
Maxout Network原理及其TensorFlow实现
Network-in-Network原理及其TensorFlow实现
如何基于TensorFlow实现ResNet和HighwayNet
深度学习每日摘要|坚持技术,追求原创