स्ट्रिक्ट लेइकोड समाधान घटाउँदै


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अकुना क्यापिटल
क्रमबद्ध घागो

स्ट्रिंग लेटकोड समाधान बृद्धि हुँदै गइरहेको समस्या बताउँछ कि हामीलाई एक दिइएको छ string इनपुटको रूपमा। हामीले इनपुट परिमार्जन गर्न आवश्यक छ। वा प्रश्नले भन्छ, हामीले यसलाई क्रमबद्ध गर्नु आवश्यक छ। यहाँ शब्द सर्ट गर्नु भनेको केवल अक्षरहरू क्रमबद्ध गर्नु आवश्यक छैन। हामी स्ट्रिंगलाई क्रमबद्ध क्रममा बढ्दो क्रममा पहिले व्यवस्थित वर्णहरूको क्रममा क्रमबद्ध गर्नेछौं जबसम्म हामी बढ्दो चरित्रमा पुग्दैनौं। र जब हामी सबैभन्दा ठूलो चरित्रमा पुग्छौं, हामी कडाईमा घट्ने क्रममा अक्षरहरू मिलाउन थाल्छौं सब भन्दा ठूला चरित्रको साथ सुरू गरेर। हामीले पूर्ण स्ट्रि's्ग क्यारेक्टरहरू प्रयोग नगरे सम्म यो प्रक्रिया दोहोर्याउनु पर्छ। सामान्यको रूपमा, अब केही उदाहरणहरू जाँचौं।

स्ट्रिक्ट लेइकोड समाधान घटाउँदै

s = "aaaabbbbcccc"
"abccbaabccba"

स्पष्टीकरण: क्रमबद्ध क्रमबद्ध स्ट्रिंगले केहि ढाँचा पछ्याउनु पर्छ। पहिले, क्यारेक्टरहरू कडाइका साथ बढिरहेको ढाँचामा र त्यसपछि घट्ने बान्कीमा हुनुपर्दछ। यहाँ आउटपुटले उही बानी पछ्याउँछ। स्ट्रिंग सुरु हुन्छ a र कडाई बढ्दै गएको ढाँचा सम्म पछ्याउँदछ c। त्यसो भए फेरि सुरू गरेर c संग समाप्त हुन्छ a. प्रक्रिया इनपुट स्ट्रि until्गको अक्षरहरू समाप्त नभएसम्म दोहोरिन्छ।

s = "rat"
"art"

स्पष्टीकरण: क्रमबद्ध (नतीजा) स्ट्रिंग सबैभन्दा सानो क्यारेक्टरबाट सुरू हुन्छ र उही शैलीलाई पछ्याउँदछ जब सम्म हामी कुनै अक्षरहरू छोड्दैनौं।

बढ्दो घट्दो स्ट्रिंगको लेटकोड समाधानको लागि दृष्टिकोण

समस्या बढ्दो घट्दो स्ट्रिंग लेटकोड समाधानले हामीलाई एक निश्चित फेशनमा दिइएको इनपुट स्ट्रि sort सॉर्ट गर्न सोध्यो। ढाँचा माथि वर्णन गरिएको छ। संक्षिप्तमा, इनपुट वर्णहरू क्रमशः बढ्दो क्रममा क्रमबद्ध गर्नुहोस् र त्यसपछि कडाई घट्दै क्रममा जब कुनै वर्णहरू रहदैन। त्यसो भए, हामी इनपुटमा प्रत्येक वर्णको गणना भण्डारण गर्न फ्रिक्वेन्सी एरे सिर्जना गर्दछौं। त्यसो भए हामी केवल फ्रिक्वेन्सी एरेमा लूप चल्छौं जबसम्म यसमा सबै क्यारेक्टरहरू थकित हुँदैनन्।

बाहिरी लूप चल्दछ जबसम्म त्यहाँ आवृत्ति एरेमा वर्णहरू (१ भन्दा ठूलो फ्रिक्वेन्सी) हुन्छ। अस्थायी स्ट्रि inमा भित्री लूपले क्यारेक्टर थप गर्दछ। यो अस्थायी स्ट्रि the मोडमा निर्भर गर्दै जवाफमा जोडिएको छ। यदि यो पहिलो पालो हो जब अस्थायी स्ट्रि added थप भईरहेको छ, यो उही बढ्दो तरीकामा थपियो। तर यदि यो एक पनी पालो हो भने, तब स्ट्रि जवाफ दिनुभन्दा पहिले उल्टाइन्छ। आवृत्ति एरेमा वर्णहरूको थकान पछि। एल्गोरिथ्मले कलर प्रकार्यलाई नयाँ जवाफ स्ट्रिंग दिन्छ।

कोड

C ++ कोड स्ट्रि Le्ग Leetcode समाधान बढाउँदाको लागि

#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

जटिलता विश्लेषण

समय जटिलता

O (N), एल्गोरिथ्ममा बाह्य लुप भएकोले, वर्णहरू फ्रिक्वेन्सी एरेमा बाँकी नआएसम्म चल्दछ।

ठाउँ जटिलता

O (N), किनभने नयाँ स्ट्रिंगले इन्पुटले लिने जस्तो खाली स्थान लिन्छ।