Nogle programmeringsproblemer har status som klassiske. Typisk er sådanne opgaver relateret til matematik, og de er meget glade for at spørge studerende om datalogi specialer, samt jobsøgende til samtaler. De er gode, fordi de hjælper med at sætte din tankegang op på en programmør måde ganske godt, samt træne den. Et af sådanne problemer er at kontrollere, om en streng er et palindrom, og vi vil overveje det i denne artikel.
Hvad er et palindrom og hvorfor være i stand til at lede efter dem
Et palindrom er et tal, bogstavkombination, ord eller tekst, der læser det samme i begge retninger. For at opsummere kan et palindrom kaldes ethvert sæt af tegn, der er symmetrisk omkring dets midte. Ordet er fra græske rødder, der bogstaveligt talt stammer fra "løbe tilbage" (palin er "igen, tilbage" og dromos, "løber"). Palindrom i Java betyder det samme som i generel betydning. Eksempler på palindromer:
1881
aaqquqqaa
pop
Middag
niveau
Rotator
Mit træningscenter
Fru jeg er Adam
Nu, sir, en krig er vundet!
1881 er et palindromnummer og de andre er palindromstrenge. I denne artikel vil vi se på palindromer, der er repræsenteret som strenge, men nogle algoritmer er ret anvendelige til andre typer palindromer i Java. Hvorfor vil du måske kigge efter palindromer? Faktisk behøver vi ikke ofte lede efter palindromer i hverdagen. Det er en meget specifik opgave. Hvis vi husker strengalgoritmer, oftere i praksis, kan programmører finde søgning efter en understreng i en streng og ikke søgning efter palindromer eller deres nummer. Imidlertid har problemer relateret til palindromer vigtige anvendelser. Den første er olympiadeprogrammering. Der kunne være opgaver til at identificere palindromer. Den anden applikation, der er relevant for nybegyndere programmører, er interview. Ved et teknisk interview, du kan godt blive bedt om hurtigt at skrive et program for at tjekke om en streng er palindrom, måske endda på et stykke papir. Nå, i videnskaben er den mest praktiske anvendelse af at finde palindromer biologiske algoritmer. Ifølge Wikipedia spiller biologiske forbindelsers palindromicitet en vigtig rolle for forskellige biologiske forbindelsers egenskaber.
Palindrom algoritme kode eksempel
Lad os tænke. En streng er en sekvens af tegn, kan man sige, en række af char. Det ville være mest logisk at følge denne sekvens fra begge sider til midten og sammenligne de ekstreme tegn. Hvis indtil vi når midten vil alle vores karakterer matche, så har vi et palindrom. Lad os oprette en boolesk metode validPalindrome(String s) for at kontrollere, 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 tjekker vi for palindromiske strenge "niveau", "cool", "Madam" og "Nu, sir, en krig er vundet!". Som du kan se, er den første, tredje og fjerde palindrom, men den anden er ikke. Hvad vil programmet give?
er niveau et palindrom? sandt er cool et palindrom? falsk er fru et palindrom? falsk er Nu, sir, en krig er vundet! et palindrom? falsk
Så den første er et palindrom, den anden er ikke. Men hvad er der galt med den tredje og fjerde? Hvorfor er resultatet falsk ? Du har sikkert allerede gættet, at pointen er, at nogle tegn i denne streng er store bogstaver og nogle er små, og for Java er M og m to forskellige tegn. Lad os forbedre programmet for at tage højde for denne forskel. Her er et program til at tjekke, om en streng er et palindrom, der løser problemer med store og små bogstaver.
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 gang er resultatet mere forudsigeligt for os:
er niveau et palindrom? sandt er cool et palindrom? falsk er fru et palindrom? sandt er Nu, sir, en krig er vundet! et palindrom? falsk
Tja … ikke ligefrem forudsigeligt. Situationen med "Madam" bliver bedre, men hvad med vores lange og glade palindrom "Nu, sir, en krig er vundet!". Det er ret nemt, hvis du husker, at alle mellemrum og tegnsætningssymboler er de samme som bogstaver for Java. Så vi er nødt til at forbedre vores algoritme igen for at rette op på denne forglemmelse. Lad os lære vores program at ignorere mellemrum og tegnsætning. Kort sagt ignorerer vi alle ikke-alfanumeriske tegn. Her er det forbedrede palindromprogram 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 hvert fald, hvad vi forventede af det:
er niveau et palindrom? sandt er cool et palindrom? falsk er fru et palindrom? sandt er Nu, sir, en krig er vundet! et palindrom? rigtigt
Måske, hvis du lige er begyndt at programmere, er det svært for dig at forstå, hvordan strengtraversal- og sammenligningsalgoritmerne fungerer. Selvfølgelig er det bedre at håndtere dette, men du kan skrive en forenklet version af selve passagen gennem rækken af tegn, som faktisk er en streng. Du kan bruge StringBuffer.reverse-metoden til at kontrollere, om en streng er et palindrom. Lad os lave den enkleste version uden at tjekke for ikke-alfanumeriske symboler og store og små bogstaver.
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 allerførste eksempel
er niveau et palindrom? sandt er cool et palindrom? falsk er fru et palindrom? falsk er Nu, sir, en krig er vundet! et palindrom? falsk
Hvis du vil, kan du forbedre dette program, som vi gjorde med det første eksempel. For at styrke det, du har lært, foreslår vi, at du ser en videolektion fra vores Java-kursus
GO TO FULL VERSION