අඩු වන නූල් ලීට්කෝඩ් විසඳුම වැඩි කිරීම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ අකූනා කැපිටල්
වර්ග කිරීම String

අඩු වන නූල් ලීට්කෝඩ් විසඳුම වැඩිවීමේ ගැටළුව පවසන්නේ අපට ලබා දී ඇති බවයි පේළියකි ආදානය ලෙස. අපි ආදානය වෙනස් කළ යුතුයි. නැතහොත් ප්‍රශ්නය පවසන පරිදි, අප එය වර්ග කළ යුතුය. මෙහි වර්ග කිරීම යන වචනයේ තේරුම හුදෙක් අක්ෂර වර්ග කිරීම නොවේ. අපි වැඩි වන අක්ෂරයට ළඟා වන තෙක් අකුරු තදින් වැඩි කරන අනුපිළිවෙලට නිශ්චිත අනුපිළිවෙලකට වර්ග කරමු. අප විශාලතම චරිතය කරා ළඟා වන විට, ලබා ගත හැකි විශාලතම අක්‍ෂරයෙන් පටන් ගෙන අකුරු තදින් අඩු කරන පිළිවෙලට සකස් කිරීමට අපි පටන් ගනිමු. සම්පූර්ණ නූලෙහි අක්‍ෂර භාවිතා වන තුරු අපට මෙම ක්‍රියාවලිය නැවත සිදු කළ යුතුය. ඉතින් සුපුරුදු පරිදි, පළමුව අපි උදාහරණ කිහිපයක් පරීක්ෂා කරමු.

අඩු වන නූල් ලීට්කෝඩ් විසඳුම වැඩි කිරීම

s = "aaaabbbbcccc"
"abccbaabccba"

පැහැදිලි කිරීම: ඉහත සඳහන් කළ පරිදි වර්ග කළ නූලට යම් රටාවක් අනුගමනය කළ යුතුය. පළමුව, අක්ෂර තදින් වැඩිවන රටාවකින් හා පසුව අඩු වන රටාවෙන් විය යුතුය. මෙහි ප්‍රතිදානය එකම රටාවක් අනුගමනය කරයි. නූල ආරම්භ වේ a සහ තෙක් දැඩි ලෙස වැඩි වන රටාවක් අනුගමනය කරයි c. ඉන්පසු නැවතත් ආරම්භ වේ c අවසන් වේ a. ආදාන නූලෙහි අකුරු අවසන් වන තුරු ක්‍රියාවලිය නැවත සිදු වේ.

s = "rat"
"art"

පැහැදිලි කිරීම: වර්ග කළ (ප්‍රති ant ල) නූල කුඩාම අක්‍ෂරයෙන් ආරම්භ වන අතර අපට අක්ෂර නොමැති වන තෙක් එකම රටාව අනුගමනය කරයි.

අඩු වන නූල් ලීට්කෝඩ් විසඳුම සඳහා ප්‍රවේශය

අඩු වන නූල් ලීට්කෝඩ් විසඳුම වැඩි කිරීමේ ගැටළුව අප විසින් ලබා දී ඇති ආදාන නූල යම් ආකාරයකින් වර්ග කිරීමට ඉල්ලා සිටියේය. රටාව ඉහත විස්තරාත්මකව විස්තර කර ඇත. කෙටියෙන් කිවහොත්, ආදාන අක්ෂර පළමුව තදින් වැඩි කරන අනුපිළිවෙලට සකසන්න, ඉන්පසු අක්ෂර ඉතිරි නොවන තෙක් තදින් අඩු කරන්න. එබැවින්, ආදානයේ එක් එක් අක්‍ෂර ගණන ගබඩා කිරීම සඳහා අපි සංඛ්‍යාත අරාවක් නිර්මාණය කරමු. ඉන්පසුව අපි සංඛ්‍යාත අරාව හරහා ලූපයක් ධාවනය කරන්නේ එහි ඇති සියලුම අක්ෂර අවසන් වන තුරු ය.

සංඛ්‍යාත අරාවෙහි අක්ෂර (සංඛ්‍යාතය 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

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

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

මත), ඇල්ගොරිතමයේ පිටත ලූපය නිසා, සංඛ්‍යාත අරාවෙහි අක්ෂර ඉතිරි වන තෙක් ක්‍රියාත්මක වේ.

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

මත), මක්නිසාද යත් නව නූල ආදානය විසින් ගන්නා ලද ඉඩ ප්‍රමාණයට සමාන වන බැවිනි.