Partition Labels

+10

Küçük harflerden oluşan bir s dizgesi alırsın. Her harf yalnızca tek bir parçada yer alacak şekilde, dizgeyi olabildiğince çok ardışık parçaya böl: Bir harf bir parçada görünüyorsa, tüm kopyaları o parçada olmalıdır. Parçaların uzunluklarını soldan sağa döndür.

Fonksiyon

partitionLabels(s: string) → integer-array

sstring: kesilecek dizge, yalnızca küçük harfler
Döndürürinteger-array: soldan sağa her bir parçanın uzunluğu

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca küçük İngilizce harfleri içerir.
The parçalar sıralarını korur ve birlikte s'nin tamamını oluşturur, bu nedenle uzunlukları toplamı s.length değerine eşittir.

Örnekler

Girdi: s = "abacdcefe"
Çıktı: [3, 3, 3]
Açıklama: a'lar 0 ve 2. konumlarda, c'ler 3 ve 5. konumlarda, e'ler ise 6 ve 8. konumlarda bulunur; bu nedenle kesimler aba'dan sonra ve cdc'den sonra yapılır. Her bölüm aynı harfle başlayıp bittiği için hiçbir bölüm tekrar kesilemez.

Gönderirken +14 gizli test

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir kesme işlemine yalnızca harfin kesme noktasının iki tarafında da bulunmadığı yerlerde izin verilir ve en iyi yanıt bu tür her yerde kesme yapar. Her yeri diziyi yeniden tarayarak sınamak ikinci dereceden zaman alır. Önce her harfin son konumunu kaydedin; ardından soldan sağa yapılan tek bir geçiş, her kesme noktasını bulur, çünkü bir parça, içindeki her harfin son kopyasına kadar uzanmalıdır.

Her boşluğu test et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Komşu harfler arasında n-1 boşluk vardır. Bir boşlukta kesmeye yalnızca kesimin her iki tarafında da aynı harf yoksa izin verilir; çünkü kesimle bölünen bir harf iki parçada yer alır. İzin verilen her yerde kesmek, en fazla sayıda parça oluşturur. İzin verilen iki komşu kesim arasındaki bir parçayı ele alalım: bu parçadaki harflerin hiçbiri sol kesimin solunda veya sağ kesimin sağında bulunmaz; dolayısıyla bu harflerin tüm kopyaları parçanın içindedir ve parça geçerlidir. Ayrıca geçerli herhangi bir yanıt yalnızca izin verilen boşluklarda kesim yapabilir; bu nedenle hiçbir yanıt daha fazla parça oluşturamaz.

Bu yüzden her boşluğu kontrol et: solundaki ve sağındaki harfleri topla ve iki kümede ortak harf yoksa kes. abacdcefe içinde aba sonrasındaki boşluğun solunda a ve b, sağında ise c, d, e ve f vardır. Ortak harf yoktur, bu yüzden kesersin. ab sonrasındaki boşluğun iki tarafında da a harfi vardır, bu yüzden kesmezsin.

Her kontrolde dizenin tamamı okunur ve n-1 boşluk bulunduğundan, işlem yaklaşık n² harf okuması gerektirir. 50.000 harfle bu, 2.5 × 10^9 okumadır; en büyük testler için çok yavaştır.

Algoritma

Geçerli parçanın başladığı yer olan start = 0 değerini ayarla.
1'den n-1'e kadar her boşluk cut için (s[cut] öğesinin hemen önündeki boşluk), s[0..cut-1] içindeki harfleri ve s[cut..n-1] içindeki harfleri işaretle.
Her iki tarafta da işaretlenmiş ortak bir harf yoksa, cevaba cut-start değerini ekle ve start = cut değerini ayarla.
Döngüden sonra son parçayı, yani n-start değerini ekle.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Her harfin aralığını birleştir

Sezgi

Her harfi, ilk konumundan son konumuna kadar uzanan bir aralık olarak düşün. Bir harfi içeren bir parça, o aralığın tamamını kapsamalıdır. Bu nedenle aralıkları çakışan iki harf aynı parçada yer almalıdır ve çakışma yayılır: a, b ile; b de c ile çakışıyorsa, üçü de aynı parçada yer alır.

Bu, aralıkları birleştirme problemidir. Tek bir geçişte her harfin ilk ve son konumunu kaydet. Ardından aralıkları başlangıç konumlarına göre sırayla ele al ve çakışanları birleştir. Birleştirilen her blok bir parçadır ve bloklar arasındaki boşluklar, izin verilen kesim noktalarının tam olarak kendisidir. Aralıkları sıralama yapmadan başlangıç konumlarına göre sırayla elde edebilirsin: dize üzerinde tekrar ilerle ve bir harfin aralığını, ilk konumunda bulunduğunda ele al.

codingisfun içinde aralıklar sırayla c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] ve u [9, 9] şeklindedir. İlk üçü tek başına kalır. i harfinden itibaren her aralık, n harfinin bittiği 10 konumunda veya daha önce başlar; bu nedenle [3, 10] aralığında birleşirler ve 8 harften oluşan bir parça meydana getirirler.

Dizede en fazla 26 farklı harf bulunabilir; dolayısıyla en fazla 26 aralık vardır ve ilk ve son konum tabloları sabit boyutludur.

Algoritma

s üzerinde tek bir geçişte, her harfin ilk ve son konumlarını first ve last olarak kaydedin.
s üzerinde tekrar ilerleyin. i konumu harfinin ilk konumu olduğunda, o harfin [i, last] aralığı başlangıç sırasına göre sıradaki aralıktır.
Aralık, mevcut bloğun end değerinden sonra başlıyorsa end-start+1 uzunluğundaki bloğu kapatın ve i konumunda yeni bir blok başlatın.
Her iki durumda da end = max(end, last) olarak ayarlayın.
Son bloğu kapatın ve uzunlukları döndürün.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Her parçayı son harfine kadar büyütün

