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


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

តារាង​មាតិកា

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ទម្រង់លេខអប្បបរមាពីលំដាប់ដែលបានផ្តល់ឱ្យចែងថាអ្នកត្រូវបានផ្តល់ឱ្យក ខ្សែអក្សរ s នៃប្រវែង / ទំហំ n តំណាងឱ្យលំនាំនៃតួអក្សរ "I" ពោលគឺការកើនឡើងនិង "D" មានន័យថាមានការថយចុះតែប៉ុណ្ណោះ។ បោះពុម្ពលេខអប្បបរមាសម្រាប់លំនាំដែលបានផ្តល់ឱ្យដោយមានខ្ទង់តែមួយគត់ពីលេខ 1-9 ។

ឧទាហរណ៍ -

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

ឧទាហរណ៍

s = "DD"
3 2 1

ការពន្យល់ៈដោយសារតួលេខនេះមិនអាចអវិជ្ជមានយើងនឹងជ្រើសរើសលេខ ៣ ជាខ្ទង់ទីមួយហើយបន្ទាប់មកបន្តបន្ថយលេខដែលនឹងមកដល់។

s = "DIDI"
2 1 4 3 5

វិធីសាស្រ្ត 1

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមខ្សែអក្សរ s ។
  2. ឆ្លងកាត់ខ្សែអក្សរដែលបានផ្តល់ឱ្យហើយពិនិត្យមើលថាតើតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែអក្សរស្មើនឹង 'ខ្ញុំ', គណនាចំនួនសរុបនៃតួអក្សរជាប់គ្នាបន្ទាប់ស្មើនឹង 'D' នៅក្នុងខ្សែអក្សរដែលបានផ្តល់ឱ្យ។
  3. ប្រសិនបើតួអក្សរ 'ខ្ញុំ' ជាតួអក្សរទីមួយនៅក្នុងខ្សែអក្សរសូមបោះពុម្ពលំនាំដែលចាប់ផ្តើមពីលេខ ១ បោះពុម្ពខ្ទង់បន្ទាប់។
  4. បោះពុម្ពលំនាំថយចុះសម្រាប់តួអក្សរបន្តបន្ទាប់ទាំងអស់ស្មើនឹង“ ឃ” ក្នុងខ្សែអក្សរដែលបានផ្តល់។
  5. ស្រដៀងគ្នានេះដែរពិនិត្យមើលថាតើតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែអក្សរស្មើនឹង equal ឃ check ពិនិត្យមើលថាតើតួអក្សរ D ឃ the ជាតួអក្សរទីមួយនៅក្នុងខ្សែអក្សររាប់លេខ the ទាំងអស់នៅក្នុងខ្សែអក្សរហើយបោះពុម្ពលំនាំតាម។
  6. បន្ថយការបញ្ចូលចុងក្រោយដោយ ១ ។

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n) ដែល n ជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ s ។

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

អូ (n) ពីព្រោះយើងបានប្រើកន្លែងទំនេរដើម្បីរក្សាទុកតួអក្សរនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីបង្កើតជាចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    int curr_max = 0; 
  
    int last_entry = 0; 
  
    int j; 
  
    for(int i=0; i<arr.length(); i++){ 
        int noOfNextD = 0; 
  
        switch(arr[i]){ 
            case 'I': 
                j = i+1; 
                while (arr[j] == 'D' && j < arr.length()){ 
                    noOfNextD++; 
                    j++; 
                } 
                    
                if (i==0){ 
                    curr_max = noOfNextD + 2; 
      
                    cout << " " << ++last_entry; 
                    cout << " " << curr_max; 
      
                    last_entry = curr_max; 
                } 
                
                else{ 
                    curr_max = curr_max + noOfNextD + 1; 
      
                    last_entry = curr_max; 
                    cout << " " << last_entry; 
                } 
      
                for (int k=0; k<noOfNextD; k++){ 
                    cout << " " << --last_entry; 
                    i++; 
                } 
                break; 
      
            case 'D': 
                if (i == 0){ 
                    j = i+1; 
                    while (arr[j] == 'D' && j < arr.length()){ 
                        noOfNextD++; 
                        j++; 
                    } 
      
                    curr_max = noOfNextD + 2; 
      
                    cout << " " << curr_max << " " << curr_max - 1; 
      
                    last_entry = curr_max - 1; 
                } 
                
                else{ 
                    cout << " " << last_entry - 1; 
                    last_entry--; 
                } 
                break; 
        } 
    } 
    cout << endl; 
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

