Leetcode жолының төмендеуін азайту


Күрделілік дәрежесі оңай
Жиі кіреді Акуна астанасы
Сұрыптау String

Leetcode Solution-ті азайту мәселесі бізге а жол кіріс ретінде. Біз енгізуді өзгертуіміз керек. Немесе сұрақта айтылғандай, біз оны сұрыптауымыз керек. Мұндағы сұрыптау термині символдарды жай сұрыптауды білдірмейді. Біз жолды белгілі бір ретпен сұрыптаймыз, алдымен өсіп жатқан таңбаға жеткенше әріптерді қатаң түрде өсіп отырады. Біз ең үлкен таңбаға қол жеткізгенде, қол жетімді ең үлкен таңбадан бастап әріптерді қатаң кему ретімен орналастыра бастаймыз. Біз бұл процесті жолдың барлық таңбалары қолданылғанша қайталауымыз керек. Әдеттегідей, алдымен бірнеше мысалды тексеріп көрейік.

Leetcode жолының төмендеуін азайту

s = "aaaabbbbcccc"
"abccbaabccba"

Түсініктеме: Жоғарыда айтылғандай, сұрыпталған жол белгілі бір үлгі бойынша жүруі керек. Біріншіден, таңбалар қатаң түрде өсетін, содан кейін кішірейетін үлгіде болуы керек. Мұндағы өнім дәл сол заңдылық бойынша жүреді. Жол басталады a дейін дейін қатаң түрде өсетін үлгі бойынша жүреді c. Содан кейін қайтадан басталады c аяқталады a. Процесс енгізу жолының әріптері таусылғанша қайталанады.

s = "rat"
"art"

Түсініктеме: сұрыпталған (нәтижелі) жол ең кіші таңбадан басталып, біз ешқандай таңбасыз қалғанға дейін сол сызба бойынша жүреміз.

String Leetcode Solution-ті азайтуды арттыру тәсілі

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 коды. Leetcode шешімі

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), өйткені жаңа жол кіріспен бірдей кеңістікті алады.