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

資訊專欄INFORMATION COLUMN

leetcode5 Longest Palindromic Substring 最長(zhǎng)且為回?cái)?shù)的子字符

Imfan / 356人閱讀

摘要：思路二指針最大長(zhǎng)度現(xiàn)在我們從回?cái)?shù)的特點(diǎn)入手。因此，假設(shè)當(dāng)前得到的回?cái)?shù)的最大長(zhǎng)度為，我們可以判斷或者是不是回?cái)?shù)。假設(shè)此時(shí)指針指向，而已知最大回?cái)?shù)子字符串的長(zhǎng)度為。

題目要求

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

翻譯過來就是說：在一個(gè)字符串中尋找最長(zhǎng)的子字符串，該字符串是回?cái)?shù)（即從左往右和從右往左讀的結(jié)果是相同的）。該字符串的最大長(zhǎng)度為1000

思路一：頭指針+尾指針

遍歷字符串，找到當(dāng)前頭指針的元素下一次出現(xiàn)時(shí)的下標(biāo)，并且判斷該子字符串是否是回?cái)?shù)。

    public String longestPalindrome(String s) {
            StringBuilder result = new StringBuilder();
            int resultLength = 0;
            
            StringBuilder temp = new StringBuilder();
            for(int i = 0 ; i=i+resultLength ; j = s.substring(0, j).lastIndexOf(s.charAt(i))){
                    temp = new StringBuilder(s.substring(i, j+1));
                    if(temp.toString().equals(temp.reverse().toString())){
                        result = temp;
                        resultLength = temp.length();
                        break;
                    }    
                }
            }
            return result.toString();
        }

在該方法中，已經(jīng)對(duì)遍歷進(jìn)行了優(yōu)化，盡可能減少了無效遍歷，例如當(dāng)長(zhǎng)度一定小于當(dāng)前結(jié)果的最大長(zhǎng)度時(shí)，跳出當(dāng)前循環(huán)并進(jìn)入下一個(gè)遍歷。但是仍然有很多無效的遍歷，因此該答案最后還是超時(shí)的。

思路二：指針+最大長(zhǎng)度

現(xiàn)在我們從回?cái)?shù)的特點(diǎn)入手。
假若一個(gè)字符串是一個(gè)回?cái)?shù)，那么該字符串內(nèi)部一定還存在更多的回?cái)?shù)。例如，abbbcbbba是一個(gè)回?cái)?shù)，那么bbbcbbb一定是一個(gè)回?cái)?shù)，那么bcb也是回?cái)?shù)，最后到b。同理，bccb是一個(gè)回?cái)?shù)，那么cc也是一個(gè)回?cái)?shù)。因此可以看出，假設(shè)當(dāng)前一個(gè)字符串是回?cái)?shù)，那么加上兩側(cè)的字符可能還是回?cái)?shù)。假設(shè)當(dāng)前一個(gè)字符串不是回?cái)?shù)，那么加上右側(cè)的字符可能構(gòu)成一個(gè)回?cái)?shù)。
因此，假設(shè)當(dāng)前得到的回?cái)?shù)的最大長(zhǎng)度為n，我們可以判斷n+1或者n+2是不是回?cái)?shù)。
為什么這么判斷呢？下面給出證明。
我們假設(shè)有一個(gè)字符串xxxxxxxxabaxxxxxxs，其中x代表任意字符。
假設(shè)此時(shí)指針指向s，而已知最大回?cái)?shù)子字符串的長(zhǎng)度為3。我們只需要判斷xxxs以及xxxxs是不是回?cái)?shù)。無需判斷xxs乃至更近是因?yàn)樗鼈兊拈L(zhǎng)度必然無法超過當(dāng)前的最大長(zhǎng)度。而無需判斷xxxxxs乃至更遠(yuǎn)是因?yàn)榧偃鐇xxxxs是回?cái)?shù)，那么xxxx一定是回?cái)?shù)，則當(dāng)前的最大長(zhǎng)度為4而不是3，與題設(shè)不符。所以只需判斷兩種情況。
這里就充分利用了回?cái)?shù)的性質(zhì)，省去了很多無效的遍歷

    public String longestPalindrome2(String s) {
        StringBuilder result = new StringBuilder();
        int curLength = 0;
        
        for(int i = 0 ; i
思路三：由中間至兩邊找回?cái)?shù)

思路三就像是思路一的徹底反轉(zhuǎn)。思路一優(yōu)先尋找回?cái)?shù)的邊緣，而思路三則直接從中間開始尋找，直至找到最遠(yuǎn)的邊緣。
正如上面所說，回?cái)?shù)的中間可能是一個(gè)單值，如aba中的b；也可能是雙值，如abba中的bb。
我們可以對(duì)當(dāng)前下標(biāo)上的單值雙值都進(jìn)行嘗試
以下是我在leetcode上找到的一個(gè)實(shí)現(xiàn)（88%）


public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;
    
    for (int i = 0; i < len-1; i++) {
         extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
         extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}



想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

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

相關(guān)文章

  • Leetcode 5 Longest Palindromic Substring 最長(zhǎng)回文子串

    摘要：難度題目是說給出一個(gè)字符串求出這個(gè)字符串的最長(zhǎng)回文的子串回文是指前后完全對(duì)稱的字符串像是之類的都算是回文奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的奇數(shù)字母比如的中心在中間字母上偶數(shù)字母比如的回文在中間兩字母的中心上由此可見回文中心點(diǎn)實(shí)際上 Given a string s, find the longest palindromic substring in s. You may as...

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

  • LeetCode-5 Longest Palindromic Substring

    摘要：題目解析題目是要找出最長(zhǎng)的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長(zhǎng)的子字符串即可了。但是這種解法遇到極端輸入狀況就會(huì)超時(shí)，指定的最長(zhǎng)長(zhǎng)度為，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為，那么極端狀況會(huì)超時(shí)。 題目 Given a string s, find the longest palindromic substring in s. You may ...

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

  • leetcode 5 Longest Palindromic Substring Java &

    摘要：回文的意思就是反轉(zhuǎn)字符串后和原字符串相等。因?yàn)檫@種想法沒次都是兩邊同時(shí)擴(kuò)展。所以要分目標(biāo)字符串長(zhǎng)度為奇數(shù)目標(biāo)字符串為偶數(shù)兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...

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

  • [Leetcode] Longest Palindromic Substring 最長(zhǎng)回文子字符串

    摘要：這種解法中，外層循環(huán)遍歷的是子字符串的中心點(diǎn)，內(nèi)層循環(huán)則是從中心擴(kuò)散，一旦不是回文就不再計(jì)算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

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

  • 分析Longest Palindromic Substring的JS解法

    摘要：通過使用，我們將無論是奇數(shù)還是偶數(shù)的回文串，都變成了一個(gè)以為中心，為半徑兩個(gè)方向擴(kuò)展的問題。并且就是回文串的長(zhǎng)度。 Given a string s, find the longest palindromic substring in s. 這題的意思是找出 最長(zhǎng)連續(xù)回文串。 思路來源于此 這里描述了一個(gè)叫Manacher’s Algorithm的算法。 算法首先將輸入字符串S， 轉(zhuǎn)換...

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

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

0條評(píng)論

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