로마 정수 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 골드만 삭스 구글 링크드 인 Microsoft 신탁 Qualtrics Roblox 동네 짱 Yahoo
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학 조회수 108

“Roman to Integer”문제에서 우리는 일부 양의 정수를 나타내는 로마 숫자 형식. 로마 숫자는 다음 표를 사용하여 정수로 변환 할 수있는 7 자로 표시됩니다.

로마 정수 Leetcode 솔루션

주의 사항: 주어진 로마 숫자의 정수 값은 값 4000을 초과하거나 같지 않습니다.

IX
9
CXXIX
129

설명 # 1

IX는 정수로 9입니다.

설명 # 2

CXXIX = C + XX + IX = 100 + 20 + 9 = 129

접근 (왼쪽에서 오른쪽으로 통과)

배열에서 왼쪽에서 오른쪽으로 전달하고 배열의 모든 문자에 대해 해당 값을 계속 추가 할 수 있습니다. 그러나 로마 숫자의 특이한 점은 정수 값이 작은 문자가 높은 값보다 먼저 발생하면 그 결과가 구별되는 합이 아니라는 것입니다.

예를 들어 로마자의 IX는 이후에 문자를 추가 한 경우 1 + 10 = 11과 같아야합니다. 그러나, IX = 9, 그 전에 발생하는 X 적분 값이 적습니다. 따라서 결과는 다음과 같이 처리됩니다. I 에서 빼다 X. 따라서 IX = 9.

따라서 단순히 문자열에있는 모든 문자의 정수 값을 더할 수는 없습니다. 위에서 언급 한 경우 옆에있는 문자도 확인해야합니다. 이런 식으로 주어진 로마 숫자 문자열을 필요한 정수로 변환 할 수 있습니다.

암호알고리즘

  1. 함수 만들기 getInteger () 다음을 사용하여 전달 된 단일 로마 문자의 값을 반환하려면 스위치 가지 경우
  2. 초기화 결과 필요한 정수 저장
  3. 다시 초기화 현재 다음 것 반복 할 때마다 각 문자의 현재 및 다음 정수 값을 문자열에 저장합니다.
  4. i = 0에 대해 반복 나는 <N  (N = 배열의 크기)
    • If i 배열의 마지막 인덱스이므로 다음 문자가 없으므로 다음의 정수 값을 추가하십시오. 문자열 [i] 반환 결과
    • 다음을 사용하여 현재 및 다음 문자의 정수 값을 검색합니다. getInteger ()
    • If 현재 <= 다음
      • 추가 현재 ~로 결과
      • 증가 i 1 씩, 즉, i++
    • 다른
      • 추가 다음 것 - 현재 ~로 결과
      • 증가 i 2, 즉, i + = 2
  5. 결과 인쇄

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 패스에서는 배열의 두 번째 마지막 인덱스부터 시작하여 마지막 문자의 정수 값을 일부 변수에 저장할 수 있습니다. 결과에 대한 마지막 문자의 정수 값을 미리 유지합니다. 이제 오른쪽에서 왼쪽으로 이동하면서 현재 문자의 정수 값이 우리가 본 마지막 (이전 / 오른쪽) 요소보다 작은 지 모든 단계에서 확인합니다. 마지막 값보다 작 으면 결과에서이 값을 뺍니다. 그렇지 않으면 결과에 추가합니다. 이 구현은 더 큰 가치를 지닌 캐릭터 앞에 더 작은 가치를 지닌 캐릭터가 후자의 캐릭터에서 빼야한다는 것을 의미한다는 위의 사실에 전적으로 기반합니다.

이 접근 방식은 이전 접근 방식과 작업 수가 거의 동일하지만 반복 할 때마다 마지막 요소를 확인하지 않아도되므로 더 편리합니다.

암호알고리즘

  1. 함수 만들기 getInteger () 위와 유사
  2. 문자열의 마지막 문자의 정수 값을 이전
  3. 초기화 결과 동일 이전
  4. 에서 반복 나는 = N – 2 까지 나는> = 0 :
    1. 현재 문자의 정수 값을 다음과 같이 저장 현재
    2. If 현재 ~보다 작다. 이전
      1. 덜다 현재결과즉, 결과 -= 현재
    3. 다른
      1. 추가 현재결과즉, 결과 += 현재
  5. 결과 인쇄

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), 우리는 일정한 메모리 공간 만 사용합니다.

코멘트를 남겨

Translate »
1