Повећавање опадајућег низа Леетцоде решење


Ниво тешкоће Лако
Често питани у Акуна Цапитал
сортирање низ

Проблем Повећавање и смањивање низа Леетцоде Солутион наводи да смо добили а низ као улаз. Морамо да изменимо унос. Или како питање стоји, морамо то да сортирамо. Израз сортирање овде не значи нужно једноставно сортирање знакова. Низ ћемо сортирати по одређеном редоследу тако што ћемо прво сложити слова у строго растућем редоследу док не дођемо до знака који се повећава. И док достижемо највећи лик, почињемо да слажемо слова у строго умањеном редоследу, почевши од највећег доступног знака. Морамо понављати овај поступак док се не користе знакови читавог низа. Као и обично, хајде да прво проверимо неколико примера.

Повећавање опадајућег низа Леетцоде решење

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

Анализа сложености

Сложеност времена

НА), пошто спољна петља у алгоритму ради све док знакови не остану у фреквенцијском пољу.

Сложеност простора

НА), јер нови низ заузима исту количину простора колико је заузео улаз.