Codebeispiel für die Java-String-Palindrom-Implementierung

Der Inhalt dieses Artikels befasst sich mit den Codebeispielen der Java-String-Palindrom-Implementierung. Ich hoffe, dass er für Freunde hilfreich ist.

String-Palindrom

Wie kann man beurteilen, ob ein String ein Palindrom-String ist? Ich denke, Sie hätten davon hören sollen. Unsere heutige Denkfrage basiert auf dieser modifizierten Version. Wenn die Zeichenfolge über eine einfach verknüpfte Liste gespeichert wird, wie kann dann festgestellt werden, ob es sich um eine Palindrom-Zeichenfolge handelt? Habt ihr
gute Lösungen? Was ist die entsprechende zeitliche und räumliche Komplexität?

Ideen:

1. Verwenden Sie schnelle und langsame Zeiger, um den mittleren Knoten zu finden
2. Kopieren Sie beim Suchen des mittleren Knotens eine verknüpfte Liste in umgekehrter Reihenfolge vom Anfang bis zum vorherigen mittleren Knoten 🎜>3. Vergleichen Sie, ob die vorherige verknüpfte Liste und die langsam verknüpfte Liste identisch sind

Code:

package me.study.algorithm;

/**
 * public class LinkNode {
 *
 *     char val;
 *
 *     LinkNode next;
 *
 *     public LinkNode() {
 *     }
 *
 *     public LinkNode(char val) {
 *         this.val = val;
 *     }
 * }
 */
public class StringBack {


    public boolean clac(LinkNode head) {

        if (head.next == null && head.next == null){
            return true;
        }

            LinkNode prev = null;
            LinkNode slow = head;
            LinkNode fast = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                LinkNode next = slow.next;
                slow.next = prev;
                prev = slow;
                slow = next;
            }


            if (fast != null) {
                slow = slow.next;
            }

            while (slow != null) {
                if (slow.val != prev.val) {
                    return false;
                }
                slow = slow.next;
                prev = prev.next;
            }

            return true;


    }
}

Beste Zeitkomplexität:

Der beste Fall ist ein einzelnes Zeichen oder ein Leerzeichen Zeichenfolge, die Zeitkomplexität beträgt O( 1)

Schlimmste Zeitkomplexität:

Die Zeitkomplexität zum Finden des Zwischenknotens beträgt n/2

Die Zeitkomplexität zum Vergleichen der Größe wird erst verglichen Finden Sie am Ende heraus, ob sie gleich sind, also ist es n/2
Phase Die Gesamtzeitkomplexität ist O(n)

Dieser Artikel ist hier. Weitere spannende Inhalte finden Sie hier die Spalte

Java Video Tutorial

der chinesischen PHP-Website!

Das obige ist der detaillierte Inhalt vonCodebeispiel für die Java-String-Palindrom-Implementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!