Programlamadaki bazı problemler klasik problemler statüsüne sahiptir. Tipik olarak, bu tür görevler matematikle ilgilidir ve mülakatlarda iş arayanların yanı sıra Bilgisayar Bilimleri uzmanlık öğrencilerine sormaktan çok hoşlanırlar. İyiler çünkü düşüncenizi bir programcıya göre oldukça iyi bir şekilde kurmanıza ve onu eğitmenize yardımcı oluyorlar. Bu tür problemlerden biri, bir dizenin palindrom olup olmadığını kontrol etmektir ve bu makalemizde bunu ele alacağız.
Palindrom nedir ve neden onları arayabiliriz?
Palindrom, her iki yönde de aynı şekilde okunan bir sayı, harf kombinasyonu, kelime veya metindir. Özetlemek gerekirse, bir palindrom, ortasına göre simetrik olan herhangi bir karakter kümesi olarak adlandırılabilir. Kelime, kelimenin tam anlamıyla "geri koşmak" türeyen Yunan köklerinden gelir (palin "tekrar, geri" ve dromos "koşmak"). Java'daki palindrom, genel anlamıyla aynı anlama gelir. Palindrom örnekleri:
1881
aaqquqqaa
pop
Öğlen
seviye
döndürücü
Spor Salonum
Hanımefendi ben Adam
Şimdi efendim, bir savaş kazanıldı!
1881 bir palindrom sayısıdır ve diğerleri palindrom dizileridir. Bu yazıda, diziler olarak temsil edilen palindromlara bakacağız, ancak bazı algoritmalar Java'daki diğer palindrom türleri için oldukça uygulanabilir. Neden palindrom aramak isteyebilirsiniz? Aslında, günlük yaşamda çoğu zaman palindrom aramak zorunda değiliz. Bu çok özel bir görev. Dize algoritmalarını hatırlarsak, pratikte daha sık olarak, programcılar bir dizede bir alt dize aramayı bulabilirler ve palindromları veya sayılarını aramazlar. Ancak palindromlarla ilgili problemlerin önemli uygulamaları vardır. Birincisi olimpiyat programlaması. Palindromları tanımlamak için görevler olabilir. Acemi programcılar için geçerli olan ikinci uygulama mülakattır. Teknik bir görüşmede, bir dizenin palindrom olup olmadığını kontrol etmek için hızlı bir şekilde bir program yazmanız istenebilir, hatta belki bir kağıt parçası üzerinde. Bilimde, palindrom bulmanın en pratik uygulaması biyolojik algoritmalardır. Wikipedia'ya göre, biyolojik bileşiklerin palindromikliği, çeşitli biyolojik bileşiklerin özelliklerinde önemli bir rol oynar.
Palindrome algoritması kod örneği
Düşünelim. Bir dize, bir karakter dizisidir, denilebilir ki, bir karakter dizisidir. Bu sırayı her iki taraftan ortaya doğru takip etmek ve uç karakterleri karşılaştırmak en mantıklısı olacaktır. Ortaya ulaşana kadar tüm karakterlerimiz eşleşirse, o zaman bir palindromumuz olur. String'in palindrom olup olmadığını kontrol etmek için validPalindrome(String s) bir boolean yöntemi oluşturalım. Java kodu burada:
public class PalindromeTest1 {
//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Ana yöntemde “level”, “cool”, “Madam” ve “Şimdi efendim, bir savaş kazanıldı!” palindromik dizileri kontrol ediyoruz. Gördüğünüz gibi birinci, üçüncü ve dördüncü palindrom ama ikincisi değil. Program ne verecek?
seviye bir palindrom mu? Doğru, havalı bir palindrom mu? yanlış Madam bir palindrom mu? yanlış Şimdi efendim, bir savaş kazanıldı! bir palindrom mu? YANLIŞ
Yani birincisi bir palindrom, ikincisi değil. Ancak, üçüncü ve dördüncüde yanlış olan ne? Sonuç neden yanlış ? Muhtemelen, bu dizedeki bazı karakterlerin büyük, bazılarının küçük harf olduğunu ve Java için M ve m'nin iki farklı karakter olduğunu tahmin etmişsinizdir. Programı bu farkı dikkate alacak şekilde geliştirelim. İşte bir dizenin büyük ve küçük harf problemlerini çözen bir palindrom olup olmadığını kontrol eden bir program.
public class PalindromeTest2 {
//lowercase and uppercase characters should be treated the same:
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Bu sefer sonuç bizim için daha öngörülebilir:
seviye bir palindrom mu? Doğru, havalı bir palindrom mu? yanlış Madam bir palindrom mu? doğru Şimdi efendim, bir savaş kazanıldı! bir palindrom mu? YANLIŞ
Pekala… tam olarak tahmin edilemez. "Madam" ile durum iyiye gidiyor, ama bizim uzun ve mutlu palindromumuz "Şimdi, efendim, bir savaş kazanıldı!" Tüm boşlukların ve noktalama işaretlerinin Java'daki harflerle aynı olduğunu hatırlarsanız, oldukça kolaydır. Dolayısıyla, bu gözden kaçmayı düzeltmek için algoritmamızı tekrar geliştirmemiz gerekiyor. Programımıza boşlukları ve noktalama işaretlerini göz ardı etmeyi öğretelim. Basitçe söylemek gerekirse, alfasayısal olmayan tüm karakterleri yok sayarız. İşte Java'daki geliştirilmiş palindrom programı.
public class PalindromeTest3 {
//in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
private static boolean isAlphanumeric(char c) {
return Character.isAlphabetic(c) || Character.isDigit(c);
}
public static boolean validPalindromeIgnorePunctuation(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
// skip chars we should ignore
while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
// overskipped -> nothing left to validate
if (i >= j) return true;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindromeIgnorePunctuation(s1);
boolean b2 = validPalindromeIgnorePunctuation(s2);
boolean b3 = validPalindromeIgnorePunctuation(s3);
boolean b4 = validPalindromeIgnorePunctuation(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
En azından sonuç beklediğimiz gibi:
seviye bir palindrom mu? Doğru, havalı bir palindrom mu? yanlış Madam bir palindrom mu? doğru Şimdi efendim, bir savaş kazanıldı! bir palindrom mu? doğru
Programlamaya yeni başlıyorsanız, dizi geçişi ve karşılaştırma algoritmalarının nasıl çalıştığını anlamak sizin için zor olabilir. Tabii ki, bununla başa çıkmak daha iyidir, ancak aslında bir dize olan karakter dizisinden geçişin basitleştirilmiş bir versiyonunu yazabilirsiniz. Bir dizenin palindrom olup olmadığını kontrol etmek için StringBuffer.reverse yöntemini kullanabilirsiniz. Alfasayısal olmayan semboller ve büyük ve küçük harfleri kontrol etmeden en basit halini yapalım.
public class PalindromeTest5 {
public static boolean validPalindrome(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
String data = buffer.toString();
if (s.equals(data)) {
return true;
}
return false;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Sonuç, ilk örnektekiyle aynı
seviye bir palindrom mu? Doğru, havalı bir palindrom mu? yanlış Madam bir palindrom mu? yanlış Şimdi efendim, bir savaş kazanıldı! bir palindrom mu? YANLIŞ
İsterseniz bu programı ilk örnekte yaptığımız gibi geliştirebilirsiniz. Öğrendiklerinizi pekiştirmek için Java Kursumuzdan bir video dersi izlemenizi öneririz.
GO TO FULL VERSION