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

資訊專(zhuān)欄INFORMATION COLUMN

LeetCode——Longest Palindromic Substring

shevy / 1671人閱讀

摘要:題目即求最長(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 may assume that the maximum length of s is 1000.  

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"
即求最長(zhǎng)回文子序列
原題鏈接:https://leetcode.com/problems...
此篇博客僅為學(xué)習(xí)記錄

我的解法及代碼

暴力解決,用outPinnerP進(jìn)行兩層遍歷:outP循環(huán)中套一層for循環(huán),用innerP遍歷,求最長(zhǎng)回文序列字符串,同時(shí)用logest變量記錄最長(zhǎng)子序列

這種寫(xiě)法很暴力效率很低,outP一層循環(huán),innerP一層循環(huán),回文序列對(duì)比一層,時(shí)間復(fù)雜度為n^3
辣雞代碼

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let strL = s.length,
        longest = 0,
        resultS = "";
    for(let outP = 0; outP < strL; outP ++){
        for(let innerP = outP + longest; innerP < strL; innerP++){
            let tempS = s.slice(outP, innerP + 1),
                tempSL = tempS.length,
                halfL = parseInt(tempSL/2),
                sub1 = null,
                sub2 = tempS.slice(halfL, tempSL);
            if(tempSL % 2 === 0){
                sub1 = tempS.slice(0, halfL)
            }else{
                sub1 = tempS.slice(0, halfL + 1)
            }
            // console.log("halfL:" + halfL);
            // console.log("tempS:" + tempS);
            // console.log("sub1:" + sub1);
            // console.log("sub2:" + sub2);
            // console.log("------------------")
            if(compareReverse(sub1, sub2)){
                longest = tempSL;
                resultS = tempS;
            }
        }
    }
    return resultS;
};
function compareReverse(s1, s2){
    let length = s1.length,
        half = Math.ceil(length),
        flag = true;
    for(let i = 0; i < half; i++){
        if( !(s1[i] === s2[length-1-i])){
            flag = false;
            break;
        }
    }
    return flag;
}
學(xué)習(xí)高效的解法

主要學(xué)習(xí)了兩種,一種是常規(guī)的中心檢測(cè)法,時(shí)間復(fù)雜度為n^2,一種是Manacher"s Algorithm 馬拉車(chē)算法,時(shí)間復(fù)雜度為n。
這里主要學(xué)習(xí)高效的馬拉車(chē)寫(xiě)法

學(xué)習(xí)及參考鏈接在此:最長(zhǎng)回文子串——Manacher 算法

中心檢測(cè)法缺點(diǎn) 1.對(duì)奇數(shù)字符串與偶數(shù)字符串需要進(jìn)行處理

奇偶數(shù)會(huì)為處理帶來(lái)一些麻煩,但是對(duì)算法的效率影響不大

2.子串重復(fù)訪問(wèn)

例如babad字符串:

str:    a b c b a b a
index:  0 1 2 3 4 5 6

使用中心檢測(cè)法,當(dāng)index = 2時(shí),訪問(wèn)了abcba,當(dāng)index = 3時(shí),訪問(wèn)了cbaabcba后半串的cba又被訪問(wèn)了一次

解決方法 1.針對(duì)奇偶問(wèn)題

在字符串中插入"#"(當(dāng)然其他字符也可以),這樣無(wú)論是奇數(shù)還是偶數(shù),所有的字符串長(zhǎng)度都會(huì)變?yōu)槠鏀?shù)

例子1:abc -> #a#b#c#
例子2:abcd -> #a#b#c#d#
2.針對(duì)重復(fù)的問(wèn)題

核心思想:利用以計(jì)算的回文子串長(zhǎng)度再進(jìn)行擴(kuò)充。
此篇博文寫(xiě)得很好易懂,推薦:最長(zhǎng)回文子串——Manacher 算法

新寫(xiě)的代碼
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let s2 = getS2(s),
        R = getR(s2),
        maxRight = 0, //記錄最右邊界
        pos = 0,  //記錄最右邊界時(shí)對(duì)應(yīng)的中心位置
        maxIndex = 0; //記錄最長(zhǎng)回文串對(duì)應(yīng)的下標(biāo)
    s2.forEach((e, i)=>{
        if(i < maxRight){ //在MR左邊
            const j = 2 * pos - i;
            R[i] = Math.min(maxRight - i, R[j]);//保證回文的情況下,包裹于已探索區(qū)域內(nèi)
            let lp = i - R[i],
                rp = i + R[i];
            while(s2[lp] === s2[rp] && lp >= 0 && rp < s2.length){
                lp--;
                rp++;
                R[i]++;
            }
            if(rp > maxRight){
                pos = i;
            }
        }else{//在MR右邊,包括同MR同一個(gè)位置
            let lp = i - 1,
                rp = i + 1;
            while(s2[lp] === s2[rp] && lp >=0 && rp < s2.length){
                lp--;
                rp++;
                R[i]++;
            }
            pos = i;
            maxRight = rp;
        }
        maxIndex = R[i] > R[maxIndex]? i:maxIndex;
    });
    let subArray = s2.slice(maxIndex - R[maxIndex] + 1, maxIndex + R[maxIndex]),
        result = "";
    for(let item of subArray){
        if(item !== "#"){
            result += item
        }
    }
    // console.log(result);
    return result;
};
function getS2(s){//獲得插入"#"后的字符串
    const sLength = s.length,
          s2Length = 2 * sLength + 1;
    let s2 = new Array(s2Length).fill("#");
    for(let j = 1, i = 0; j < s2Length; j=j+2, i++){
        s2[j] = s[i];
    }
    return s2;
}
function getR(s2){//創(chuàng)建回文字符串半徑數(shù)組
    let R = new Array(s2.length).fill(1);//初始值為1;
    return R;
}
結(jié)果

僅僅超過(guò)60%,沉默.jpg,還有很多地方可以優(yōu)化

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

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

相關(guān)文章

  • [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
  • 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 最長(zhǎng)回文子串

    摘要:難度題目是說(shuō)給出一個(gè)字符串求出這個(gè)字符串的最長(zhǎng)回文的子串回文是指前后完全對(duì)稱的字符串像是之類(lèi)的都算是回文奇數(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 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
  • leetcode5 Longest Palindromic Substring 最長(zhǎng)且為回?cái)?shù)的子字符

    摘要:思路二指針最大長(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 i...

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

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

0條評(píng)論

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