Լարային կոդերի լուծման նվազեցում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակունա Կապիտալ
դասավորում String

Stet Leetcode Solution- ի նվազեցման խնդիրն ասում է, որ մեզ տրվում է ա լարային որպես մուտքագրում: Մենք պետք է փոփոխենք մուտքագրումը: Կամ, ինչպես հարցն է նշում, մենք պետք է այն տեսակավորենք: Այստեղ տեսակավորում տերմինը չի նշանակում, որ ուղղակի տեսակավորվում են նիշերը: Մենք տողը կդասավորենք հատուկ հերթականությամբ ՝ նախ տառերը խիստ աճող հերթականությամբ դասավորելու համար, մինչև հասնենք աճող բնույթին: Եվ երբ հասնում ենք ամենամեծ նիշին, մենք սկսում ենք տառեր դասավորել խիստ նվազող հերթականությամբ ՝ սկսած ամենամեծ նիշից: Մենք պետք է կրկնենք այս գործընթացը մինչև ամբողջ լարի նիշերի օգտագործումը: Այսպիսով, ինչպես միշտ, եկեք նախ ստուգենք մի քանի օրինակներ:

Լարային կոդերի լուծման նվազեցում

s = "aaaabbbbcccc"
"abccbaabccba"

Բացատրություն. Ինչպես նշվեց վերևում, տեսակավորված տողը պետք է հետևի որոշակի օրինաչափության: Նախ, նիշերը պետք է լինեն խիստ աճող, այնուհետև ՝ նվազող օրինաչափությամբ: Արդյունքն այստեղ հետևում է նույն օրինակին: Լարը սկսվում է դրանից a և հետևում է խիստ աճող օրինակին մինչև c, Հետո նորից սկսած c ավարտվում է a. Գործընթացը կրկնվում է մինչև մուտքային տողի տառերը սպառվեն:

s = "rat"
"art"

Բացատրություն. Տեսակավորված (արդյունքի) տողը սկսվում է ամենափոքր նիշից և հետևում է նույն օրինակին, մինչև մենք չմնանք առանց նիշերի:

Լարային կոդերի լուծման նվազման մոտեցում

Leetcode Solution- ի նվազող տողի աճող խնդիրը խնդրեց մեզ որոշակի տիպով դասավորել տրված մուտքային տողը: Օրինակը մանրամասն նկարագրված է վերևում: Կարճ ասած, մուտքագրման նիշերը նախ դասավորեք խստորեն աճող կարգով և ապա խիստ նվազող կարգով, մինչև որ ոչ մի նիշ չմնա: Այսպիսով, մենք ստեղծում ենք հաճախականության զանգված ՝ յուրաքանչյուր նիշի քանակը մուտքագրման մեջ պահելու համար: Դրանից հետո մենք պարզապես մի օղակ ենք վարում հաճախականության զանգվածի վրա, մինչև դրա բոլոր նիշերը սպառվեն:

Արտաքին օղակն անցնում է այնքան ժամանակ, քանի դեռ հաճախականության զանգվածում կան նիշեր (1-ից ավելի հաճախականություն): Ներքին օղակը նիշը կցում է ժամանակավոր տողի: Այս ժամանակավոր տողը կախված է շրջադարձից պատյանին կցվում է: Եթե ​​ժամանակավոր լարն ավելացնելիս առաջին շրջադարձն է, այն ավելացվում է նույն աճող եղանակով: Բայց եթե դա հավասարաչափ շրջադարձ է, ապա պատասխանը կցելուց առաջ տողը շրջվում է: Հաճախականության զանգվածում նիշերի սպառումից հետո: Ալգորիթմը զանգի գործառույթին է վերադարձնում պատասխանների նոր տողը:

Կոդ

C ++ կոդ ՝ լարային 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

Լարի տողերի լուծման մեծացման ավելացման Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ ալգորիթմի արտաքին օղակն անցնում է մինչև նիշերի հաճախականության զանգվածում մնալը:

Տիեզերական բարդություն

ՎՐԱ), քանի որ նոր տողը տանում է նույն քանակությամբ տարածք, ինչքան վերցված է մուտքի կողմից: