សំណុំបែបបទលេខអប្បបរមាពីលំដាប់ដែលបានផ្តល់ឱ្យ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន Amazon និយមជ្រុល ក្រុមហ៊ុន Goldman Sachs គែមព័ត៌មាន Snapchat
អារេ ជង់ ខ្សែអក្សរ

បញ្ហា“ សំណុំបែបបទលេខអប្បបរមាពីលំដាប់ដែលបានផ្តល់ឱ្យ” ចែងថាអ្នកត្រូវបានផ្តល់គំរូមួយចំនួន ខ្ញុំ និង ឃរបស់ តែប៉ុណ្ណោះ។ អត្ថន័យនៃ I តំណាងឱ្យការកើនឡើងនិងសម្រាប់ការថយចុះយើងត្រូវបានផ្តល់ឱ្យជាមួយ D។ របាយការណ៍បញ្ហាស្នើឱ្យបោះពុម្ពលេខអប្បបរមាដែលត្រូវនឹងលំនាំដែលបានផ្តល់។ យើងត្រូវប្រើតួរលេខចាប់ពីលេខ ១ ដល់ ៩ ហើយគ្មានលេខណាមួយគួរត្រូវបានធ្វើម្តងទៀតឡើយ។

ឧទាហរណ៍

DIID
21354

ការពន្យល់

ខ្ទង់ទីមួយគឺ ២ បន្ទាប់មកបន្ទាប់ពីបន្ថយវាខ្ទង់បន្ទាប់នឹងមាន ១ ។ បន្ទាប់មកកើនឡើង ២ នឹងបង្កើត ៣ ជាខ្ទង់អប្បបរមាដែលធំជាង ២ ។ ហើយបន្ទាប់មកយើងត្រូវបង្កើនវាម្តងទៀតប៉ុន្តែបន្ទាប់ពីកើនឡើងម្តងទៀតយើងត្រូវបន្ថយវា ។ ចាប់តាំងពីតួលេខមិនអាចត្រូវបានធ្វើម្តងទៀត។ ដូច្នេះយើងនឹងបង្កើនវាដោយ ២ ហើយបន្ទាប់មកបន្ថយវាដោយ ១ ។

ដូច្នេះលទ្ធផលនឹងក្លាយជា ២ ១ ៣ ៥ ៤

ជាថ្មីម្តងទៀតយើងបង្កើនតួលេខបច្ចុប្បន្ន។ ប៉ុន្តែការធ្វើវានឹងផ្តល់ឱ្យយើង ៤ ហើយបន្ទាប់ពីបន្ថយថាយើងនឹងត្រូវប្រើលេខ ១ ២ ឬ ៣ ហើយលេខទាំងអស់នេះត្រូវបានប្រើរួចហើយ។ ដូច្នេះយើងត្រូវបង្កើនខ្ទង់បច្ចុប្បន្នទៅ ៥ ហើយនោះជាវិធីដែលយើងឈានដល់ចម្លើយ។

ក្បួនដោះស្រាយដើម្បីបង្កើតជាចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់ឱ្យ

  1. ពិនិត្យមើលថាតើប្រវែងដែលបានផ្តល់ឱ្យធំជាងឬស្មើនឹង ៩ ប្រសិនបើពិតបន្ទាប់មកត្រឡប់ -9 ។
  2. ប្រកាសអាគុយសាកទំហំ n + 1 និងកំណត់តម្លៃរាប់ដល់ ១ ។
  3. ចាប់ផ្តើមឆ្លងកាត់អារេពី ០ ដល់ n (រួមបញ្ចូល) ។
    1. ពិនិត្យមើលថាតើ i គឺស្មើនឹង n ឬតួអក្សរបច្ចុប្បន្នរបស់ខ្សែអក្សរគឺស្មើនឹង“ ខ្ញុំ” ប្រសិនបើពិត
      1. ឆ្លងកាត់អារេពីតម្លៃមុនដល់ -១ ។
        1. ធ្វើបច្ចុប្បន្នភាពតម្លៃនៃជួរលទ្ធផលដោយធ្វើតាមជំហានខាងក្រោម។
          1. បង្កើនតម្លៃនៃការរាប់ហើយរក្សាទុកវាទៅជួរលទ្ធផល។
          2. ពិនិត្យមើលថាតើ j គឺសន្ទស្សន៍បច្ចុប្បន្នធំជាង ០ និងតួអក្សរបច្ចុប្បន្ននៃខ្សែគឺ“ ខ្ញុំ” បន្ទាប់មកបំបែក។
  4. លទ្ធផលត្រឡប់មកវិញ។

