Някои задачи в програмирането имат статут на класически. Обикновено такива задачи са свързани с математика и те много обичат да задават студенти от специалностите по компютърни науки, Howто и търсещи работа на интервюта. Те са добри, защото помагат да настроите мисленето си по програмист доста добре, Howто и да го тренирате. Един от тези проблеми е проверката дали даден низ е палиндром и ние ще го разгледаме в тази статия.
Какво е палиндром и защо можете да ги търсите
Палиндромът е число, буквена комбинация, дума or текст, които се четат еднакво и в двете посоки. За да обобщим, палиндром може да се нарече всеки набор от знаци, който е симетричен спрямо средата си. Думата е от гръцки корени, които буквално произлизат от „бягане назад“ (palin е „отново назад“ и dromos „бягане“). Палиндром в Java означава същото като общото meaning. Примери за палиндроми:
1881 г
aaqquqqaa
поп
По обяд
ниво
Ротатор
Моят фитнес
Госпожо, аз съм Адам
Сега, сър, войната е спечелена!
1881 е палиндромно число, а останалите са палиндромни низове. В тази статия ще разгледаме палиндроми, които са представени като низове, но някои алгоритми са доста приложими за други видове палиндроми в Java. Защо може да искате да търсите палиндроми? Всъщност не ни се налага често да търсим палиндроми в ежедневието. Това е много специфична задача. Ако си спомним низовите алгоритми, по-често на практика програмистите могат да намерят търсене на подниз в низ, а не търсене на палиндроми or техния брой. Въпреки това проблемите, свързани с палиндромите, имат важни applications. Първият е олимпиадата по програмиране. Може да има задачи за идентифициране на палиндроми. Второто приложение, което е от meaning за начинаещите програмисти, е интервюирането. На техническо интервю, може да бъдете помолени бързо да напишете програма, за да проверите дали даден низ е палиндром, може би дори на лист хартия. Е, в науката най-практическото приложение на намирането на палиндроми са биологичните алгоритми. Според Wikipedia палиндромността на биологичните съединения играе важна роля в свойствата на различни биологични съединения.
Пример за code на алгоритъм на палиндром
Нека да помислим. Низът е поредица от знаци, може да се каже, масив от char. Най-логично би било да следвате тази последователност от двете страни до средата и да сравните крайните знаци. Ако докато стигнем до средата, всичките ни герои съвпадат, тогава имаме палиндром. Нека създадем булев метод validPalindrome(String s), за да проверим дали String е палиндром. Java codeът е тук:
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);
}
}
В основния метод проверяваме за палиндромни низове „level“, „cool“, „Madam“ и „Сега, сър, войната е спечелена!“. Както можете да видите, първото, третото и четвъртото са палиндроми, но второто не е. Какво ще даде програмата?
нивото палиндром ли е? вярно ли е готиното палиндром? невярно мадам палиндром ли е? false е Сега, сър, войната е спечелена! палиндром? невярно
И така, първото е палиндром, второто не е. Какво обаче не е наред с третия и четвъртия? Защо резултатът е фалшив ? Вероятно вече се досещате, че въпросът е, че някои символи в този низ са главни, а други малки, а за Java M и m са два различни знака. Нека подобрим програмата, за да вземе предвид тази разлика. Ето програма за проверка дали даден низ е палиндром, която решава проблеми с главни и малки букви.
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);
}
}
Този път резултатът е по-предвидим за нас:
нивото палиндром ли е? вярно ли е готиното палиндром? невярно мадам палиндром ли е? вярно е Сега, сър, войната е спечелена! палиндром? невярно
Е… не е точно предсказуемо. Ситуацията с „госпожо“ се подобрява, но Howво ще кажете за нашия дълъг и щастлив палиндром „Сега, господине, войната е спечелена!“. Много е лесно, ако помните, че всички интервали и препинателни знаци са същите като буквите за Java. Така че трябва отново да подобрим нашия алгоритъм, за да коригираме този пропуск. Нека научим нашата програма да игнорира интервали и препинателни знаци. Просто казано, ние игнорираме всички небуквено-цифрови знаци. Ето подобрената програма за палиндром в Java.
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);
}
}
Поне резултатът е това, което очаквахме от него:
нивото палиндром ли е? вярно ли е готиното палиндром? невярно мадам палиндром ли е? вярно е Сега, сър, войната е спечелена! палиндром? вярно
Може би, ако тепърва започвате да програмирате, ви е трудно да разберете How работят алгоритмите за обхождане на низове и сравнение. Разбира се, по-добре е да се справите с това, но можете да напишете опростена version на самото преминаване през масива от знаци, което всъщност е низ. Можете да използвате метода StringBuffer.reverse, за да проверите дали даден низ е палиндром. Нека направим най-простата version, без да проверяваме за небуквено-цифрови символи и главни и малки букви.
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);
}
}
Резултатът е същият като в първия пример
нивото палиндром ли е? вярно ли е готиното палиндром? невярно мадам палиндром ли е? false е Сега, сър, войната е спечелена! палиндром? невярно
Ако искате, можете да подобрите тази програма, Howто направихме в първия пример. За да затвърдите наученото, ви предлагаме да гледате видео урок от нашия курс по Java
GO TO FULL VERSION