当前位置:首页 » Project Euler » 详细页

Roman numerals 题号:89 难度: 20 中英对照

For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number.

For example, it would appear that there are at least six ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem.

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

Solution

这题的关键步骤是如何把文件中的每个罗马数字转换成最有效(即最短)的罗马数字。首先想到的是把罗马数字转换成阿拉伯数字,写成最有效的罗马数字形式之后,重新计算长度。 注意到,题目中提示“文件中所有罗马数字写法都不包含连续超过四个相同字符”。不超过四个相同字符的话就方便了,因为罗马数字的规则是不能超过三个连续字符,那么枚举出所有四个字符连用的,再转换就行。 根据罗马数字的规则: 1. 可以把I放在V和X的前面,那么就可以把IIII写成IV,VIIII写成IX 2. 可以把X放在L和C的前面,那么就可以把XXXX写成XL,LXXXX写成XC 3. 可以把C放在D和M的前面,那么就可以把CCCC写成CD,DCCCC写成CM 所以,根据以上出现的6种4个字符连用情况,每遇到上面这6个字符串时(IIII,VIIII,XXXX,LXXXX,CCCC,DCCCC),变为长度为2的串即可。因为题目没要保证转换后罗马数字的正确性,因此,可以用任意2个字符如"kk"进行替换。 在替换过程中,可以使用String.ReplaceAll方法,通过正则表达式实现字符串的替换,从而简化代码。

Code

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;

public class p089 {
	public static void main(String[] args) {
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	public static long run() {
		String path="C:\\Users\\wby\\Desktop\\p089_roman.txt";//txt文件存放的位置
        String str="";//存放txt文件中的内容
        //读取文件
        try{
        	str=new String(Files.readAllBytes(Paths.get(path)));
        } catch (Exception e) {  
            e.printStackTrace();  
        }


		 String pattern = "DCCCC|LXXXX|VIIII|CCCC|XXXX|IIII";
         String replacement = "kk"; 
         String s1=str.toString().replaceAll(pattern, replacement);
		return str.length()-s1.length();
	}
	
	
}
743
16ms