ចាវ៉ាកម្មវិធីដើម្បីបង្កើតចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        int curr_max = 0; 
  
        int last_entry = 0; 
  
        int j; 
  
        for (int i = 0; i < arr.length(); i++){ 
            int noOfNextD = 0; 
  
            switch (arr.charAt(i)){ 
                case 'I': 
                    j = i + 1; 
                    while (j < arr.length() && arr.charAt(j) == 'D'){ 
                        noOfNextD++; 
                        j++; 
                    } 
  
                    if (i == 0){ 
                        curr_max = noOfNextD + 2; 
  
                        System.out.print(" " + ++last_entry); 
                        System.out.print(" " + curr_max); 
  
                        last_entry = curr_max; 
                    }  
                    
                    else{ 
                        curr_max = curr_max + noOfNextD + 1; 
  
                        last_entry = curr_max; 
                        System.out.print(" " + last_entry); 
                    } 
  
                    for (int k = 0; k < noOfNextD; k++){ 
                        System.out.print(" " + --last_entry); 
                        i++; 
                    } 
                    break; 
  
                case 'D': 
                    if (i == 0){ 
                        j = i + 1; 
                        while (j < arr.length()&&arr.charAt(j) == 'D'){ 
                            noOfNextD++; 
                            j++; 
                        } 
  
                        curr_max = noOfNextD + 2; 
  
                        System.out.print(" " + curr_max + " " + (curr_max - 1)); 
  
                        last_entry = curr_max - 1; 
                    }  
                    else{ 
                        System.out.print(" " + (last_entry - 1)); 
                        last_entry--; 
                    } 
                    break; 
            } 
        } 
        System.out.println(); 
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

វិធីសាស្រ្ត 2

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមខ្សែអក្សរ s ។
  2. បង្កើតវ៉ិចទ័រ v នៃចំនួនគត់ប្រភេទ។
  3. ពិនិត្យមើលថាតើតួអក្សរដំបូងនៃខ្សែអក្សរដែលបានផ្តល់គឺ 'ខ្ញុំ' រុញ 1 និង 2 នៅក្នុងវ៉ិចទ័រហើយកំណត់ចំនួនដែលអាចរកបានអប្បបរមា 3 និងទីតាំងនៃ 'ខ្ញុំ' ជា 1 ។
  4. ការជម្រុញផ្សេងទៀត ២ និង ១ នៅក្នុងវ៉ិចទ័រហើយកំណត់ចំនួនអប្បបរមាដែលអាចប្រើបានជា ៣ និងទីតាំងនៃ 'I' ដូច ០ ។
  5. ឆ្លងកាត់ខ្សែអក្សរដែលចាប់ផ្តើមពីលេខ 1 ហើយពិនិត្យមើលថាតើតួអក្សរបច្ចុប្បន្ននៃខ្សែដែលបានផ្តល់គឺ 'ខ្ញុំ' រុញចំនួនដែលមានអប្បបរមានៅក្នុងវ៉ិចទ័របង្កើនចំនួនអប្បបរមាដែលអាចរកបាននិងធ្វើបច្ចុប្បន្នភាពទីតាំងនៃ 'ខ្ញុំ' ជាសន្ទស្សន៍បច្ចុប្បន្ន + 1 ។
  6. ផ្សេងទៀតជំរុញធាតុបច្ចុប្បន្នជាវ៉ិចទ័រវ៉ិចទ័រម្តងទៀតនិងបង្កើនចំនួនអប្បបរមាដែលអាចរកបាន។
  7. បោះពុម្ពវ៉ិចទ័រ។

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n) ដែល n ជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ s ។

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

