Lettcode_13_Roman to Integer - 로마 디지털 변환 알고리즘

본 고 는 학습 중의 총 결 입 니 다. 전재 하 는 것 을 환영 하지만 출처 를 밝 혀 주 십시오.http://blog.csdn.net/pistolove/article/details/41486885
본문 을 통 해 당신 이 배 울 수 있 는 지식 은 다음 과 같 습 니 다.
    (1) 본 문제 의 풀이 방향 을 이해 하고 앞으로 비슷 한 장면 에서 비교적 좋 은 방법 을 생각 하지 못 하면 본 고 를 사용 하 는 방법 을 고려 할 수 있다. 비록 효율 이 높 지 않 지만.
    (2) 문자열 의 캡 처 와 HashMap 관련 작업 을 배 울 수 있 습 니 다.
Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
문제 풀이 의 방향 은 다음 과 같다.
    (1) 이 문 제 는 어렵 지 않 습 니 다. switch 로 조건 판단 을 하고 반환 값 에 따라 결 과 를 누적 구 할 수 있 습 니 다.본문 은 HashMap 을 사용한다.
    (2) 로마 숫자 와 대응 하 는 정 수 를 HashMap 에 저장한다.제목 제한 조건 이 1 - 3999 이기 때문에 저장 해 야 할 로마 숫자 는 1 - 9, 10 - 100, 100 - 1000, 1000 - 3000 이 고 수량 은 사실 입 니 다.
많 지 않다.
    (3) 주어진 로마 숫자 문자열 에 대해 먼저 그 길 이 를 판단 하고 길이 가 0 이 아니라면 계속 합 니 다.그 다음 에 우 리 는 로마 숫자 에 숫자 간 에 포함 관계 가 있 음 을 발견 했다. 예 를 들 어 III 는 II 와
I. 따라서 주어진 로마 숫자 문자열 에 대해 서 는 하위 문자열 이 맵 에 대응 하 는 값 이 비어 있 는 지 판단 해 야 합 니 다.우 리 는 먼저 첫 번 째 문 자 를 캡 처 하여 맵 에 있 는 값 이 비어 있 는 지, 비어 있 지 않 으 면 계속 캡 처 합 니 다.
두 번 째 문 자 를 가 져 옵 니 다. 이 두 글자 가 Map 에서 값 이 비어 있 지 않 으 면 세 번 째 문 자 를 계속 캡 처 합 니 다. 이 세 글자 가 Map 에서 값 이 비어 있 지 않 으 면 계속 합 니 다. 캡 처 된 문자 가 Map 에서 맞 을 때 까지...
대응 하 는 값 이 비어 있 으 면 마지막 으로 추 가 된 문 자 를 맵 에 대응 하 는 값 으로 저장 합 니 다. 문자열 에 있 는 모든 문자 가 캡 처 작업 과 관련 될 때 까지 마지막 으로 얻 은 값 은 해당 하 는 정수 값 입 니 다.
알고리즘 구현 코드 는 다음 과 같 습 니 다 (PS: 본인 의 기술 에 한계 가 있 습 니 다. 아직 효율 적 인 알고리즘 을 쓸 수 없습니다. 좋 은 알고리즘 이 있 으 면 공유 하 시기 바 랍 니 다. 감사합니다)

public int romanToInt(String s) {
	Map<String, Integer> maps = new HashMap<String, Integer>();
	maps.put("I", 1);
	maps.put("II", 2);
	maps.put("III", 3);
	maps.put("IV", 4);
	maps.put("V", 5);
	maps.put("VI", 6);
	maps.put("VII", 7);
	maps.put("VIII", 8);
	maps.put("IX", 9);
	maps.put("X", 10);
	maps.put("XX", 20);
	maps.put("XXX", 30);
	maps.put("XL", 40);
	maps.put("L", 50);
	maps.put("LX", 60);
	maps.put("LXX", 70);
	maps.put("LXXX", 80);
	maps.put("XC", 90);
	maps.put("C", 100);
	maps.put("CC", 200);
	maps.put("CCC", 300);
	maps.put("CD", 400);
	maps.put("D", 500);
	maps.put("DC", 600);
	maps.put("DCC", 700);
	maps.put("DCCC", 800);
	maps.put("CM", 900);
	maps.put("M", 1000);
	maps.put("MM", 2000);
	maps.put("MMM", 3000);

	if (s.length() == 0)
		return -1;
	int count = 0;
	int flag = 0;
	for (int i = 0; i < s.length(); i++) {
		while (flag < s.length()
				&& maps.get(s.substring(i, flag + 1)) != null) {
			flag++;
		}
		count = count + maps.get(s.substring(i, flag));
		i = flag - 1;
	}
	return count;
}