Azalan String Leetcode Həllinin artırılması

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Paytaxt Akuna
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions çeşidləyici SimBaxılıb 86

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Azalan String Leetcode Solution-un artırılması problemi bizə verilən bir a olduğunu bildirir sim giriş olaraq. Girişi dəyişdirməliyik. Və ya sualda deyildiyi kimi, bunu çeşidləməliyik. Buradakı sort termini mütləq sadəcə simvolları sıralamaq demək deyil. Əvvəlcə artan xarakterə çatana qədər hərfləri ciddi şəkildə artan qaydada düzəltmək üçün ipi müəyyən bir qaydada sıralayacağıq. Ən böyük xarakterə çatdıqda, mövcud ən böyük simvoldan başlayaraq hərfləri ciddi şəkildə azalan qaydada düzəltməyə başlayırıq. Bu prosesi bütün simvol simvolları istifadə olunana qədər təkrarlamalıyıq. Həmişə olduğu kimi əvvəlcə bir neçə nümunəni yoxlayaq.

Azalan String Leetcode Həllinin artırılmasıPin

s = "aaaabbbbcccc"
"abccbaabccba"

İzahat: Yuxarıda göstərildiyi kimi sıralanmış sətir müəyyən bir nümunəni izləməlidir. Əvvəlcə simvollar ciddi şəkildə artan və sonra azalma şəklində olmalıdır. Buradakı məhsul eyni nümunəni izləyir. Simli ilə başlayır a və qədər ciddi şəkildə artan bir nümunəni izləyir c. Sonra yenidən başlayır c ilə bitir a. Prosedur giriş sətirinin hərfləri bitənə qədər təkrarlanır.

s = "rat"
"art"

İzahat: Sıralanmış (nəticələnən) sətir ən kiçik simvoldan başlayır və heç bir simvol qalmayana qədər eyni qaydada hərəkət edir.

Azaldılmış Simli Leetcode həllinin artırılması üçün yanaşma

Azalan String Leetcode Solution-un artırılması problemi, verilən giriş sətrini müəyyən bir şəkildə sıralamağımızı istədi. Nümunə yuxarıda ətraflı təsvir edilmişdir. Qısaca, giriş simvollarını əvvəlcə ciddi şəkildə artan qaydada və sonra heç bir simvol qalmayana qədər ciddi şəkildə azalan qaydada düzəldin. Beləliklə, girişdə hər bir simvolun sayını saxlamaq üçün bir tezlik massivi yaradırıq. Sonra, sadəcə bütün frekanslar tükənənə qədər tezlik massivi üzərində bir döngə aparırıq.

Xarici döngə tezlik massivində simvollar (tezlik 1-dən çox) olana qədər işləyir. İç döngə xarakteri müvəqqəti bir sətirdə əlavə edir. Bu müvəqqəti simli növbəyə görə cavaba əlavə olunur. Müvəqqəti simli əlavə edildikdə ilk növbədirsə, eyni artan qaydada əlavə olunur. Ancaq bərabər bir növbədirsə, cavab vermək üçün əlavə etmədən əvvəl simli geri çevrilir. Tezlik massivindəki simvolların tükənməsindən sonra. Alqoritm, zəng edən funksiyasına yeni bir cavab simli qaytarır.

Kodu

Azaldılmış Simli Leetcode həllinin artırılması üçün C ++ kodu

#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

Azalan String Leetcode Çözümünü artırmaq üçün Java Kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), alqoritmdə xarici dövr olduğundan, simvollar tezlik massivində qalana qədər işləyir.

Kosmik Mürəkkəblik

O (N), çünki yeni sətir girişin götürdüyü qədər yer tutur.

Crack Sistemi Dizayn Müsahibələri
Translate »
1