អូ (n) ពីព្រោះយើងបានប្រើកន្លែងទំនេរដើម្បីរក្សាទុកតួអក្សរនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីបង្កើតជាចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    int min_avail = 1, pos_of_I = 0; 
  
    vector<int>v; 
  
    if (arr[0]=='I'){ 
        v.push_back(1); 
        v.push_back(2); 
        min_avail = 3; 
        pos_of_I = 1; 
    } 
    
    else{ 
        v.push_back(2); 
        v.push_back(1); 
        min_avail = 3; 
        pos_of_I = 0; 
    } 
  
    for (int i=1; i<arr.length(); i++){ 
        if (arr[i]=='I'){ 
            v.push_back(min_avail); 
            min_avail++; 
            pos_of_I = i+1; 
        } 
        
        else{ 
            v.push_back(v[i]); 
            for (int j=pos_of_I; j<=i; j++){ 
                v[j]++; 
            }
  
            min_avail++; 
        } 
    } 
  
    for (int i=0; i<v.size(); i++){ 
        cout << v[i] << " "; 
    }
    cout << endl; 
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

ចាវ៉ាកម្មវិធីដើម្បីបង្កើតចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

import java.util.*; 

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        int min_avail = 1, pos_of_I = 0;  
        
        ArrayList<Integer> al = new ArrayList<>(); 
        
        if (arr.charAt(0) == 'I'){  
            al.add(1);  
            al.add(2);  
            min_avail = 3;  
            pos_of_I = 1;  
        }  
        
        else{ 
            al.add(2); 
            al.add(1); 
            min_avail = 3;  
            pos_of_I = 0;  
        } 
        
        for (int i = 1; i < arr.length(); i++){ 
            if (arr.charAt(i) == 'I'){ 
                al.add(min_avail); 
                min_avail++; 
                pos_of_I = i + 1; 
            } 
            
            else{ 
                al.add(al.get(i)); 
                for (int j = pos_of_I; j <= i; j++) {
                    al.set(j, al.get(j) + 1); 
                }
                min_avail++; 
            } 
        } 
        
        for (int i = 0; i < al.size(); i++) {
            System.out.print(al.get(i) + " "); 
        }
        System.out.println();  
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

វិធីសាស្រ្ត 3

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមខ្សែអក្សរ s ។
  2. បង្កើតរចនាសម្ព័ន្ធទិន្នន័យជង់។
  3. ឆ្លងកាត់ខ្សែអក្សរហើយរុញសន្ទស្សន៍បច្ចុប្បន្ន +1 នៅក្នុងជង់នៅរាល់ការនិយាយឡើងវិញ។ Chcek ប្រសិនបើសន្ទស្សន៍បច្ចុប្បន្នស្មើនឹងប្រវែងនៃខ្សែអក្សរឬតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែគឺស្មើនឹង 'ខ្ញុំ' ខណៈពេលដែលជង់មិនទទេធ្វើឱ្យធាតុទាំងអស់នៃជង់នៅក្នុងខ្សែអក្សរ។
  4. បោះពុម្ពខ្សែអក្សរ។

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n) ដែល n ជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ s ។

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

អូ (n) ពីព្រោះយើងបានប្រើកន្លែងទំនេរដើម្បីរក្សាទុកតួអក្សរនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីបង្កើតជាចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    string result; 
  
    stack<int> stk; 
  
    for (int i = 0; i <= arr.length(); i++){ 
        stk.push(i + 1); 
  
        if (i == arr.length() || arr[i] == 'I'){ 
            
            while (!stk.empty()){ 
                result += to_string(stk.top()); 
                result += " "; 
                stk.pop(); 
            } 
        } 
    } 
  
    cout << result << endl;  
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

