Leetcode Solution မှ Integer သို့ရောမ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Facebook က Goldman Sachs Google LinkedIn တို့ Microsoft က Oracle က Qualtrics Roblox Uber Yahoo က
သင်္ချာ ကြိုး

“ ရောမသို့ပေါင်းစည်းခြင်း” ပြနာတွင်၊ ကြိုး ၎င်း၏အချို့အပြုသဘောကိန်းကိုယ်စားပြု ရောမ ဂဏန်းပုံစံ။ ရောမနံပါတ်များကိုအောက်ပါဇယား သုံး၍ ကိန်းဂဏန်း ၇ ခုဖြင့်ကိန်းဂဏန်းများအဖြစ်ပြောင်းလဲနိုင်သည်။

Leetcode Solution မှ Integer သို့ရောမ

မှတ်စု: ပေးထားသောရောမဂဏန်း၏ကိန်းသည်တန်ဖိုး ၄၀၀၀ ထက်မပိုပါ။

နမူနာ

IX
9
CXXIX
129

ရှင်းလင်းချက် # 1

IX သည်ကိန်း၏ ၉ ဖြစ်သည်

ရှင်းလင်းချက် # 2

CXXIX = ကို C + XX + IX = 100 + 20 + 9 = 129

ချဉ်းကပ်မှု (ဘယ်မှညာသို့)

ဘယ်ဘက်မှညာဘက်ဖြတ်သန်းသွားခြင်းကိုကျွန်ုပ်တို့ပြုလုပ်နိုင်ပြီး၎င်းအတွင်းရှိစာလုံးတိုင်းအတွက်သက်ဆိုင်ရာတန်ဖိုးကို ဆက်၍ ထည့်နိုင်သည်။ သို့သော်၊ ကိန်းဂဏန်းများ၏ထူးခြားသောလက္ခဏာမှာမြင့်မားသောတန်ဖိုးမပေါ်မီကိန်းအနိမ့်ကျသောအက္ခရာတစ်ခုဖြစ်ပေါ်လျှင်ရလဒ်သည်ကွဲပြားသောပေါင်းလဒ်မဟုတ်ပါ။

ဥပမာအားဖြင့်၊ အကယ်၍ စာလုံးများထပ်မံထည့်ပါက၊ ရောမပါ IX သည် 1 + 10 = 11 နှင့်ညီသည်။ အဖြစ်, IX = 9 အဖြစ် အဲ့တာမတိုင်ခင် X အရေးပါသောတန်ဖိုးလျော့နည်းသည်။ ဒါကြောင့်ရလဒ်အဖြစ်ကုသသည် I နှုတ်ယူသည် X။ ထို့ကြောင့် IX = 9 ။

ထို့ကြောင့်ကျွန်ုပ်တို့သည် string အတွင်းရှိအက္ခရာတိုင်း၏ကိန်းတန်ဖိုးအားလုံးကိုရိုးရှင်းစွာ ထပ်၍ မထည့်နိုင်ပါ။ အထက်ဖော်ပြပါကိစ္စရပ်အတွက်စာလုံးဘေးရှိစာလုံးကိုစစ်ဆေးရန်လိုသည်။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်ပေးထားသောရောမဂဏန်း string ကိုလိုအပ်သည့်ကိန်းသို့ပြောင်းနိုင်သည်။

algorithm

  1. function တစ်ခုဖန်တီးပါ getInteger () သုံးပြီးအဲဒါကိုကူးတဲ့တစ်ခုတည်းသောရောမဇာတ်ကောင်များ၏တန်ဖိုးကိုပြန်လာရန် ပွောငျးလဲ အမှုပေါင်း
  2. စတငျ ရလဒ် လိုအပ်သောကိန်းသိုလှောင်ရန်
  3. တနည်းကား, အစပြု ယခု နှင့် လာမယ့် သက်ဆိုင်ရာအက္ခရာများ၏လက်ရှိနှင့်နောက်ကိန်းတန်ဖိုးများ၏တန်ဖိုးကိုကြားဖြတ်တိုင်းအတွက် string တွင်သိမ်းဆည်းရန်
  4. သည်အထိဈ = 0 အဘို့အကြားမှာ i <N <  (N = ခင်းကျင်း၏အရွယ်အစား)
    • If i array ရဲ့နောက်ဆုံးအညွှန်းကိန်း၊ ကျွန်တော်တို့မှာနောက်ထပ်ဇာတ်ကောင်မရှိဘူး ကြိုး [i] ပြန်လာ ရလဒ်
    • သုံး၍ လက်ရှိနှင့်နောက်စာလုံးများ၏ကိန်းတန်ဖိုးကိုရယူပါ getInteger ()
    • If လက်ရှိ <= လာမယ့်
      • ပေါင်း ယခု အမှ ရလဒ်
      • တိုး i 1 ဖြင့်ဆိုလိုသည်မှာ i++
    • အခြားသူ
      • ပေါင်း လာမယ့် - ယခု အမှ ရလဒ်
      • တိုး i 2 ဖြင့်ဆိုလိုသည်မှာ i + = 2
  5. ရလဒ်ပုံနှိပ်ပါ

