கொடுக்கப்பட்ட வரிசையிலிருந்து குறைந்தபட்ச எண்ணை உருவாக்குங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அகோலைட் அமேசான் வெறியர்கள் கோல்ட்மேன் சாக்ஸ் தகவல் எட்ஜ் SnapChat
அணி ஸ்டேக் சரம்

“கொடுக்கப்பட்ட வரிசையிலிருந்து குறைந்தபட்ச எண்ணை உருவாக்கு” ​​என்ற சிக்கல் உங்களுக்கு சில வடிவங்கள் வழங்கப்பட்டதாகக் கூறுகிறது இருக்கிறது மற்றும் டி மட்டும். இதன் பொருள் I அதிகரிப்பதற்கும் குறைப்பதற்கும் குறிக்கிறது D. கொடுக்கப்பட்ட வடிவத்தை திருப்திப்படுத்தும் குறைந்தபட்ச எண்ணை அச்சிட சிக்கல் அறிக்கை கேட்கிறது. நாம் 1-9 முதல் இலக்கங்களைப் பயன்படுத்த வேண்டும், எந்த இலக்கங்களும் மீண்டும் செய்யப்படக்கூடாது.

உதாரணமாக

DIID
21354

விளக்கம்

முதல் இலக்கம் 2 ஆகும், பின்னர் அதைக் குறைத்த பிறகு அடுத்த இலக்கம் 1 ஆக இருக்கும். பின்னர் 2 ஐ அதிகரிப்பது 3 ஐ குறைந்தபட்ச இலக்கமாக 2 ஐ விட அதிகமாக்கும். பின்னர் அதை மீண்டும் அதிகரிக்க வேண்டும், ஆனால் மீண்டும் அதிகரித்த பிறகு, அதை குறைக்க வேண்டும் . இலக்கங்களை மீண்டும் செய்ய முடியாது என்பதால். எனவே அதை 2 ஆல் அதிகரிப்போம், பின்னர் அதை 1 ஆகக் குறைப்போம்.

எனவே வெளியீடு 2 1 3 5 4 ஆக மாறும்

மீண்டும் தற்போதைய இலக்கத்தை அதிகரிக்கிறோம். ஆனால் அதைச் செய்வது நமக்கு 4 ஐக் கொடுக்கும், மேலும் 1, 2, அல்லது 3 ஐப் பயன்படுத்த வேண்டியிருக்கும். இந்த இலக்கங்கள் அனைத்தும் ஏற்கனவே பயன்படுத்தப்பட்டன. எனவே தற்போதைய இலக்கத்தை 5 ஆக அதிகரிக்க வேண்டும். அதோடு நாம் பதிலை அடைகிறோம்.

கொடுக்கப்பட்ட வரிசையிலிருந்து குறைந்தபட்ச எண்ணை உருவாக்குவதற்கான வழிமுறை

  1. கொடுக்கப்பட்ட வரிசை நீளம் 9 ஐ விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கிறதா என்று சரிபார்க்கவும், உண்மை என்றால் -1 ஐ திரும்பவும்.
  2. N + 1 அளவின் ஒரு கரி வரிசையை அறிவித்து, எண்ணின் மதிப்பை 1 ஆக அமைக்கவும்.
  3. வரிசையை 0 முதல் n வரை (தொடங்கி) பயணிக்கத் தொடங்குங்கள்.
    1. சரிபார்க்கவும் i சமம் n அல்லது சரத்தின் தற்போதைய எழுத்து “நான்” க்கு சமம், உண்மை என்றால்
      1. முந்தைய மதிப்பிலிருந்து -1 க்கு வரிசையை கடந்து செல்லுங்கள்.
        1. பின்வரும் படிகளைச் செய்வதன் மூலம் வெளியீட்டு வரிசையின் மதிப்புகளைப் புதுப்பிக்கவும்.
          1. எண்ணிக்கையின் மதிப்பை அதிகரித்து வெளியீட்டு வரிசையில் சேமிக்கவும்.
          2. சரிபார்க்கவும் j தற்போதைய குறியீடானது 0 ஐ விட அதிகமாக உள்ளது, மேலும் சரத்தின் தற்போதைய தன்மை “நான்”, பின்னர் உடைக்கவும்.
  4. வருவாய் முடிவு.

விளக்கம்

