下面是CN人才網(wǎng)小編為大家解答騰訊2016軟開(kāi)實(shí)習(xí)生筆試題目，歡迎大家閱讀。

　　騰訊2016軟開(kāi)實(shí)習(xí)生筆試題目

　　問(wèn)題：求給定字符串s的回文(palindrome)子串中，長(zhǎng)度最大的回文子串的長(zhǎng)度。

　　回文(palindrome)是指從左往右讀和從右往左讀字符串，看到的字符串都是一樣的。比如“cabbeaf”,回文子串包括”c”“aba”“abba”等，最長(zhǎng)的子串是“abba”，長(zhǎng)度為4.

　　程序輸入：“cabbeaf”

　　程序輸出：

　　// C++ program to find the length of the longest palindrome

　　// for string "abeba" , longest palindrome is "abeba", thus 5;

　　// use recursion with memorization method

　　#include

　　#include

　　#include

　　using namespace std;

　　class Solution

　　// b/e is the begin/end index of the string s

　　// dp[i][j] is the biggest length of palindrome of s[i][j]

　　int palLength(string s, int b, int e, vector>&dp)

　　if (dp[b][e] != 0) return dp[b][e];

　　if (b > e ) return 0;

　　if (b == e) { dp[b][e] = 1; return 1; }

　　//if s[b]=s[e], then move b forward and e backward and do recursion

　　if (s[b] == s[e]){

　　dp[b][e] = palLength(s, b + 1, e - 1, dp) + 2;

　　//else move b forward or e backward and find the bigger one

　　else dp[b][e] = std::max(palLength(s, b + 1, e, dp), palLength(s, b, e - 1, dp));

　　return dp[b][e];

　　public:

　　int findPalindrome(string s){

　　int n = s.size();

　　vector> dp(n, vector(n, 0));

　　return palLength(s, 0, n - 1, dp);

　　// Driver program to test above function

　　int main()

　　string s("cabbeaf");

　　Solution solution;

　　cout << solution.findPalindrome(s);

　　這道題在leetcode上見(jiàn)過(guò)類似的題目，leetcode上是要求所有可能的劃分結(jié)果和最少的劃分次數(shù)，而這里只用求劃分之后的回文子串最長(zhǎng)的長(zhǎng)度就可以了。

　　用遞歸方法的思路是從字符串兩頭開(kāi)始找，對(duì)于當(dāng)前頭b和當(dāng)前尾e指定的字符串s[b…e]，如果頭和尾字符一樣s[b]=s[e]，那么最大回文子串長(zhǎng)度就是s[b+1 … e-1]的最大回文子串長(zhǎng)度加上2;如果頭和尾字符不一樣，那么頭和尾各移動(dòng)一步求回文子串長(zhǎng)度，即求s[b+1…e]和s[b…e-1]的回文子串長(zhǎng)度，然后s[b…e]的最大回文子串長(zhǎng)度就是s[b+1…e]和s[b…e-1]中的最大值。遞歸結(jié)束條件是b>=e，這里有一點(diǎn)注意的就是b>e，則返回0，b=e時(shí)按理說(shuō)應(yīng)該返回1，因?yàn)閷?duì)于一個(gè)字符，本身就可以看作是長(zhǎng)度為1的回文。這里根據(jù)題目要求來(lái)做相應(yīng)判斷就可以了。

　　另外，為了避免遞歸做重復(fù)的工作，用一個(gè)矩陣dp來(lái)記錄已經(jīng)求得的部分的回文子串長(zhǎng)度，初始dp矩陣的元素都為0，遞歸程序開(kāi)始檢查dp[b][e]是不是為0，不為0則說(shuō)明已經(jīng)找過(guò)了，直接返回該值就可以了。