国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

KnewOne / 1627人閱讀

摘要:這種解法中,外層循環(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 of S is 1000, and there exists one unique longest palindromic substring.
暴力法 Brute Force 復(fù)雜度

時(shí)間 O(n^3) 空間 O(1)

思路

暴力法就是窮舉所有子字符串的可能,然后依次按位判斷其是否是回文,并更新結(jié)果。雖然其時(shí)間復(fù)雜度很高,但它對(duì)空間的要求很低。

代碼
public class Solution {
    public String longestPalindrome(String s) {
        int maxLength = 0;
        int maxStart = 0;
        int len = s.length();
        //i是字符串長(zhǎng)度
        for(int i = 0; i < len; i++){
            //j是字符串起始位置
            for(int j = 0; j < len - i; j++){
                //挨個(gè)判斷是否回文
                if(isPalindrome(s,i,j) && (i+1)>maxLength){
                    maxLength = i + 1;
                    maxStart = j;
                }
            }
        }
        return s.substring(maxStart,maxStart + maxLength);
    }
    
    private isPalindrome(String s, int i, int j){
        int left = j;
        int right = j + i;
        while(left
動(dòng)態(tài)規(guī)劃 Dynamic Programming
復(fù)雜度

時(shí)間 O(n^2) 空間 O(n^2)

思路

根據(jù)回文的特性,一個(gè)大回文按比例縮小后的字符串也必定是回文,比如ABCCBA,那BCCB肯定也是回文。所以我們可以根據(jù)動(dòng)態(tài)規(guī)劃的兩個(gè)特點(diǎn):第一大問(wèn)題拆解為小問(wèn)題,第二重復(fù)利用之前的計(jì)算結(jié)果,來(lái)解答這道題。那如何劃分小問(wèn)題呢,我們可以先把所有長(zhǎng)度最短為1的子字符串計(jì)算出來(lái),根據(jù)起始位置從左向右,這些必定是回文。然后計(jì)算所有長(zhǎng)度為2的子字符串,再根據(jù)起始位置從左向右。到長(zhǎng)度為3的時(shí)候,我們就可以利用上次的計(jì)算結(jié)果:如果中心對(duì)稱的短字符串不是回文,那長(zhǎng)字符串也不是,如果短字符串是回文,那就要看長(zhǎng)字符串兩頭是否一樣。這樣,一直到長(zhǎng)度最大的子字符串,我們就把整個(gè)字符串集窮舉完了,但是由于使用動(dòng)態(tài)規(guī)劃,使計(jì)算時(shí)間從O(N^3)減少到O(n^2)。

注意

外循環(huán)的變量控制的實(shí)際上不是字符串長(zhǎng)度,而是字符串首到尾的增量

二維數(shù)組的第一維是指子字符串起始位置,第二維是指終止位置,所存數(shù)據(jù)表示是否回文

代碼
public class Solution {
    public String longestPalindrome(String s) {
        int maxLength = 0;
        int maxStart = 0;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        //i是字符串長(zhǎng)度
        for(int i = 0; i < len; i++){
            //j是字符串起始位置
            for(int j = 0; j < len - i; j++){
                if(i==0||i==1){
                    //如果字符串長(zhǎng)度為0,必定為回文
                    dp[j][j+i] = true;
                } else if(s.charAt(j+i)==s.charAt(j)){
                    //如果左右兩端相等,那只要中心對(duì)稱子字符串是回文就是回文
                    dp[j][j+i] = dp[j+1][j+i-1];
                } else {
                    //否則不是回文
                    dp[j][j+i] = false;
                }
                if(dp[j][j+i] && i > maxLength){
                    maxLength = i + 1;
                    maxStart = j;
                }
            }
        }
        return s.substring(maxStart,maxStart + maxLength);
    }
}
中心擴(kuò)散法 Spread From Center 復(fù)雜度

時(shí)間 O(n^2) 空間 O(1)

思路

動(dòng)態(tài)規(guī)劃雖然優(yōu)化了時(shí)間,但也浪費(fèi)了空間。實(shí)際上我們并不需要一直存儲(chǔ)所有子字符串的回文情況,我們需要知道的只是中心對(duì)稱的較小一層是否是回文。所以如果我們從小到大連續(xù)以某點(diǎn)為個(gè)中心的所有子字符串進(jìn)行計(jì)算,就能省略這個(gè)空間。 這種解法中,外層循環(huán)遍歷的是子字符串的中心點(diǎn),內(nèi)層循環(huán)則是從中心擴(kuò)散,一旦不是回文就不再計(jì)算其他以此為中心的較大的字符串。由于中心對(duì)稱有兩種情況,一是奇數(shù)個(gè)字母以某個(gè)字母對(duì)稱,而是偶數(shù)個(gè)字母以兩個(gè)字母中間為對(duì)稱,所以我們要分別計(jì)算這兩種對(duì)稱情況。

代碼
public class Solution {
    String longest = "";
    
    public String longestPalindrome(String s) {
        for(int i = 0; i < s.length(); i++){
            //計(jì)算奇數(shù)子字符串
            helper(s, i, 0);
            //計(jì)算偶數(shù)子字符串
            helper(s, i, 1);
        }
        return longest;
    }
    
    private void helper(String s, int idx, int offset){
        int left = idx;
        int right = idx + offset;
        while(left>=0 && right longest.length()){
            longest = currLongest;
        }
    }
}

2018/2

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        maxStr = ""
        for index in range(0, len(s)):
            sub1 = self.spreadFromCenter(s, index, 0)
            sub2 = self.spreadFromCenter(s, index, 1)
            if len(sub1) > len(maxStr):
                maxStr = sub1
            if len(sub2) > len(maxStr):
                maxStr = sub2
        return maxStr
        
    def spreadFromCenter(self, string, centerIndex, offset):
        leftIndex = centerIndex
        rightIndex = centerIndex + offset
        length = len(string)
        while leftIndex >= 0 and rightIndex < length and string[leftIndex] == string[rightIndex]:
            leftIndex = leftIndex - 1
            rightIndex = rightIndex + 1
        leftIndex = leftIndex + 1
        substring = string[leftIndex:rightIndex]
        return substring
馬拉車算法 Manacher Algorithm 復(fù)雜度

時(shí)間 O(n) 空間 O(n)

關(guān)于時(shí)間復(fù)雜度的證明:http://www.zhihu.com/question...

思路

Manacher算法是非常經(jīng)典的計(jì)算連續(xù)下標(biāo)回文的算法。它利用了回文的對(duì)稱性,更具體的來(lái)說(shuō),是回文內(nèi)回文的對(duì)稱性,來(lái)解決這個(gè)問(wèn)題。
參見(jiàn):http://www.felix021.com/blog/...

代碼
public class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<=1){
            return s;
        }
        // 預(yù)處理字符串,避免奇偶問(wèn)題
        String str = preProcess(s);
        // idx是當(dāng)前能夠向右延伸的最遠(yuǎn)的回文串中心點(diǎn),隨著迭代而更新
        // max是當(dāng)前最長(zhǎng)回文串在總字符串中所能延伸到的最右端的位置
        // maxIdx是當(dāng)前已知的最長(zhǎng)回文串中心點(diǎn)
        // maxSpan是當(dāng)前已知的最長(zhǎng)回文串向左或向右能延伸的長(zhǎng)度
        int idx = 0, max = 0;
        int maxIdx = 0;
        int maxSpan = 0;
        int[] p = new int[str.length()];
        for(int curr = 1; curr < str.length(); curr++){
            // 找出當(dāng)前下標(biāo)相對(duì)于idx的對(duì)稱點(diǎn)
            int symmetryOfCurr = 2 * idx - curr;
            // 如果當(dāng)前已知延伸的最右端大于當(dāng)前下標(biāo),我們可以用對(duì)稱點(diǎn)的P值,否則記為1等待檢查
            p[curr] = max > curr? Math.min(p[symmetryOfCurr], max - curr):1;
            // 檢查并更新當(dāng)前下標(biāo)為中心的回文串最遠(yuǎn)延伸的長(zhǎng)度
            while((curr+p[curr])max){
                max = p[curr] + curr;
                idx = curr;
            }
            // 檢查并更新當(dāng)前已知的最長(zhǎng)回文串信息
            if(p[curr]>maxSpan){
                maxSpan = p[curr];
                maxIdx = curr;
            }
        }
        //去除占位符
        return s.substring((maxIdx-maxSpan)/2,(maxSpan+maxIdx)/2-1);
    }
    
    private String preProcess(String s){
        // 如ABC,變?yōu)?#A#B#C#
        StringBuilder sb = new StringBuilder();
        sb.append("$");
        for(int i = 0; i < s.length(); i++){
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }
}
后續(xù) Follow Up

Q:如果只能在頭或尾刪,問(wèn)最少刪多少字符能使得該字符串變?yōu)榛匚模?br>A:就是找到最長(zhǎng)回文串,然后把長(zhǎng)度減一下就行了。

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/64389.html

相關(guān)文章

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

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

    NotFound 評(píng)論0 收藏0
  • LeetCode.5 最長(zhǎng)回文串(longest-palindromic-substring)(J

    摘要:一題目最長(zhǎng)回文子串給定一個(gè)字符串,找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。 一、題目 最長(zhǎng)回文子串: 給定一個(gè)字符串 s,找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。 示例 1: 輸入: babad輸出: bab注意: aba 也是一個(gè)有效答案。 示例 2: 輸入: cbbd輸出: bb 二、我的答案 思路 1.排...

    Steven 評(píng)論0 收藏0
  • LeetCode——Longest Palindromic Substring

    摘要:題目即求最長(zhǎng)回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決,用及進(jìn)行兩層遍歷循環(huán)中套一層循環(huán),用遍歷,求最長(zhǎng)回文序列字符串,同時(shí)用變量記錄最長(zhǎng)子序列這種寫(xiě)法很暴力,效率很低,一層循環(huán),一層循環(huán),回文序列對(duì)比一層,時(shí)間復(fù)雜度為辣 題目: Given a string s, find the longest palindromic substring in s. You ma...

    shevy 評(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)檫@種想法沒(méi)次都是兩邊同時(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

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

0條評(píng)論

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