Sıralı növbə LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur AmazonBaxılıb 52

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.

Problem bəyanat

Sıralı növbə LeetCode Həlli – Sizə sətir verilir s və tam ədəd k. Birincilərdən birini seçə bilərsiniz k məktubları s və onu sətirin sonuna əlavə edin.

Qayıtmaq qeyd olunan addımı istənilən sayda hərəkəti tətbiq etdikdən sonra əldə edə biləcəyiniz leksikoqrafik cəhətdən ən kiçik simli.

Input: s = "cba", k = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1st character 'b' to the end, obtaining the final result "acb".

Izahat

İki mümkün hal:

K==1,

bu halda verilmiş əməliyyatları yerinə yetirməklə verilmiş sətirin fırlanmalarını alırıq. Deməli, cavab belə olacaq leksikoqrafik cəhətdən bütün fırlanmalar arasında ən kiçik sətir.

Məsələn: s = "dcba"

– Öndən d çıxarın və arxaya əlavə edin. s = "cbad".

– Öndən c çıxarın və arxaya əlavə edin. s = "badc"

– Öndən b çıxarın və arxadan əlavə edin. s = "adcb"

– Öndən a çıxarın və arxadan əlavə edin. s = "dcba"

Bütün fırlanan sətirlər arasında s=”adcb” leksikoqrafik cəhətdən ən kiçikdir.

K>=2,

Bu maraqlı bir haldır. Burada bir neçə əməliyyat yerinə yetirərək istənilən elementi dəyişdirə bilirik. Aşağıdakı nümunəyə baxın

Məsələn: bacd

İlk iki simvolu əvəz edək, yəni b və a

– Bir seçin və arxaya itələyin. s=”bcda”

– b seçin və arxaya itələyin. s = "cdab"

– c seçin və arxaya itələyin. s = "dabc"

– d seçin və arxaya itələyin. s = "abcd"

Müşahidə edə bilərik ki, bacd hərfinin ilk iki hərfi indi abcd ilə dəyişdirilir. İstənilən iki elementi əvəz edə bildiyimizə görə, bu o deməkdir ki, bütöv bir sətri çeşidləmək mümkündür, sadəcə bir neçə əməliyyat tətbiq etmək olar. Beləliklə, bu halda cavab sıralanmış sətir olacaqdır.

Birincisi, bu simli fırlanmadır.
12345 -> 23451 -> 34512 -> 45123 -> 51234 (Aydınlaşdırmaq üçün hərflər əvəzinə rəqəmlərdən istifadə edilmişdir.)

If K == 1, biz yalnız bütün sətri döndərə bilərik. Var S.length müxtəlif dövlətlər və biz leksikoqrafik cəhətdən ən kiçik sətri qaytarırıq.

If K > 1, bu o deməkdir ki, biz edə bilərik:

  1. bütün simi döndərin,
  2. ilk hərfdən başqa bütün sətri çevirin.
    012345 -> 023451 -> 034512 -> 045123 -> 051234

Dönə bilərik i+1başlanğıc üçün böyük hərf (metod 1),
sonra fırladın isona qədər böyük hərf (2-ci üsul).
2XXX01 -> XXX012

Bu şəkildə edə bilərik bubble sort bütün simli leksikoqrafik cəhətdən.
Belə ki, yalnız sıralanır simli qayıt.

Kodu

Sifarişli növbə üçün C++ kodu

class Solution {
public:
    string orderlyQueue(string S, int K) {
        if (K > 1) {
            sort(S.begin(), S.end());
            return S;
        }
        string res = S;
        for (int i = 1; i < S.length(); i++)
            res = min(res, S.substr(i) + S.substr(0, i));
        return res;
    }
};

Sıralı növbə üçün Java kodu

class Solution {
     public String orderlyQueue(String S, int K) {
        if (K > 1) {
            char S2[] = S.toCharArray();
            Arrays.sort(S2);
            return new String(S2);
        }
        String res = S;
        for (int i = 1; i < S.length(); i++) {
            String tmp = S.substring(i) + S.substring(0, i);
            if (res.compareTo(tmp) > 0) res = tmp;
        }
        return res;
    }
}

Sıralı növbə üçün Python kodu

class Solution:
    def orderlyQueue(self, S, K):
        return "".join(sorted(S)) if K > 1 else min(S[i:] + S[:i] for i in range(len(S)))

Nizamlı Queue LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (nlogn)

Kosmik Mürəkkəblik

O (1)

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