題目
給定一個(gè)字符串 s晦炊，找到 s 中最長(zhǎng)的回文子串榜聂。你可以假設(shè) s 的最大長(zhǎng)度為1000唉俗。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba"也是一個(gè)有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
tips: 回文字符串：正讀反讀都一樣
敘事
這道題目level為中等娱仔，讀第一遍我就覺(jué)得可能會(huì)很棘手沐飘，當(dāng)然立刻就有一個(gè)簡(jiǎn)單的解題思路，因?yàn)橹肋@種解法很爛所以一直沒(méi)有coding牲迫。直到有一天····
強(qiáng)迫癥患者根本無(wú)法繼續(xù)愉快coding了耐朴。。盹憎。只好不拖延筛峭，解決這個(gè)棘手的問(wèn)題····當(dāng)然肯定是因?yàn)樽约翰瞬庞X(jué)得棘手···
分析
最簡(jiǎn)單能想到的解決方案就是把字符串的所有子串枚舉出來(lái)，每一個(gè)都判斷是否是回文字符串脚乡，然后選長(zhǎng)度最長(zhǎng)的回文子串蜒滩。滨达。。后來(lái)我才知道這個(gè)算法叫暴力算法···名字很酷···暴力足以解決很多問(wèn)題····代碼很簡(jiǎn)單
public String longestPalindrome(String s) {
if(s.isEmpty()){
return s;
}
String res=s.substring(0,1);
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String k=s.substring(i,j);
String rk=new StringBuffer(k).reverse().toString();
if(k.equals(rk)&&k.length()>res.length()){
res=k;
}
}
}
return res;
}
一段不加注釋都能看得懂的代碼···我們執(zhí)行了一下····
果然···暴力的leetcode都看不過(guò)去···
現(xiàn)有的知識(shí)和智慧已經(jīng)不夠用了俯艰。然后去google解法捡遍。最強(qiáng)的是一個(gè)叫馬拉車(chē)的算法，看起來(lái)有點(diǎn)復(fù)雜竹握，而且對(duì)其他算法題幫助不大画株，所以拖拉的樓主決定晚點(diǎn)再學(xué)這個(gè)馬拉車(chē)。接下來(lái)就是動(dòng)態(tài)規(guī)劃算法啦辐。谓传。。等我起一個(gè)title芹关。
動(dòng)態(tài)規(guī)劃
為什么單獨(dú)將動(dòng)態(tài)規(guī)劃羅列出來(lái)呢续挟，因?yàn)檫@在算法問(wèn)題中好像十分普遍和重要。樓主之前刷面試題侥衬，很多算法問(wèn)題的answer 作者都直接甩一句動(dòng)態(tài)規(guī)劃···好诗祸，今天就直面曾經(jīng)欠下的債。動(dòng)態(tài)規(guī)劃頗有點(diǎn)“大事化小轴总，小事化了”的感覺(jué)直颅。在動(dòng)態(tài)規(guī)劃中有三個(gè)重要的元素最優(yōu)子結(jié)構(gòu)，邊界怀樟，狀態(tài)轉(zhuǎn)移公式功偿，我們稍后結(jié)合一個(gè)例子理解一下這仨概念~
理解動(dòng)態(tài)規(guī)劃有一個(gè)最典型的例子：
有面值分別為1，3往堡，5的三種硬幣若干械荷，需要湊成11元最少需要多少硬幣，湊成n元最少需要多少硬幣投蝉？
和往常一樣我們來(lái)一起找規(guī)律：
假如：
- 湊成0元需要0個(gè)硬幣 //d(0)=0
- 湊成1元需要1個(gè)1元硬幣 //d(1)=d(0)+1
- 湊成2元需要2個(gè)1元硬幣 //d(2)=d(1)+1
- 湊成3元需要3個(gè)1元硬幣或者1個(gè)3元硬幣养葵，那么我們選擇1個(gè)3元硬幣 //d(3)=min{d(2)+1,d(3-3)+1}
- 湊成4元需要1個(gè)3元硬幣征堪，1個(gè)1元硬幣 //d(4)=d(3)+1;
- 湊成5元需要1個(gè)3元硬幣瘩缆，2個(gè)1元硬幣或者1個(gè)5元硬幣，那么我們選擇1個(gè)5元硬幣 //d(5)=min{d(4)+1,d(5-5)+1}
- 佃蚜。庸娱。。谐算。
- 抽離出來(lái)d(i)=min{ d(i-1)+1,d(i-vj)+1 }熟尉，其中i-vj >=0，vj表示第j個(gè)硬幣的面值;
這里d(i-1)+1和d(i-vj)+1是d(i)的最優(yōu)子結(jié)構(gòu)洲脂，d(0)=0是邊界斤儿，d(i)=min{ d(i-1)+1,d(i-vj)+1 }是狀態(tài)轉(zhuǎn)移公式剧包。其實(shí)我們根據(jù)邊界+狀態(tài)轉(zhuǎn)移公式就能得到最終動(dòng)態(tài)規(guī)劃的結(jié)果。
上述程序的java實(shí)現(xiàn)
public int dp(int n) {
n++;
int min[] = new int[n];
int[] V = {1, 3, 5};
min[0]=0;
for (int i = 1; i < n; i++) {
min[i] = min[i-1]+1;
for (int j = 0; j < V.length; j++) {
if (V[j] > i) {
break;
}
if (min[i - V[j]] < min[i-1]) {
min[i] = min[i - V[j]] + 1;
}
}
}
return min[n - 1];
}
因?yàn)槲乙彩墙裉觳湃チ私鈩?dòng)態(tài)規(guī)劃往果，所以有可能有些理解不對(duì)表述不對(duì)的地方疆液。歡迎指出。
關(guān)于動(dòng)態(tài)規(guī)劃我看了的兩篇文章：
動(dòng)態(tài)規(guī)劃：從新手到專(zhuān)家
參考：程序員小灰動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃解決最長(zhǎng)回文子串
我們創(chuàng)建一個(gè)二維數(shù)組陕贮，boolean[][]dp,其中dp[i][j]表示字符串第i到j(luò)是否為回文堕油。那么邊界值其實(shí)很清楚了，j-i=1的都為true 字符串長(zhǎng)度為1的都為true肮之。狀態(tài)轉(zhuǎn)換如何設(shè)定呢掉缺？當(dāng)字符串i所在的字符等于字符串j所在的字符，并且它的內(nèi)部(dp[i+1][j-1])為回文那么dp[i][j]為true戈擒。因?yàn)檫@樣的規(guī)律眶明，我們要保證判斷dp[i][j]的時(shí)候dp[i+1][j-1]已經(jīng)判斷，所以我們遍歷采用i降序j升序的嵌套遍歷的方式
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return s;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int left = 0;
int right = 0;
for (int i = n - 2; i >= 0; i--) {
dp[i][i] = true;
for (int j = i + 1; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3是因?yàn)閍ba一定是回文
if(dp[i][j]&&right-left<j-i){
left=i;
right=j;
}
}
}
return s.substring(left,right+1);
}
這次我們?cè)龠\(yùn)行筐高，發(fā)現(xiàn)順利通過(guò)leetcode的考驗(yàn)~~
測(cè)試用例：dsfsdhadhfkdsdsfsdhadhdsfsdhadhfkddsfsdhadhfkdsahfksadhdsfsdhadhfkdsahfksadhfksddsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsksahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsk
哈哈好不好奇特別暴力算法呀哈哈哈哈哈~~~時(shí)間復(fù)雜度和空間復(fù)雜度達(dá)到極致的算法Ｗ咐础！
希望大家能教教我馬拉車(chē)算法？痢犬辰！
