Temel LeetCode Algoritması Problemi Bölüm 57: Alfabetik Büyük Harf Değiştirme Problemini Çözmek İçin İki Yöntem
LeetCode 784. Harf büyüklüğünün tam düzenlemesi (3B Şekillerin Yüzey Alanı)
Sorun Açıklaması:
Bir S dizesi verildiğinde, S dizesindeki her harfin durumunu değiştirerek yeni bir dize elde edebiliriz. Olası tüm dizelerin bir koleksiyonunu döndür.
Misal:
C dili uygulaması:
Bu problemi çözmenin birçok yolu var.Önceki uygulamam BFS (en geniş algoritma) kullanmaktı, ancak BFS'nin bir kuyruk oluşturması gerekiyor ve kodun tamamı 80'den fazla satır alıyor. BFS algoritmasının amacı, ilk önce orijinal dizgiyi sıraya koymak, ardından orijinal dizenin her karakterini geçmek, eğer bir harfle karşılaşırsa, sıradaki öğeleri sırayla açmaya başlayacak ve her eleman için karakterin durumunu değiştirerek yeni bir tane oluşturmaktır. Dize, sıraya yeniden girilir. Bu, tüm karakterler geçilene kadar devam eder.
Burada verdiğimiz kod başka bir çözümdür Bu yöntem bir ikame yöntemi değil, aşamalı bir doldurma yöntemidir.
Ayrıntılı kod aşağıdaki gibidir:
İlk önce boş bir dize oluşturun ve res ile doldurun. Yine de orijinal dizenin her karakterini taramak gerekir. Bir sayı ile karşılaşılırsa, her yeni dizeden sonra doğrudan doldurulur; bir harfle karşılaşılırsa, geçici bir dizi oluşturulur ve dizi öğesi budur. Büyük ve küçük harfler.
Count değişkeni, yeni dizelerin sayısını kaydeder ve kodun 18. satırındaki döngü kademeli olarak doldurulur. İşte bir ayrıntı, örneğin, mevcut sayı = 2, res = "b", S ise = 'c', lowerAndUpper içeriği. Bu zamanda, bc'ye ek olarak, bC dizesi üretilecektir Yaklaşımımız yeni bC dizesini res konumuna kaydetmektir.
Son olarak, verimlilik konusundan bahsedin. Burada verilen iki algoritmanın verimliliği iyi değil. İkinci algoritmanın en kötü zaman karmaşıklığı O (n ^ 2) 'dir.
Şimdilik, daha iyi algoritma karmaşıklığına sahip algoritmalar düşünmedim, bunun hakkında düşünmek için zamanım var.
Ayrıca düşüncelerinizi ifade etmek için yorum alanına bir mesaj bırakabilirsiniz.
Python dilinin uygulanması:
Python uygulaması tamamen C dilinin ikinci uygulama yöntemini ifade eder. Python'da uygulamak daha kolay.
kod aşağıdaki gibi gösterilir:
Java dilinin uygulanması:
Java'nın uygulanması için BFS algoritmasını kullanıyorum, çünkü java kütüphanesinde kuyruk arayüzünün uygulanması C dilinden çok daha basit. Belirli uygulama ilkeleri için, C dili uygulamasındaki açıklamaya bakın.
kod aşağıdaki gibi gösterilir:
