دیئے گئے ترتیب سے کم سے کم تعداد بنائیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اکٹھا کرنا ایمیزون فانٹکس گولڈمین سیکس انفارمیشن ایج 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) سے این تک شامل کرنا شروع کریں۔
    1. اگر چیک کریں i کے برابر ہے n یا اسٹرنگ کا حالیہ کردار "I" کے برابر ہے ، اگر درست ہے تو
      1. -1 کی پچھلی قیمت سے صف کو عبور کریں۔
        1. درج ذیل اقدامات کرکے آؤٹ پٹ صف کی قدر کو اپ ڈیٹ کریں۔
          1. گنتی کی قدر میں اضافہ کریں اور اسے آؤٹ پٹ صف میں محفوظ کریں۔
          2. اگر چیک کریں j موجودہ انڈیکس 0 سے زیادہ ہے ، اور اسٹرنگ کا حالیہ کردار بھی "I" ہے ، پھر ، توڑنا۔
  4. نتیجہ لوٹائیں۔

وضاحت

صرف اور صرف اور صرف اور صرف ایک تار کو دیکھتے ہوئے ، ہمیں پیٹرن کو پرنٹ کرنے کے لئے کہا جاتا ہے جو دیئے گئے کے ساتھ تشکیل پا سکتا ہے سٹرنگ. یہاں I اس سے زیادہ مراد ہے کہ ہمیں کم سے کم تعداد بنانا یا بنانا ہے جو دیئے گئے تسلسل کو جواز بناسکے۔ فرض کریں اگر ہم کہیں DI، کہاں D کم سے کم تعداد کم ہونے کا مطلب ہے 2 اس کے بعد کم سے کم تعداد 21 بنائیں۔ ہندسے کو دہرایا نہیں جاسکتا ، تعداد میں صرف 1-9 کے ہندسے شامل ہوسکتے ہیں۔ اس کے بعد ، "میں" موجود ہے ، ہمیں کم سے کم تعداد میں اضافہ کرنا چاہئے۔ چونکہ 21 پہلے ہی موجود ہے۔ ہمارا مقصد ایک بڑھتی ہوئی تعداد تشکیل دینا ہے۔ اس طرح 1 کے بعد 3 ہوتا ہے ، کیونکہ 2 پہلے سے استعمال میں ہے ، اور اس کے بعد 3 واحد تعداد ہے جس میں شامل ہوسکتا ہے۔

ان تمام تصورات اور نظریات کے ساتھ ، ہم سے کہا جاتا ہے کہ وہ کم سے کم تعداد پرنٹ کریں جو مندرجہ ذیل شرائط کی پیروی اور اطمینان بخش ہے۔ ہم آؤٹ پٹ صف کو استعمال کرنے جارہے ہیں جس میں ہم سب اپنے آؤٹ پٹ کو اس کردار کی صف میں محفوظ کرتے ہیں۔ ہم نے ڈیٹا کی توثیق اور تصدیق کے ل conditions کچھ شرائط بنائیں۔ اگر ہمیں سٹرنگ کی لمبائی 9 سے زیادہ یا اس کے برابر معلوم ہوجاتی ہے تو پھر ہم اس کے نتیجے میں -1 واپس آجاتے ہیں کیونکہ ہمیں سختی سے 1-9 ہندسے کو استعمال کرنے کا حکم دیا گیا ہے اور کسی بھی ہندسے کی تکرار نہیں کی جاسکتی ہے۔

ان پٹ کے بطور جو تار ہمیں موصول ہوا ہے اس کو عبور کریں۔ اگر موجودہ انڈیکس تار کی لمبائی کے برابر ہے یا موجودہ حرف "I" کے برابر ہے۔ تب صرف ہم آگے بڑھتے ہیں۔ اس کے بعد موجودہ قیمت (i) سے سابقہ ​​قیمت سے گذرنا شروع کریں ، یہاں تک کہ -1 تک پہنچ جا.۔ اس لوپ کے اندر ہم گنتی کی قدر میں اضافہ کرتے اور انڈیکس j + 1 پر آؤٹ پٹ صف میں اسٹور کرتے رہتے ہیں۔ پھر چیک کریں کہ کیا قیمت ہے j سے زیادہ یا اس کے برابر ہے 0 اور یہ بھی کہ اگر موجودہ کردار "میں" ہوں۔ اگر سچ ہے تو ، پھر لوپ کو توڑیں اور مزید کرداروں کے لئے آگے بڑھیں۔

ضابطے

دیئے گئے ترتیب سے کم سے کم تعداد بنانے کیلئے C ++ کوڈ

#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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) کہاں "N" استفسار کے تار کی لمبائی ہے۔ پہلے چیک کریں کہ ہم اندرونی اندر لوپ کے اندر داخل ہوتے ہیں ، صرف اس صورت میں جب ہم اختتام کو پہنچ گئے ہوں یا موجودہ انڈیکس I ہے۔ اور گھریلو لوپ ایک پسماندہ سمت چلتا ہے اور اگر ہم پار آتے ہیں تو ہم لوپ سے باہر آجاتے ہیں۔ لہذا ہم کہہ سکتے ہیں کہ جب ہم کسی I کا سامنا کرتے ہیں اور ان اشارے پر کام کرتے ہیں جب ان میں ڈی اسٹور ہوتا ہے تو ہم گھریلو لوپ میں داخل ہوجاتے ہیں۔ چونکہ ہر انڈیکس میں یا تو I یا D. ہوسکتا ہے ہم ہر ایک کردار میں صرف ایک ہی کردار سے گزر رہے ہیں۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

O (N)، کیونکہ ہم نے نتائج کو ذخیرہ کرنے کے لئے آؤٹ پٹ کیریکٹر کی صف تیار کی ہے۔ مسئلے کے لئے جگہ کی پیچیدگی بھی لکیری ہے۔