ចាវ៉ាកម្មវិធីដើម្បីបង្កើតចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

import java.util.*; 

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        String result = ""; 
  
        Stack<Integer> stk = new Stack<Integer>(); 
  
        for (int i = 0; i <= arr.length(); i++) { 
            stk.push(i + 1); 
  
            if (i == arr.length() || arr.charAt(i) == 'I') { 
                while (!stk.empty()) { 
                    result += String.valueOf(stk.peek()); 
                    result += " "; 
                    stk.pop(); 
                } 
            } 
        } 
  
        System.out.println(result);   
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

វិធីសាស្រ្ត 4

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមក ខ្សែអក្សរ s.
  2. ពិនិត្យមើលថាតើប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យធំជាងឬស្មើ ៩ បោះពុម្ព -9 និងត្រឡប់មកវិញ។
  3. ឆ្លងកាត់ខ្សែអក្សរដែលបានផ្តល់ឱ្យហើយពិនិត្យមើលថាតើសន្ទស្សន៍បច្ចុប្បន្នស្មើនឹងប្រវែងនៃខ្សែអក្សរឬតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែគឺស្មើនឹង 'I', ឆ្លងកាត់ម្តងទៀតពីសន្ទស្សន៍បច្ចុប្បន្ន - ពី 1 ដល់ 0 ហើយធ្វើបច្ចុប្បន្នភាពលទ្ធផលនៃសន្ទស្សន៍បច្ចុប្បន្ន + ១ ។
  4. ប្រសិនបើសន្ទស្សន៍បច្ចុប្បន្នធំជាងឬស្មើ ០ ហើយតួអក្សរបច្ចុប្បន្ននៅក្នុងខ្សែគឺស្មើនឹង is ខ្ញុំ I បំបែករង្វិលជុំ។
  5. បោះពុម្ពលទ្ធផល។

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n) ដែល n ជាប្រវែងនៃខ្សែអក្សរដែលបានផ្តល់ s ។

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

អូ (n) ពីព្រោះយើងបានប្រើកន្លែងទំនេរដើម្បីរក្សាទុកតួអក្សរនៃខ្សែអក្សរដែលបានផ្តល់ឱ្យ។

លេខកូដ

កម្មវិធី C ++ ដើម្បីបង្កើតជាចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

#include <bits/stdc++.h> 
using namespace std; 
  
string FormMinNumber(string arr){ 
    int n = arr.length(); 
  
    if(n >= 9){ 
        return "-1";
    }
  
    string result(n+1, ' ');  
  
    int count = 1;   
  
    for (int i = 0; i <= n; i++){
        
        if (i == n || arr[i] == 'I'){
            
            for (int j = i - 1 ; j >= -1 ; j--){ 
                result[j + 1] = '0' + count++; 
                
                if(j >= 0 && arr[j] == 'I'){ 
                    break; 
                }
            } 
        } 
    } 
    return result;   
} 
  
int main(){ 
    string s = "IDID";
    
    cout<<FormMinNumber(s); 
    
    return 0; 
}
13254

ចាវ៉ាកម្មវិធីដើម្បីបង្កើតចំនួនអប្បបរមាពីលំដាប់ដែលបានផ្តល់

import java.util.*; 

class MinNum{ 
      
    static String FormMinNumber(String arr){ 
        int n = arr.length(); 
  
        if (n >= 9){ 
            return "-1";
        }
  
        char result[] = new char[n + 1]; 
  
        int count = 1; 
  
        for (int i = 0; i <= n; i++){ 
            
            if (i == n || arr.charAt(i) == 'I'){ 
                
                for (int j = i - 1; j >= -1; j--){ 
                    result[j + 1] = (char) ((int) '0' + count++); 
                    
                    if (j >= 0 && arr.charAt(j) == 'I'){ 
                        break; 
                    }
                } 
            } 
        } 
        return new String(result);   
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        System.out.println(FormMinNumber(s)); 
    } 
}
13254