Java 文字列回文実装のコード例-＆＃＆チュートリアル-php.cn

Java 文字列回文実装のコード例

不言

リリース： 2019-03-25 11:02:06

転載

3028 人が閲覧しました

この記事では、Java 文字列回文の実装に関するコード例を紹介します。これには一定の参考値があります。必要な友人は参照してください。お役に立てば幸いです。

文字列回文

文字列が回文文字列であるかどうかを判断する方法については、聞いたことがあると思います。今日のトピックは、この
質問の修正版に基づいています。文字列が単一リンクリストを介して保存されている場合、それが回文文字列であるかどうかをどのように判断するのでしょうか?
良い解決策はありますか?対応する時間と空間の複雑さはどれくらいですか?

アイデア:
1. 高速ポインタと低速ポインタを使用して中間ノードを見つけます。
2. 中間ノードを見つけながら、逆リンクリストを最初から中間ノードにコピーします。 3. prev リンクリストと低速リンクリストが同じかどうかを比較します。

コード:

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;


    }
}

ログイン後にコピー

最良の時間計算量:

最良のケースは、単一の文字または空の文字列です。時間計算量は O( 1)

最悪の時間計算量:

中間ノードを見つける時間計算量は n/2
サイズの比較時間計算量は、それらが等しいかどうかを最後まで比較できないため、これは n/2
フェーズです。合計の時間計算量は O(n)

この記事はここにあります。さらにエキサイティングな内容については、

Java ビデオチュートリアル##をご覧ください。 PHP 中国語 Web サイトの # 列。

以上がJava 文字列回文実装のコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。