ලබා දී ඇති අනුපිළිවෙලින් අවම අංකය සාදන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් ගෝල්ඩ්මන් සැක්ස්
අරා අඩුක්කුව String

පටුන

ගැටළු ප්රකාශය

“ලබා දී ඇති අනුපිළිවෙලින් අවම අංකයක් පෝරමය මඟින් ඔබට ලබා දී ඇති බව සඳහන් වේ පේළියකි 'I' අක්ෂර රටාවක් නිරූපණය කරන දිග / ප්‍රමාණය n, එනම් වැඩි වීම සහ 'D' එනම් අඩු වීම පමණි. 1-9 සිට අද්විතීය ඉලක්කම් සහිතව දී ඇති රටාව සඳහා අවම අංකය මුද්‍රණය කරන්න.

උදාහරණයක් වශයෙන් -

ලබා දී ඇති අනුපිළිවෙලින් අවම අංකය සාදන්න

උදාහරණයක්

s = "DD"
3 2 1

පැහැදිලි කිරීම: ඉලක්කම් negative ණ විය නොහැකි බැවින්, අපි පළමු ඉලක්කම් ලෙස 3 ක් තෝරාගෙන ඉදිරියට එන ඉලක්කම් අඩු කරමින් සිටිමු.

s = "DIDI"
2 1 4 3 5

1 ක්රමය

ඇල්ගොරිතම

  1. නූලක් ආරම්භ කරන්න.
  2. දී ඇති නූල් හරහා ගමන් කර, නූල් වල වත්මන් අක්‍ෂරය 'I' ට සමාන දැයි පරීක්ෂා කරන්න, දී ඇති නූලෙහි 'D' ට සමාන ඊළඟ අඛණ්ඩ අක්ෂර ගණන ගණනය කරන්න.
  3. 'I' අක්ෂරය නූලෙහි පළමු අක්‍ෂරය නම්, වැඩිවන රටාව 1 සිට ආරම්භ කර ඊළඟ ඉලක්කම් මුද්‍රණය කරන්න.
  4. දී ඇති නූලෙහි 'D' ට සමාන ඊළඟ අඛණ්ඩ අක්ෂර සඳහා අඩු වන රටාව මුද්‍රණය කරන්න.
  5. ඒ හා සමානව, නූල් වල වත්මන් අක්‍ෂරය 'ඩී' ට සමාන දැයි පරීක්ෂා කරන්න, 'ඩී' අක්ෂරය නූලෙහි පළමු අක්‍ෂරය දැයි පරීක්ෂා කරන්න, නූලෙහි ඇති සියලුම 'ඩී' ගණන් කර රටාව මුද්‍රණය කරන්න.
  6. නැතිනම් අවසාන ප්‍රවේශය 1 කින් අඩු කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n) මෙහි n යනු දී ඇති නූල් වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව

O (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. නූලක් ආරම්භ කරන්න.
  2. වර්ගයේ නිඛිලයක දෛශිකයක් සාදන්න.
  3. දී ඇති නූලෙහි පළමු අක්‍ෂරය 'I' දැයි පරීක්ෂා කර, දෛශිකයේ 1 සහ 2 තල්ලු කර ලබා ගත හැකි අවම අංකය 3 ලෙසත්, 'I' හි පිහිටීම 1 ලෙසත් සකසන්න.
  4. දෛශිකයේ 2 සහ 1 තල්ලු කර ලබා ගත හැකි අවම අංකය 3 ලෙසත්, 'I' හි පිහිටීම 0 ලෙසත් සකසන්න.
  5. 1 සිට ඇරඹෙන නූල හරහා ගමන් කර දී ඇති නූල් වල වත්මන් අක්ෂරය 'I' දැයි පරීක්ෂා කර, දෛශිකයේ ඇති අවම අංකය තල්ලු කරන්න, පවතින අවම අංකය වැඩි කර 'I' හි පිහිටීම වත්මන් දර්ශකය + 1 ලෙස යාවත්කාලීන කරන්න.
  6. වෙනත් ආකාරයකින් දෛශිකයේ දෛශිකයේ වත්මන් මූලද්‍රව්‍යය නැවත තල්ලු කර ලබා ගත හැකි අවම සංඛ්‍යාව වැඩි කරන්න.
  7. දෛශිකය මුද්‍රණය කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n) මෙහි n යනු දී ඇති නූල් වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව

O (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. නූලක් ආරම්භ කරන්න.
  2. තොග දත්ත ව්‍යුහයක් සාදන්න.
  3. නූල හරහා ගමන් කර සෑම පුනරාවර්තනයකදීම වත්මන් දර්ශකය + 1 තොගයේ තල්ලු කරන්න. වත්මන් දර්ශකය නූලෙහි දිගට සමාන නම් හෝ නූල් වල වත්මන් අක්‍ෂරය 'I' ට සමාන නම් Chcek කරන්න, තොගය හිස් නොවන්නේ නම්, නූලක ඇති සියලුම අංග සමපාත වේ.
  4. නූල මුද්‍රණය කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n) මෙහි n යනු දී ඇති නූල් වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව

O (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. ආරම්භ කරන්න a පේළියකි s.
  2. දී ඇති නූල් වල දිග 9 ට වඩා වැඩි හෝ සමාන දැයි පරීක්ෂා කරන්න, මුද්‍රණය -1, සහ ආපසු.
  3. දී ඇති නූල හරහා ගමන් කර වත්මන් දර්ශකය නූලෙහි දිගට සමාන ද නැතිනම් නූල් වල වත්මන් අක්‍ෂරය 'I' ට සමාන ද යන්න පරීක්ෂා කරන්න, වත්මන් දර්ශකයේ සිට 1 දක්වා 0 දක්වා ගමන් කර වත්මන් දර්ශකයේ ප්‍රති result ලය යාවත්කාලීන කරන්න + 1.
  4. වත්මන් දර්ශකය 0 ට වඩා වැඩි හෝ සමාන නම් සහ නූල් වල වත්මන් අක්ෂරය 'I' ට සමාන නම්, ලූපය බිඳ දමන්න.
  5. ප්‍රති result ලය මුද්‍රණය කරන්න.

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n) මෙහි n යනු දී ඇති නූල් වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව

O (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