Noen problemer i programmering har status som klassiske. Vanligvis er slike oppgaver relatert til matematikk, og de er veldig glade i å spørre studenter om datavitenskapelige spesialiteter, samt jobbsøkere på intervjuer. De er gode fordi de hjelper til med å sette opp tenkningen din på en programmerer måte ganske bra, i tillegg til å trene den. Et av slike problemer er å sjekke om en streng er et palindrom, og vi skal vurdere det i denne artikkelen.
Hva er et palindrom og hvorfor være i stand til å lete etter dem
Et palindrom er et tall, bokstavkombinasjon, ord eller tekst som leser det samme i begge retninger. For å oppsummere kan et palindrom kalles ethvert sett med tegn som er symmetrisk rundt midten. Ordet er fra greske røtter som bokstavelig talt stammer fra "løpe tilbake" (palin er "igjen, tilbake," og dromos, "løper."). Palindrom i Java betyr det samme som i generell betydning. Eksempler på palindromer:
1881
aaqquqqaa
pop
Middagstid
nivå
Rotator
Mitt treningsstudio
Fru jeg er Adam
Nå, sir, en krig er vunnet!
1881 er et palindromnummer og de andre er palindromstrenger. I denne artikkelen skal vi se på palindromer som er representert som strenger, men noen algoritmer er ganske anvendelige for andre typer palindromer i Java. Hvorfor vil du kanskje se etter palindromer? Det er faktisk ikke ofte vi trenger å lete etter palindromer i hverdagen. Det er en ganske spesifikk oppgave. Hvis vi husker strengalgoritmer, oftere i praksis, kan programmerere finne å søke etter en delstreng i en streng, og ikke søke etter palindromer eller deres nummer. Imidlertid har problemer knyttet til palindromer viktige anvendelser. Den første er olympiadeprogrammering. Det kan være oppgaver for å identifisere palindromer. Den andre applikasjonen som er relevant for nybegynnere programmerere er intervju. På et teknisk intervju, du kan godt bli bedt om å raskt skrive et program for å sjekke om en streng er palindrom, kanskje til og med på et stykke papir. Vel, i vitenskapen er den mest praktiske anvendelsen av å finne palindromer biologiske algoritmer. Ifølge Wikipedia spiller biologiske forbindelsers palindromitet en viktig rolle i egenskapene til ulike biologiske forbindelser.
Eksempel på palindromalgoritmekode
La oss tenke. En streng er en sekvens av tegn, kan man si, en rekke tegn. Det ville være mest logisk å følge denne sekvensen fra begge sider til midten og sammenligne de ekstreme karakterene. Hvis inntil vi når midten vil alle karakterene våre matche, så har vi et palindrom. La oss lage en boolsk metode validPalindrome(String s) for å sjekke om String er palindrom. Java-koden er her:
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);
}
}
I hovedmetoden sjekker vi for palindromiske strenger "nivå", "kul", "Madam" og "Nå, sir, en krig er vunnet!". Som du kan se, er den første, tredje og fjerde palindromer, men den andre er det ikke. Hva vil programmet gi?
er nivå et palindrom? sant er kult et palindrom? usant er Madam et palindrom? falsk er Nå, sir, en krig er vunnet! et palindrom? falsk
Så det første er et palindrom, det andre er det ikke. Men hva er galt med den tredje og fjerde? Hvorfor er resultatet falskt ? Du har sikkert allerede gjettet at poenget er at noen tegn i denne strengen er store bokstaver og noen er små, og for Java er M og m to forskjellige tegn. La oss forbedre programmet for å ta hensyn til denne forskjellen. Her er et program for å sjekke om en streng er et palindrom som løser store og små bokstaver.
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);
}
}
Denne gangen er resultatet mer forutsigbart for oss:
er nivå et palindrom? sant er kult et palindrom? usant er Madam et palindrom? sant er Nå, sir, en krig er vunnet! et palindrom? falsk
Vel ... ikke akkurat forutsigbart. Situasjonen med "Madam" blir bedre, men hva med vårt lange og lykkelige palindrom "Nå, sir, en krig er vunnet!". Det er ganske enkelt, hvis du husker at alle mellomrom og tegnsettingssymboler er de samme som bokstaver for Java. Så vi må forbedre algoritmen vår igjen for å rette opp denne forglemmelsen. La oss lære programmet vårt å ignorere mellomrom og tegnsetting. Enkelt sagt ignorerer vi alle ikke-alfanumeriske tegn. Her er det forbedrede palindromprogrammet i 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);
}
}
Resultatet er i det minste det vi forventet av det:
er nivå et palindrom? sant er kult et palindrom? usant er Madam et palindrom? sant er Nå, sir, en krig er vunnet! et palindrom? ekte
Kanskje, hvis du akkurat har begynt å programmere, er det vanskelig for deg å forstå hvordan algoritmene for stringtraversering og sammenligning fungerer. Selvfølgelig er det bedre å takle dette, men du kan skrive en forenklet versjon av selve passasjen gjennom rekken av tegn, som faktisk er en streng. Du kan bruke StringBuffer.reverse-metoden for å sjekke om en streng er et palindrom. La oss gjøre den enkleste versjonen uten å se etter ikke-alfanumeriske symboler og store og små bokstaver.
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);
}
}
Resultatet er det samme som i det aller første eksemplet
er nivå et palindrom? sant er kult et palindrom? usant er Madam et palindrom? falsk er Nå, sir, en krig er vunnet! et palindrom? falsk
Hvis du vil, kan du forbedre dette programmet slik vi gjorde med det første eksemplet. For å forsterke det du lærte, foreslår vi at du ser en videoleksjon fra vårt Java-kurs
GO TO FULL VERSION