成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

字符串回文實(shí)現(xiàn)

hzc / 3167人閱讀

摘要：字符串回文如何判斷一個(gè)字符串是否是回文字符串的問題，我想你應(yīng)該聽過，我們今天的思題目就是基于這個(gè)問題的改造版本。

字符串回文

如何判斷一個(gè)字符串是否是回文字符串的問題，我想你應(yīng)該聽過，我們今天的思題目就是基于這個(gè)
問題的改造版本。如果字符串是通過單鏈表來存儲(chǔ)的，那該如何來判斷是一個(gè)回文串呢？你有什么
好的解決思路呢？相應(yīng)的時(shí)間空間復(fù)雜度又是多少呢？

思路：
1.使用快慢指針來找到中間節(jié)點(diǎn)
2.在找中間節(jié)點(diǎn)的同時(shí)復(fù)制一份反序的從開頭到中間節(jié)點(diǎn)的鏈表prev
3.比較prev鏈表和slow鏈表是否相同

代碼：

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;


    }
}

最好時(shí)間復(fù)雜度：
最好的情況就是單個(gè)字符或者空字符串，時(shí)間復(fù)雜度為O(1)

最壞時(shí)間復(fù)雜度：
查找中間節(jié)點(diǎn)時(shí)間復(fù)雜度n/2
比較大小時(shí)間復(fù)雜度直到最后才比較出是否相等所以為n/2
相加起來最后的時(shí)間復(fù)雜度為O(n)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73898.html

相關(guān)文章

  • 最長回文子串——Manacher 算法

    摘要：問題定義最長回文子串問題給定一個(gè)字符串，求它的最長回文子串長度。可以采用動(dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來解最長回文串問題，無需討論串長度的奇偶性。 0. 問題定義 最長回文子串問題：給定一個(gè)字符串，求它的最長回文子串長度。 如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例： 12321 a aba abba aaaa tatt...

    mingzhong 評(píng)論0 收藏0

  • [算法總結(jié)] 搞定 BAT 面試——幾道常見的子符串算法題

    摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長度不會(huì)超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個(gè)可能的最長回文子序列為。數(shù)值為或者字符串不是一個(gè)合法的數(shù)值則返回。 說明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點(diǎn)：https://www.weiweiblog.c...

    chanjarster 評(píng)論0 收藏0

  • [Leetcode] Palindrome Permutation 回文變換

    摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對(duì)稱點(diǎn)如果是字符，該字符會(huì)是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

    svtter 評(píng)論0 收藏0

  • java算法題：最長回文串

    摘要：給定一個(gè)包含大寫字母和小寫字母的字符串，找到通過這些字母構(gòu)造成的最長的回文串。比如不能當(dāng)做一個(gè)回文字符串。注意假設(shè)字符串的長度不會(huì)超過。代碼實(shí)現(xiàn)最長回文串回文串是一個(gè)正讀和反讀都一樣的字符串，比如或者等等就是回文串。 LeetCode: 給定一個(gè)包含大寫字母和小寫字母的字符串，找到通過這些字母構(gòu)造成的最長的回文串。在構(gòu)造過程中，請(qǐng)注意區(qū)分大小寫。比如Aa不能當(dāng)做一個(gè)回文字符串。注 意:...

    Honwhy 評(píng)論0 收藏0

  • 獲取最長回文子串

    摘要：以下是最長回文子串的相關(guān)代碼，相關(guān)邏輯已在注釋中注明我們?cè)械淖址赡艽嬖趦煞N回文子串，一種是具有基數(shù)個(gè)元素例如一種是具有偶數(shù)個(gè)元素例如這樣的話分情況判斷比較復(fù)雜所以我們對(duì)原字符串進(jìn)行擴(kuò)充在相鄰元素中插入特殊值插入后的原基數(shù)回文子串變成了 以下是最長回文子串的Manacher‘s Algorithm相關(guān)代碼，相關(guān)邏輯已在注釋中注明： public static String solu...

    ymyang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<