Ромын бүхэл бүтэн Leetcode шийдэл  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Facebook-ийн Goldman Sachs Google-ийн LinkedIn Microsoft- Oracle-ийн Qualtrics Roblox Uber Yahoo
алгоритмууд кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Математик String

“Ромоос бүхэл тоо” гэсэн бодлогод бид a мөр түүний дотор зарим эерэг бүхэл тоог илэрхийлнэ Роман тоон хэлбэр. Ромын тоонуудыг дараахь хүснэгтийг ашиглан бүхэл тоонд хөрвүүлж болох 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.

Тиймээс бид тэмдэгт бүрийн бүхэл тоон утгыг энгийн байдлаар нэмж чадахгүй. Дээр дурдсан тохиолдолд бид хажууд нь байгаа дүрийг шалгах хэрэгтэй. Ийм байдлаар бид өгөгдсөн роман тооны мөрийг шаардлагатай бүхэл тоо болгон хөрвүүлж чадна.

мөн үзнэ үү
Leetcode шийдлийн жагсаалтыг эргүүлэх

Алгоритм

  1. Функц үүсгэх getInteger () түүнд шилжүүлсэн нэг роман тэмдэгтийн утгыг буцааж өгөх өөрчлөх тохиолдлууд
  2. Эхлүүлэх үр дүн шаардлагатай бүхэл тоог хадгалах
  3. Дахин эхлүүл одоогийн болон ирэх тухайн тэмдэгтийн одоогийн ба дараагийн бүхэл тоон утгыг мөрөнд давталт бүрт хадгалах
  4. I = 0 хүртэл давтана би <N  (N = массивын хэмжээ)
    • If i нь массивын сүүлийн индекс бөгөөд бидэнд дараагийн тэмдэгт байхгүй тул бүхэл тоон утгыг нэмнэ үү Мөр [i] буцаж ирнэ үр дүн
    • Одоогийн ба дараагийн тэмдэгтүүдийн бүхэл тоон утгыг ашиглана уу getInteger ()
    • If одоогийн <= дараагийн
      • нэмэх одоогийн нь үр дүн
      • Инфляци i 1-ээр, өөрөөр хэлбэл i++
    • Бусад
      • нэмэх ирэх - одоогийн нь үр дүн
      • Инфляци i 2-оор, өөрөөр хэлбэл i + = 2
  5. Үр дүнг хэвлэ

Ромын бүхэл бүтэн 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;
}

Java програм

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

Ромын бүхэл бүтэн Leetcode шийдлийн цогц шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Энд бид мөрийг нэг удаа туулдаг. Бид бүхэл тоон хязгаар нь 4000-аас бага тул мөрийн хэмжээ үргэлж тогтмол утга байх болно. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь юм O (1).

мөн үзнэ үү
График хувилах

Сансрын нарийн төвөгтэй байдал

O (1), Бид зөвхөн тогтмол санах ойн зайг ашигладаг.

Хандлага (Баруун зүүн дамжуулалт)  

Баруунаас зүүнээс зүүнээс баруун тийш ялгаа нь тэдгээрийг хэрэгжүүлэхэд оршино. Баруунаас зүүн тийш дамжуулахад массивын сүүлчийн тэмдэгтийн бүхэл тоон утгыг зарим хувьсагч дотор хадгалан хоёр дахь сүүлчийн индексээс эхлүүлж болно. Бид сүүлчийн тэмдэгтийн салшгүй утга, үр дүнг урьдчилж хадгална. Одоо бид баруунаас зүүн тийш шилжихдээ одоогийн тэмдэгтийн бүхэл тоон утга нь бидний харсан сүүлчийн (өмнөх / баруун) элементээс бага байгаа эсэхийг алхам бүр дээр шалгана. Хэрэв энэ нь сүүлчийн утгаас бага байвал бид энэ утгыг үр дүнгээс хасна. Үгүй бол бид үүнийг үр дүн дээрээ нэмнэ. Энэхүү хэрэгжилт нь дээр дурдсан баримтад бүрэн үндэслэсэн бөгөөд том хэмжээтэй дүрээс өмнө бага үнэлгээтэй байх нь түүнийг сүүлчийнхээс хасах шаардлагатай гэсэн үг юм.

Энэ арга нь өмнөх арга барилтай харьцуулахад үйл ажиллагааны тоогоор бараг ижил боловч давталт бүрийн сүүлчийн элементийг шалгахаас татгалзах нь илүү тохиромжтой юм.

Алгоритм

  1. Функц үүсгэх getInteger () дээрхтэй төстэй
  2. Мөрний сүүлчийн тэмдэгтийн бүхэл утгыг хадгална уу prev
  3. Эхлүүлэх үр дүн тэнцүү prev
  4. -Аас давтах i = N - 2 хүртэл би> = 0:
    1. Одоогийн тэмдэгтийн бүхэл утгыг дараах байдлаар хадгална одоогийн
    2. If одоогийн бага байна prev
      1. Хасах одоогийн нь үр дүн, тэр бол, үр дүн -= одоогийн
    3. Бусад
      1. нэмэх одоогийн to үр дүн, тэр бол, үр дүн += одоогийн
  5. Үр дүнг хэвлэ

Ромын бүхэл бүтэн 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;
}

Java програм

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

Ромын бүхэл бүтэн Leetcode шийдлийн цогц шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дахин хэлэхэд бид мөрийг нэг удаа туулдаг. Дээр дурдсанчлан цаг хугацааны нарийн төвөгтэй байдал юм O (1).

мөн үзнэ үү
Анхан шатны тооллыг тоолох

Сансрын нарийн төвөгтэй байдал

O (1), Бид зөвхөн тогтмол санах ойн зайг ашигладаг.