Sezgi

İlk konumlara hiç gerek yok. Dizeyi soldan sağa oku ve geçerli parçadaki herhangi bir harfin en sağdaki son konumu olan end değerini tut. i konumundaki harfi okuduğunda, o harfin son kopyası da bu parçada olmalıdır; bu nedenle daha ilerideyse end değerini last[s[i]] olarak güncelle.

i, end değerine ulaştığında, bu parçada okuduğun her harfin son kopyası i konumunda ya da öncesindedir. Hiçbir harf i sonrasındaki sınırı aşmaz; dolayısıyla oradan kesmek mümkündür. Uzunluğu end-start+1 olan parçayı kapat ve yeni parçaya i+1 konumundan başla.

İlk fırsatta kesmek neden doğru açgözlü seçimdir? i, end değerine ulaşmadan önce parçadaki bir harfin hâlâ daha ileride bir kopyası vardır; bu yüzden daha erken kesmek mümkün değildir. Ayrıca tarama, kesilebilecek hiçbir sınırı kaçırmaz: i sonrasındaki sınırı hiçbir harf aşmıyorsa parçadaki her harf en geç i konumunda sona erer; bu nedenle tam o noktada end, i'ye eşittir. Tarama yalnızca kesmeye izin verilen sınırları bulur; böylece mümkün olan en çok sayıda parça elde edilir.

abacdcefe içinde son konumlar a için 2, b için 1, c için 5, d için 4, e için 8 ve f için 7'dir. a'yı okumak end değerini 2 yapar, b bu değeri değiştirmez ve i = 2 konumunda parça 3 uzunluğuyla kapanır. c, end değerini 5 yapar ve parça 5 konumunda, yine 3 uzunluğuyla kapanır. e parçası 8 konumunda kapanır.

Algoritma

Tek bir geçişte, 26 elemanlı bir dizide her harfin son konumu olan last[c] değerini sakla.
start = 0 ve end = 0 olarak ayarla.
Her i konumu için end = max(end, last[s[i]]) olarak ayarla.
i == end ise yanıta end-start+1 ekle ve start = i+1 olarak ayarla.
Uzunlukları döndür.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Tuzaklar ve uç durumlar

Açgözlü geçiş kısa olduğundan hatalar, hangi konumla karşılaştırma yaptığınızda ve parça uzunluklarında gizlidir.

Parçanın end konumuna ulaştığınızda kesmek yerine, mevcut harfin son kopyasına ulaştığınızda kesmek. abcba dizisinde 2. indeksteki c kendi son kopyasıdır, ancak a'lar 4. indekse kadar devam eder; bu nedenle orada kesmek hem a'yı hem de b'yi böler.
Uzunlukta bir eksiklik ya da fazlalık. start ile end arasındaki, her iki uç da dahil olan bir parçada end-start+1 harf vardır.
Uzunluklar yerine kesme konumlarını döndürmek. abacdcefe için yanıt [3, 3, 3] olur; [2, 5, 8] değil.
Aralıklarda kestiğinizde son parçayı unutmak. Son parçanın ardından aralık olmadığından, döngü bittiğinde bir kez n-start ekleyin.
Her farklı harf için bir parça beklemek. zebraz beş farklı harf ve tek bir parça içerir; çünkü z'ler aralarındaki her şeyi bir arada tutar.

Sıkça sorulan sorular4

Partition Labels'ın zaman karmaşıklığı nedir?

Bir geçiş her harfin son konumunu kaydeder ve ikinci geçiş kesme noktalarını belirler; bu nedenle zaman karmaşıklığı O(n) olur. Son konumlar tablosunda, dizenin uzunluğu ne olursa olsun 26 giriş bulunur; bu nedenle çıktı hesaba katılmadığında ek alan O(1) olur.

Partition Labels için açgözlü yaklaşım neden işe yarar?

Mevcut bölüm, içerdiği her harfin son kopyasına ulaşmalıdır; bu yüzden end öncesinde kesme yapılamaz. end noktasında bölümdeki hiçbir harf daha sonra görünmez; dolayısıyla kesmeye izin verilir ve kesmek dizenin geri kalanına hiçbir zarar vermez. Bu nedenle geçiş, izin verilen her aralıkta keser ve başka hiçbir yerde kesmez; böylece herhangi bir yanıtın içerebileceği en fazla bölüm sayısına ulaşır.

Partition Labels, aralıkları birleştirme problemi midir?

Evet, gizli biçimde. Her harf, ilk kopyasından son kopyasına kadar olan aralığı kapsar; çakışan aralıkların bir bölümü ortak olmalıdır ve bunları birleştirmek tam olarak parçaları verir. Açgözlü geçiş, birleştirme işleminin anlık olarak yapılmasıyla aynıdır: end, o ana kadar birleştirilen bloğun sağ kenarıdır.

Partition Labels kaç parça döndürebilir?

1 ile 26 arasında. Hiçbir harf iki bölümde yer alamaz; bu nedenle her bölüm en az bir kendine ait harfe sahiptir ve yalnızca 26 küçük harf vardır. Her harfin bir kez geçtiği bir dize, uzunluğu 1 olan 26 bölüm verir; aynı harfle başlayıp biten bir dize ise tek bir bölüm verir.

Python

def partitionLabels(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "abacdcefe"

Beklenen

[3, 3, 3]

Partition Labels

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her boşluğu test et

Her harfin aralığını birleştir

Her parçayı son harfine kadar büyütün

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler