Баланд бардоштани сатҳи ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Akuna Capital
Sorting сатр

Мушкилоти зиёд кардани ҳалли коҳишёбандаи сатри Leetcode мегӯяд, ки ба мо а данд ҳамчун вуруд. Мо бояд вурудро тағир диҳем. Ё тавре ки савол мегӯяд, мо бояд онро ҷобаҷо кунем. Истилоҳи навъ дар ин ҷо маънои ҷудокунии аломатҳоро надорад. Мо сатрро бо тартиби мушаххас ҷобаҷо мекунем, то ҳарфҳоро бо тартиби қатъиян афзоишёфта то расидан ба аломати афзоянда. Ва вақте ки мо ба аломати калонтарин мерасем, мо ба тартиб додани ҳарфҳо бо тартиби қатъиян коҳишёфта аз калонтарин аломати мавҷуда оғоз мекунем. Мо бояд ин равандро то истифодаи тамоми аломатҳои сатр такрор кунем. Барои ҳамин, одатан, биёед аввал якчанд мисолро тафтиш кунем.

Баланд бардоштани сатҳи ҳалли Leetcode

s = "aaaabbbbcccc"
"abccbaabccba"

Шарҳ: Тавре ки дар боло ишора шуд, сатри мураттабшуда бояд намунаи муайянеро риоя кунад. Аввалан, аломатҳо бояд дар шакли қатъиян афзоянда ва сипас дар шакли камшавӣ бошанд. Натиҷа дар ин ҷо аз рӯи ҳамин тарз аст. Сатр бо a ва то пайдоиши як қатъиян афзоянда амал мекунад c. Пас бори дигар бо c бо хотима меёбад a. Раванд то такмил ёфтани ҳарфҳои сатри вуруд такрор карда мешавад.

s = "rat"
"art"

Шарҳ: Сатрҳои мураттабшуда (натиҷавӣ) аз хурдтарин аломат оғоз ёфта, то ҳамон даме, ки мо аломат надорем, амал мекунад.

Равиш барои зиёд кардани ҳалли камкунии сатри Leetcode

Масъалаи зиёд кардани сатри Leetcode Solution аз мо хоҳиш кард, ки сатри вуруди додашударо ба тарзи муайян ҷобаҷо кунем. Намуна дар боло муфассал тавсиф шудааст. Хулоса, аломатҳои вурудро аввал бо тартиби қатъиян зиёдшаванда ва сипас бо тартиби қатъиян камшударо то он даме ки ягон аломат боқӣ монад, тартиб диҳед. Ҳамин тавр, мо массиви басомадро месозем, то ҳисоби ҳар як аломатро дар вуруд нигоҳ дорем. Сипас, мо танҳо аз болои массиви басомад давр мезанем, то даме ки ҳамаи аломатҳои он тамом шаванд.

Доираи беруна то он даме ки дар массиви басомад аломатҳо (басомади калон аз 1) мавҷуд аст, кор мекунад. Доираи дохилӣ аломатро дар сатри муваққатӣ илова мекунад. Ин сатри муваққатӣ вобаста ба гардиш ба ҷавоб илова карда мешавад. Агар ин навбати аввал ҳангоми илова кардани сатри муваққатӣ бошад, он бо ҳамон тарзи афзоиш илова карда мешавад. Аммо агар ин гардиши ҷуфт бошад, пас сатр пеш аз замима барои посух додан баръакс карда мешавад. Пас аз тамом шудани аломатҳо дар массиви басомад. Алгоритм сатри ҷавоби навро ба функсияи зангзада бармегардонад.

рамз

Кодекси C ++ барои баланд бардоштани сатри Leetcode Solution

#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), зеро сатри нав ҳамон миқдор ҷойро мегирад, ки вуруд гирифтааст.