ஒரு சரம் மற்றும் நான் மற்றும் டி மட்டுமே கொடுக்கப்பட்டால், கொடுக்கப்பட்டதை உருவாக்கக்கூடிய வடிவத்தை அச்சிடுமாறு கேட்கப்படுகிறோம் சரம். இங்கே I கொடுக்கப்பட்ட வரிசையை நியாயப்படுத்தக்கூடிய குறைந்தபட்ச எண்ணை நாம் உருவாக்க வேண்டும் அல்லது உருவாக்க வேண்டும் என்பது அதிகரிப்பதைக் குறிக்கிறது. நாங்கள் சொன்னால் வைத்துக்கொள்வோம் DI, எங்கே D குறைந்தபட்ச எண்ணிக்கையை குறைப்பதை குறிக்கிறது, அதாவது 2 ஐ குறைந்தபட்ச எண்ணாக 21 ஐ உருவாக்குகிறது. இலக்கங்களை மீண்டும் செய்ய முடியாது, எண்ணில் 1-9 முதல் இலக்கங்கள் மட்டுமே இருக்க முடியும். அதன் பிறகு, “நான்” இருக்கிறது, நாம் குறைந்தபட்சமாக அதிகரிக்கும் எண்ணை உருவாக்க வேண்டும். 21 ஏற்கனவே இருப்பதால். அதிகரித்து வரும் எண்ணிக்கையை உருவாக்குவதை நோக்கமாகக் கொண்டுள்ளோம். இவ்வாறு 1 ஐ 3 ஐத் தொடர்ந்து வருகிறது, ஏனென்றால் 2 ஏற்கனவே பயன்பாட்டில் உள்ளது, அதன் பிறகு 3 மட்டுமே இணைக்கக்கூடிய ஒரே எண்.

இந்த கருத்துகள் மற்றும் யோசனைகள் அனைத்தையும் கொண்டு, கொடுக்கப்பட்ட நிபந்தனைகளைப் பின்பற்றி திருப்திப்படுத்தும் குறைந்தபட்ச எண்ணை அச்சிடுமாறு கேட்கப்படுகிறோம். வெளியீட்டு வரிசையை நாம் பயன்படுத்தப் போகிறோம், அதில் நாம் அனைவரும் எங்கள் வெளியீட்டை அந்த எழுத்துக்குறி வரிசையில் சேமித்து வைக்கிறோம். தரவு சரிபார்ப்பு மற்றும் சரிபார்ப்புக்கு சில நிபந்தனைகளை நாங்கள் செய்துள்ளோம். சரத்தின் நீளம் 9 ஐ விட அதிகமாகவோ அல்லது அதற்கு சமமாகவோ நாம் கண்டால், இதன் விளைவாக -1 ஐத் தருகிறோம், ஏனெனில் 1-9 இலக்கத்தைப் பயன்படுத்த நாங்கள் கண்டிப்பாக கட்டளையிடப்பட்டுள்ளோம், எந்த இலக்கங்களையும் மீண்டும் செய்ய முடியாது.

உள்ளீடாக நாங்கள் பெற்ற சரத்தை கடந்து செல்லுங்கள். தற்போதைய குறியீடு சரத்தின் நீளத்திற்கு சமமாக இருந்தால் அல்லது தற்போதைய எழுத்து “நான்” க்கு சமமாக இருந்தால். பின்னர் மட்டுமே நாங்கள் மேலும் முன்னேறுகிறோம். அதன் பிறகு தற்போதைய மதிப்பு (i) க்கு முந்தைய மதிப்பிலிருந்து -1 ஐ அடையும் வரை பயணிக்கத் தொடங்குங்கள். இந்த வட்டத்திற்குள் நாம் எண்ணிக்கையின் மதிப்பை அதிகரித்து, குறியீட்டு j + 1 இல் வெளியீட்டு வரிசையில் சேமித்து வைத்திருக்கிறோம். இதன் மதிப்பு இருக்கிறதா என்று சோதிக்கவும் j விட அதிகமாகவோ அல்லது சமமாகவோ உள்ளது 0 தற்போதைய எழுத்து “நான்” என்றால். உண்மை என்றால், சுழற்சியை உடைத்து மேலும் எழுத்துக்களுக்கு மேலும் தொடரவும்.

குறியீடு

கொடுக்கப்பட்ட வரிசையிலிருந்து குறைந்தபட்ச எண்ணை உருவாக்க சி ++ குறியீடு

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

கொடுக்கப்பட்ட வரிசையிலிருந்து குறைந்தபட்ச எண்ணை உருவாக்க ஜாவா குறியீடு

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்) எங்கே “என்” வினவல் சரத்தின் நீளம். உள்ளமைக்கப்பட்ட வளையத்திற்குள் நாம் நுழைகிறோமா என்பதை முதலில் சரிபார்க்கவும், நாம் முடிவை அடைந்திருந்தால் அல்லது தற்போதைய குறியீடு I ஆக இருந்தால் மட்டுமே. மற்றும் உள்ளமைக்கப்பட்ட வளையம் பின்தங்கிய திசையில் இயங்குகிறது, மேலும் நான் குறுக்கே வந்தால் வளையிலிருந்து வெளியே வருகிறோம். எனவே நாம் சொல்லலாம் நான் ஒரு ஐ சந்திக்கும் போது உள்ளமைக்கப்பட்ட வளையத்திற்குள் நுழைந்து, அவற்றை டி சேமித்து வைத்திருக்கும் குறியீடுகளில் வேலை செய்கிறோம். ஒவ்வொரு குறியீட்டிலும் நான் அல்லது டி இருக்கக்கூடும் என்பதால், ஒவ்வொரு எழுத்துக்கும் மேலாக நாம் ஒன்றுதான் பயணிக்கிறோம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் முடிவைச் சேமிக்க வெளியீட்டு எழுத்துக்குறி வரிசையை உருவாக்கியுள்ளோம். சிக்கலுக்கான இட சிக்கலானது நேரியல் ஆகும்.