成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

LeetCode代碼分析——5. longest-palindromic-substring（動(dòng)態(tài)規(guī)

neuSnail / 3798人閱讀

摘要：題目描述給定一個(gè)字符串，找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。示例輸入輸出思路分析暴力解法解決一個(gè)問題如果沒有思路，就要想辦法從簡(jiǎn)單粗暴的解法開始，然后想辦法優(yōu)化它。

題目描述

https://leetcode-cn.com/probl...

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè)?s 的最大長(zhǎng)度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"
思路分析 暴力解法

解決一個(gè)問題如果沒有思路，就要想辦法從簡(jiǎn)單粗暴的解法開始，然后想辦法優(yōu)化它。
以"babad"為例，

子串長(zhǎng)度為1的時(shí)候，必然是回文

子串長(zhǎng)度為2的時(shí)候，[ba,ab,ba,ad]，需要兩個(gè)字符串相等才是回文

子串長(zhǎng)度為3的時(shí)候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等

子串長(zhǎng)度為4的時(shí)候，[baba,abad]。判斷方式同3

...

因此得到了一個(gè)暴力的解法，就是三層循環(huán)，

第一層循環(huán)是子串的長(zhǎng)度規(guī)模(12345)

第二層循環(huán)是遍歷每個(gè)子串(ba ab ba ad)

第三層循環(huán)是對(duì)比首尾的字符是否相等

時(shí)間復(fù)雜度

$$ O(n^3) $$

空間復(fù)雜度

$$ O(1) $$

動(dòng)態(tài)規(guī)劃 
子串長(zhǎng)度為1的時(shí)候，必然是回文


子串長(zhǎng)度為2的時(shí)候，[ba,ab,ba,ad]，需要兩個(gè)字符串相等才是回文


子串長(zhǎng)度為3的時(shí)候，[bab,aba,bad]，需要從兩邊向中心依次判斷字符是否相等


子串長(zhǎng)度為4的時(shí)候，[baba,abad]。判斷方式同3


...

基于暴力解法，我們發(fā)現(xiàn)3是可以復(fù)用1的結(jié)論的，4是可以復(fù)用2的結(jié)論的，5是可以復(fù)用3的結(jié)論的，因此就發(fā)現(xiàn)了DP的一個(gè)要素（重疊子問題）
DP的其它要素是最優(yōu)子結(jié)構(gòu)、子問題獨(dú)立，以及狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程：
dpi表示子串長(zhǎng)度為i時(shí)，從j開頭的子串是否為回文
s表示字符串

$$ dp[i][j] = egin{equation} egin{cases} true,&i=1 s[j] == s[j+1],&i=2 dp[i-2][j] && s[j]==s[j+i],&其它 end{cases} end{equation} $$

長(zhǎng)度為1的時(shí)候必然是回文，
長(zhǎng)度為2的時(shí)候取決于前后兩個(gè)字符串是否相等
其它情況則3看1,4看2，這樣看之前的是否是回文，然后判斷子串的首尾兩個(gè)是否是回文

根據(jù)狀態(tài)轉(zhuǎn)移方程填寫dp數(shù)組，最后得到問題結(jié)果

時(shí)間復(fù)雜度

$$ O(n^2) $$

空間復(fù)雜度

$$ O(n^2) $$

中心擴(kuò)展法

然后再基于動(dòng)態(tài)規(guī)劃解法的思路，分析下能否進(jìn)一步縮小空間復(fù)雜度
todo

源碼 動(dòng)態(tài)規(guī)劃 
public class MyDpSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            // i表示規(guī)格
            for(int j = 0; j < s.length() - i; j++){
                if(i == 0){
                    dp[i][j] = true;
                } else if(i == 1) {
                    dp[i][j]= s.charAt(j) == s.charAt(j+1);
                } else {
                    dp[i][j] = s.charAt(j) == s.charAt(j+i) && dp[i-2][j+1];
                }
            }
        }
        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = 0; j + i < s.length(); j++) {
                if(dp[i][j]) {
                    return s.substring(j, j + i + 1);
                }
            }
        }
        return "";
    }

}
中心擴(kuò)展法 
public class MyCenterExternSolution {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
        if(s.length() == 1) {
            return s;
        }
        int max_m = 0;
        int max_n = 0;
        int max = 0;
        for(int i = 1; i < s.length() * 2; i++) {
            int m,n,len=0;
            if((i & 1) == 0) {
                // i是偶數(shù)，說明中心點(diǎn)在一個(gè)字母上
                m = i / 2;
                n = i / 2;
            } else {
                // i是奇數(shù)，說明中心點(diǎn)在字母之間
                m = (i - 1) / 2;
                n = (i + 1) / 2;
            }
            while(m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
                m--;
                n++;
                len = n - m;
            }
            if(len > max) {
                max = len;
                max_m = m+1;
                max_n = n-1;
            }
        }
        return s.substring(max_m, max_n + 1);
    }

}

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

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

相關(guān)文章

  • 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】貪心算法--買賣股票的最佳時(shí)機(jī) II（122）

    摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當(dāng)前看來是最好的選擇，不從整體最優(yōu)上加以考慮，也就是說，只關(guān)心當(dāng)前最優(yōu)解，按照貪心策略，不關(guān)心以后，我們只關(guān)心當(dāng)前利益。 一、寫在前面 為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數(shù)人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...

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

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會(huì)折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號(hào)上。三匯總返回目錄在月日月日這半個(gè)月中，做了匯總了數(shù)組知識(shí)點(diǎn)?；蛘呃奖疚淖钕旅妫砑拥奈⑿诺葧?huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

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

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

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

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

  • [LintCode/LeetCode] Decode Ways [String to Integer

    摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動(dòng)規(guī)方法表示字符串的前位到包含方法的個(gè)數(shù)。最后返回對(duì)應(yīng)字符串末位的動(dòng)規(guī)結(jié)果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

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

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

0條評(píng)論

閱讀需要支付1元查看
<