அதிகரித்து வரும் சரம் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அகுனா மூலதனம்
வரிசையாக்க சரம்

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

அதிகரித்து வரும் சரம் லீட்கோட் தீர்வு

s = "aaaabbbbcccc"
"abccbaabccba"

விளக்கம்: வரிசைப்படுத்தப்பட்ட சரத்திற்கு மேலே குறிப்பிட்டபடி ஒரு குறிப்பிட்ட முறையைப் பின்பற்ற வேண்டும். முதலில், எழுத்துக்கள் கண்டிப்பாக அதிகரிக்கும் வடிவத்திலும் பின்னர் குறைக்கும் வடிவத்திலும் இருக்க வேண்டும். இங்கே வெளியீடு அதே முறையைப் பின்பற்றுகிறது. சரம் தொடங்குகிறது a மற்றும் வரை கண்டிப்பாக அதிகரிக்கும் முறையைப் பின்பற்றுகிறது c. பின்னர் மீண்டும் தொடங்குகிறது c உடன் முடிகிறது a. உள்ளீட்டு சரத்தின் எழுத்துக்கள் தீர்ந்துபோகும் வரை செயல்முறை மீண்டும் நிகழ்கிறது.

s = "rat"
"art"

விளக்கம்: வரிசைப்படுத்தப்பட்ட (விளைவாக) சரம் மிகச்சிறிய எழுத்துடன் தொடங்குகிறது மற்றும் எழுத்துக்கள் எதுவுமில்லாமல் இருக்கும் வரை அதே முறையைப் பின்பற்றுகிறது.

அதிகரிக்கும் சரம் லீட்கோட் தீர்வை அதிகரிப்பதற்கான அணுகுமுறை

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

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

குறியீடு

சரம் லீட்கோட் தீர்வை அதிகரிப்பதற்கான சி ++ குறியீடு

#include <bits/stdc++.h>
using namespace std;

string sortString(string s) {
    vector<int> frq(26, 0);
    for(auto x: s)
        frq[x-'a']++;
    int par = false;
    string ans = "";
    bool can = false;
    do{
        can = false;
        string ss = "";
        for(int i=0;i<26;i++)
            if(frq[i]){
                ss += (char)(i+'a');
                frq[i]--;
                can |= (frq[i] > 0);
            }
        if(par == true)
            reverse(ss.begin(), ss.end());
        par ^= 1;
        ans += ss;
    } while(can);
    return ans;
}

int main()
{
    cout<<sortString("aaaabbbbcccc");
}
abccbaabccba

சரம் லீட்கோட் தீர்வை அதிகரிப்பதற்கான ஜாவா குறியீடு

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String sortString(String s) {
        ArrayList<Integer> frq = new ArrayList<Integer>();
        for(int i=0;i<26;i++)
            frq.add(0);
        for(int i=0;i<s.length();i++)
            frq.set(s.charAt(i)-'a', frq.get(s.charAt(i)-'a')+1);
        int par = 0;
        StringBuilder ans = new StringBuilder();
        boolean can = false;
        do{
            can = false;
            StringBuilder ss = new StringBuilder();
            for(int i=0;i<26;i++)
                if(frq.get(i)>0){
                    ss.append((char)(i+'a'));
                    frq.set(i, frq.get(i)-1);
                    can |= (frq.get(i) > 0);
                }
            if(par == 1)
                ss.reverse();
            par ^= 1;
            ans.append(ss);
        } while(can == true);
        return ans.toString();
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(sortString("aaaabbbbcccc"));
  }
}
abccbaabccba

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

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

ஓ (என்), வழிமுறையின் வெளிப்புற வளையம் என்பதால், அதிர்வெண் வரிசையில் எழுத்துக்கள் இருக்கும் வரை இயங்கும்.

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

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