Leetcode Solution ကို Integer သို့ရောမ၏အကောင်အထည်ဖော်ခြင်း

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 Solution မှ Integer သို့ရောမ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

ဤတွင်ကျွန်ုပ်တို့သည်တစ်ချိန်က string ကိုဖြတ်သန်း။ ကျွန်တော်တို့မှာကိန်းစစ်ကန့်သတ်ချက် ၄၀၀၀ ထက်နည်းတဲ့အတွက် string size ဟာအမြဲတမ်းအမြဲတမ်းတန်ဖိုးဖြစ်နေလိမ့်မယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးသည် အို (၁).

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ကျွန်ုပ်တို့သည်စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသာသုံးသည်။

ချဉ်းကပ်မှု (ဘယ်ဘက်မှညာသို့)

Right-to-left နှင့် left-to-right အကြားခြားနားချက်ကတော့သူတို့အကောင်အထည်ဖော်မှုတွင်တည်ရှိသည်။ Right-to-Left pass မှာ array ရဲ့ဒုတိယနောက်ဆုံးအညွှန်းကိန်းကနေစပြီးအချို့သော variable ထဲမှာနောက်ဆုံးစာလုံး၏ကိန်းဂဏန်းကိုသိုလှောင်ထားနိုင်သည်။ ကျွန်ုပ်တို့သည်နောက်ဆုံးဇာတ်ကောင်များ၏အဓိကကျသောတန်ဖိုးကိုရလဒ်ကိုကြိုတင်ထိန်းသိမ်းထားသည်။ အခုဆိုရင်ညာဘက်ကိုမှဘယ်ဘက်သို့ရွေ့လျားသွားတဲ့အခါ၊ လက်ရှိစာလုံး၏ကိန်းဂဏန်းသည်နောက်ဆုံး (ယခင် / ညာ) မြင်တွေ့ခဲ့ရသောဒြပ်စင်ထက်လျော့နည်းမနေကိုအဆင့်တိုင်းကိုစစ်ဆေးသည်။ အကယ်၍ ၎င်းသည်နောက်ဆုံးတန်ဖိုးထက်လျော့နည်းပါကကျွန်ုပ်တို့သည်ဤတန်ဖိုးကိုရလဒ်မှနုတ်လိုက်ပါ။ ဒီလိုမှမဟုတ်ရင်ကျွန်တော်တို့ရဲ့ရလဒ်ကထည့်ပါ။ ဤအကောင်အထည်ဖော်မှုသည်အထက်ပါအချက်အပေါ်အခြေခံသည်။ ပိုမိုကြီးသောတန်ဖိုးမပေးမီတန်ဖိုးသေးငယ်သည့်ဇာတ်ကောင်သည်၎င်းကိုအဆုံးတွင်နုတ်ရမည်ဟုဆိုလိုသည်။

ဤချဉ်းကပ်မှုသည်ယခင်ချဉ်းကပ်မှုနှင့်တူသောစစ်ဆင်ရေးအရေအတွက်နှင့်အတူတူနီးပါးဖြစ်သော်လည်းနောက်ဆုံးကြားဖြတ်ချက်အတွက်စစ်ဆေးရန်ဖယ်ထုတ်လိုက်သည်နှင့် ပို၍ အဆင်ပြေသည်။

algorithm

  1. function တစ်ခုဖန်တီးပါ getInteger () အထက်တွင်ကဲ့သို့ဆင်တူသည်
  2. string ၏နောက်ဆုံးအက္ခရာ၏ integer တန်ဖိုးကိုသိမ်းထားပါ prev
  3. စတငျ ရလဒ် ညီမျှသည် prev
  4. မှဖြတ် i = N - 2 မှီတိုငျအောငျ i> = 0:
    1. အဖြစ်လက်ရှိဇာတ်ကောင်များ၏ကိန်းတန်ဖိုးသိမ်းထားပါ ယခု
    2. If ယခု ထက်နည်းသည် prev
      1. နုတ်ပါ ယခု မှ ရလဒ်ဆိုလိုသည်မှာ ရလဒ် -= ယခု
    3. အခြားသူ
      1. ပေါင်း ယခု သို့ ရလဒ်ဆိုလိုသည်မှာ ရလဒ် += ယခု
  5. ရလဒ်ပုံနှိပ်ပါ

Leetcode Solution ကို Integer သို့ရောမ၏အကောင်အထည်ဖော်ခြင်း

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 Solution မှ Integer သို့ရောမ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

တနည်းကား, ကျနော်တို့တစ်ချိန်က string ကိုဖြတ်သန်း။ အထက်တွင်ဆွေးနွေးထားသည့်အတိုင်းအချိန်ရှုပ်ထွေးသည် အို (၁).

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ကျွန်ုပ်တို့သည်စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသာသုံးသည်။