ការពន្យល់

ដែលបានផ្តល់ឱ្យខ្សែអក្សរមួយនិងតែមួយគត់របស់ I និង D យើងត្រូវបានស្នើសុំឱ្យបោះពុម្ពលំនាំដែលអាចត្រូវបានបង្កើតឡើងជាមួយដែលបានផ្តល់ឱ្យ ខ្សែអក្សរ។ នៅទីនេះ I សំដៅទៅលើការកើនឡើងដែលយើងត្រូវធ្វើឬបង្កើតជាចំនួនអប្បបរមាដែលអាចបញ្ជាក់អំពីលំដាប់ដែលបានផ្តល់។ ឧបមាថាបើយើងនិយាយ DI, ដែលជាកន្លែងដែល D តំណាងឱ្យការថយចុះចំនួនអប្បបរមាដូចជាលេខ ២ ដែលបន្តដោយការបង្កើតលេខ ២១ ជាចំនួនអប្បបរមា។ តួលេខមិនអាចត្រូវបានធ្វើម្តងទៀតទេលេខអាចមានតែតួលេខពីលេខ 2-21 ។ បន្ទាប់ពីនោះ“ ខ្ញុំ” នៅទីនោះយើងគួរតែបង្កើតចំនួនកើនឡើងអប្បបរមា។ ចាប់តាំងពី 1 មានរួចទៅហើយ។ យើងមានគោលបំណងបង្កើតចំនួនកើនឡើង។ ដូច្នេះលេខ ១ គឺបន្តដោយលេខ ៣ ពីព្រោះលេខ ២ កំពុងប្រើប្រាស់រួចហើយហើយលេខ ៣ គឺជាលេខតែមួយគត់ដែលអាចចូលរួមបាន។

ជាមួយនឹងគំនិតនិងគំនិតទាំងអស់នេះយើងត្រូវបានស្នើសុំឱ្យបោះពុម្ពលេខអប្បបរមាដែលធ្វើតាមនិងបំពេញលក្ខខណ្ឌដែលបានផ្តល់។ យើងនឹងប្រើអារេលទ្ធផលដែលយើងរក្សាទុកលទ្ធផលរបស់យើងទៅអារេតួអក្សរនោះ។ យើងបានបង្កើតលក្ខខណ្ឌមួយចំនួនសម្រាប់ការធ្វើឱ្យមានសុពលភាពទិន្នន័យនិងការផ្ទៀងផ្ទាត់។ ប្រសិនបើយើងរកឃើញប្រវែងនៃខ្សែដែលធំជាងឬស្មើ ៩ ។ បន្ទាប់មកយើងត្រឡប់ -9 ជាលទ្ធផលព្រោះយើងត្រូវបានគេបញ្ជាឱ្យប្រើខ្ទង់លេខ ១ ដល់ ៩ ខ្ទង់យ៉ាងតឹងរឹងហើយគ្មានតួលេខអាចត្រូវបានធ្វើម្តងទៀតឡើយ

ឆ្លងកាត់ខ្សែអក្សរដែលយើងបានទទួលជាការបញ្ចូល។ ប្រសិនបើសន្ទស្សន៍បច្ចុប្បន្នស្មើនឹងប្រវែងខ្សែអក្សរឬតួអក្សរបច្ចុប្បន្នស្មើនឹង“ ខ្ញុំ” ។ បន្ទាប់មកមានតែយើងបន្តទៅមុខទៀត។ បន្ទាប់ពីនោះចាប់ផ្តើមឆ្លងកាត់ពីតម្លៃមុនទៅតម្លៃបច្ចុប្បន្ន (អាយ) រហូតដល់ -១ បានដល់។ នៅខាងក្នុងរង្វិលជុំនេះយើងបន្តបង្កើនតម្លៃនៃការរាប់និងរក្សាទុកក្នុងអារេលទ្ធផលនៅសន្ទស្សន៍ 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 និងធ្វើការលើសូចនាករដែល D ផ្ទុកនៅពួកវា។ ដោយសារលិបិក្រមនីមួយៗអាចមានខ្ញុំឬឃ។ យើងកំពុងឆ្លងកាត់តួអក្សរនីមួយៗតែមួយ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N)ពីព្រោះយើងបានបង្កើតអារេតួអក្សរបញ្ចេញដើម្បីរក្សាទុកលទ្ធផល។ ភាពស្មុគស្មាញនៃលំហសម្រាប់បញ្ហាក៏ជាលីនេអ៊ែរដែរ។