“Roman to Integer”문제에서 우리는 현 일부 양의 정수를 나타내는 로마 숫자 형식. 로마 숫자는 다음 표를 사용하여 정수로 변환 할 수있는 7 자로 표시됩니다.
주의 사항: 주어진 로마 숫자의 정수 값은 값 4000을 초과하거나 같지 않습니다.
차례
예
IX
9
CXXIX
129
설명 # 1
IX는 정수로 9입니다.
설명 # 2
CXXIX = C + XX + IX = 100 + 20 + 9 = 129
접근 (왼쪽에서 오른쪽으로 통과)
배열에서 왼쪽에서 오른쪽으로 전달하고 배열의 모든 문자에 대해 해당 값을 계속 추가 할 수 있습니다. 그러나 로마 숫자의 특이한 점은 정수 값이 작은 문자가 높은 값보다 먼저 발생하면 그 결과가 구별되는 합이 아니라는 것입니다.
예를 들어 로마자의 IX는 이후에 문자를 추가 한 경우 1 + 10 = 11과 같아야합니다. 그러나, IX = 9, I 그 전에 발생하는 X 적분 값이 적습니다. 따라서 결과는 다음과 같이 처리됩니다. I 에서 빼다 X. 따라서 IX = 9.
따라서 단순히 문자열에있는 모든 문자의 정수 값을 더할 수는 없습니다. 위에서 언급 한 경우 옆에있는 문자도 확인해야합니다. 이런 식으로 주어진 로마 숫자 문자열을 필요한 정수로 변환 할 수 있습니다.
암호알고리즘
- 함수 만들기 getInteger () 다음을 사용하여 전달 된 단일 로마 문자의 값을 반환하려면 스위치 가지 경우
- 초기화 결과 필요한 정수 저장
- 다시 초기화 현재 및 다음 것 반복 할 때마다 각 문자의 현재 및 다음 정수 값을 문자열에 저장합니다.
- i = 0에 대해 반복 나는 <N (N = 배열의 크기)
- If i 배열의 마지막 인덱스이므로 다음 문자가 없으므로 다음의 정수 값을 추가하십시오. 문자열 [i] 반환 결과
- 다음을 사용하여 현재 및 다음 문자의 정수 값을 검색합니다. getInteger ()
- If 현재 <= 다음
- 추가 현재 ~로 결과
- 증가 i 1 씩, 즉, i++
- 다른
- 추가 다음 것 - 현재 ~로 결과
- 증가 i 2, 즉, i + = 2
- 결과 인쇄
Roman to Integer Leetcode 솔루션 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int getInteger(char c)
{
switch(c)
{
case 'I' : return 1;
case 'V' : return 5;
case 'X' : return 10;
case 'L' : return 50;
case 'C' : return 100;
case 'D' : return 500;
case 'M' : return 1000;
default : return -1;
}
}
int romanToInt(string s)
{
int n = s.size() , result = 0 , current , next , i = 0;
while(i < n)
{
if(i == n - 1)
{
result += getInteger(s[i]);
return result;
}
current = getInteger(s[i]) , next = getInteger(s[i + 1]);
if(current >= next)
result += current , i++;
else
result += next - current , i += 2;
}
return result;
}
int main()
{
string s = "CXXIX";
cout << romanToInt(s) << '\n';
return 0;
}
자바 프로그램
class roman_to_int
{
public static void main(String args[])
{
String s = "CXXIX";
System.out.println(romanToInt(s));
}
static int getInteger(char c)
{
switch(c)
{
case 'I' : return 1;
case 'V' : return 5;
case 'X' : return 10;
case 'L' : return 50;
case 'C' : return 100;
case 'D' : return 500;
case 'M' : return 1000;
default : return -1;
}
}
static int romanToInt(String s)
{
int n = s.length() , result = 0 , current , next , i = 0;
while(i < n)
{
if(i == n - 1)
{
result += getInteger(s.charAt(i));
return result;
}
current = getInteger(s.charAt(i));
next = getInteger(s.charAt(i + 1));
if(current >= next)
{
result += current;
i++;
}
else
{
result += next - current;
i += 2;
}
}
return result;
}
}
129
Roman to Integer Leetcode 솔루션의 복잡성 분석
시간 복잡성
여기서 우리는 문자열을 한 번 횡단합니다. 4000 미만의 정수 제한이 있으므로 문자열 크기는 항상 상수 값입니다. 따라서 시간 복잡도는 O (1).
공간 복잡성
O (1), 우리는 일정한 메모리 공간 만 사용합니다.
접근 (오른쪽에서 왼쪽 패스)
오른쪽에서 왼쪽과 왼쪽에서 오른쪽의 차이점은 구현에 있습니다. Right-to-Left 패스에서는 배열의 두 번째 마지막 인덱스부터 시작하여 마지막 문자의 정수 값을 일부 변수에 저장할 수 있습니다. 결과에 대한 마지막 문자의 정수 값을 미리 유지합니다. 이제 오른쪽에서 왼쪽으로 이동하면서 현재 문자의 정수 값이 우리가 본 마지막 (이전 / 오른쪽) 요소보다 작은 지 모든 단계에서 확인합니다. 마지막 값보다 작 으면 결과에서이 값을 뺍니다. 그렇지 않으면 결과에 추가합니다. 이 구현은 더 큰 가치를 지닌 캐릭터 앞에 더 작은 가치를 지닌 캐릭터가 후자의 캐릭터에서 빼야한다는 것을 의미한다는 위의 사실에 전적으로 기반합니다.
이 접근 방식은 이전 접근 방식과 작업 수가 거의 동일하지만 반복 할 때마다 마지막 요소를 확인하지 않아도되므로 더 편리합니다.
암호알고리즘
- 함수 만들기 getInteger () 위와 유사
- 문자열의 마지막 문자의 정수 값을 이전
- 초기화 결과 동일 이전
- 에서 반복 나는 = N – 2 까지 나는> = 0 :
- 현재 문자의 정수 값을 다음과 같이 저장 현재
- If 현재 ~보다 작다. 이전
- 덜다 현재 에 결과즉, 결과 -= 현재
- 다른
- 추가 현재 에 결과즉, 결과 += 현재
- 결과 인쇄
Roman to Integer Leetcode 솔루션 구현
C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
int getInteger(char c)
{
switch(c)
{
case 'I' : return 1;
case 'V' : return 5;
case 'X' : return 10;
case 'L' : return 50;
case 'C' : return 100;
case 'D' : return 500;
case 'M' : return 1000;
default : return -1;
}
}
int romanToInt(string s)
{
int n = s.size();
int prev = getInteger(s[n - 1]) , result = prev , current;
for(int i = n - 2 ; i >= 0 ; i--)
{
current = getInteger(s[i]);
if(current < prev)
result -= current;
else
result += current;
prev = current;
}
return result;
}
int main()
{
string s = "CXXIX";
cout << romanToInt(s) << '\n';
return 0;
}
자바 프로그램
class roman_to_int
{
public static void main(String args[])
{
String s = "CXXIX";
System.out.println(romanToInt(s));
}
static int getInteger(char c)
{
switch(c)
{
case 'I' : return 1;
case 'V' : return 5;
case 'X' : return 10;
case 'L' : return 50;
case 'C' : return 100;
case 'D' : return 500;
case 'M' : return 1000;
default : return -1;
}
}
static int romanToInt(String s)
{
int n = s.length();
int prev = getInteger(s.charAt(n - 1)) , result = prev , current;
for(int i = n - 2 ; i >= 0 ; i--)
{
current = getInteger(s.charAt(i));
if(current < prev)
result -= current;
else
result += current;
prev = current;
}
return result;
}
}
129
Roman to Integer Leetcode 솔루션의 복잡성 분석
시간 복잡성
다시 한 번 문자열을 횡단합니다. 위에서 논의한 바와 같이 시간 복잡성은 O (1).
공간 복잡성
O (1), 우리는 일정한 메모리 공간 만 사용합니다.
