leetcode算法题解(Java版)-2-最长回文子串
一、int数字反转 题目描述Reverse digits of an integer. Example1: x = 123, return 321Example2: x = -123, return -321 思路： 题目很简单，需要注意的是：int型是32位的。1000000003 反转后就超了！所以需要包装类Integer中的最大值和最小值 小技巧：为了实现反转，可以先把符号保存到flag中。 代码： public class Solution { public int reverse(int x) { int res=0; int flag=x>0?1:-1; x=x*flag; while(x>0){ res=10*res+x%10; x/=10; } res=res*flag; if(res>Integer.MAX_VALUE){ res=Integer.MAX_VALUE; } if(res<Integer.MIN_VALUE){ res=Integer.MIN_VALUE; } return (int)res; } } 二、简单模拟、StringBuffer类 题目描述 The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line:"PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); convert("PAYPALISHIRING", 3)should return"PAHNAPLSIIGYIR". 思路： 这题考到了StringBuffer类，虽然是将原字符“Z“字型排开，然后按每行输出得到结果。观察发现：从上到下（0~nRows)，然后再从下到上（nRows-2~0），依次把字符添加到每行对应的sb后面。最后再按行输出就行。 语法点：sb.append(char c);sb.toString();sb.length;s.charAt(int index);s.length(); 代码: public class Solution { public String convert(String s, int nRows) { if(s==null||s.length()<=0||nRows<=1){ return s; } StringBuffer [] sb=new StringBuffer[nRows]; for(int i=0;i<nRows;i++){ sb[i]=new StringBuffer(); } int len=s.length(); int tot=0; while(tot<len){ for(int i=0;i<nRows&&tot<len;i++){ sb[i].append(s.charAt(tot++)); } for(int j=nRows-2;j>0&&tot<len;j--){ sb[j].append(s.charAt(tot++)); } } for(int i=1;i<nRows;i++){ sb[0].append(sb[i]); } return sb[0].toString(); } } 三、最长回文子串 题目描述 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. 思路 中间扩散法：因为回文串是中心对称的。不妨找到回文串的中心，往两边扩散来看是否符合回文串定义。奇数：一个中心字符；偶数：两个中心字符 dp大法：设置一个dp状态数组，dp(i,j)=true如果子串i~j是回文串，那么子串i-1~j+1是不是回文串跟i~j有关，所以可以用dp。状态转移方程：dp(i,j)=(s[i]==s[j]&&dp(i+1,j-1)) 代码：中间扩散： public class Solution { public String longestPalindrome(String s) { if(s==null||s.length()<=1){ return s; } int len=s.length(); int beg=0; int ans=0; //odd for(int i=1;i<len;i++){ int m=i-1; int n=i+1; while(m>=0&&n<len&&s.charAt(m)==s.charAt(n)){ if(n-m+1>ans){ ans=n-m+1; beg=m; } m--; n++; } } //even for(int i=0;i<len;i++){ int m=i; int n=i+1; while(m>=0&&n<len&&s.charAt(m)==s.charAt(n)){ if(n-m+1>ans){ ans=n-m+1; beg=m; } m--; n++; } } if(beg==0&&ans==1){ return s.charAt(0)+""; } return s.substring(beg,beg+ans); } } dp大法： public class Solution { public String longestPalindrome(String s) { int len=s.length(); if(len<2||s==null){ return s; } boolean [][] dp=new boolean [len][len]; int maxlen=0; int beg=0; for(int i=0;i<len;i++){//dp解题，初始化dp状态数组 dp[i][i]=true; } for(int i=0;i<len;i++){ for(int j=0;j<i;j++){ if(s.charAt(i)==s.charAt(j)){ if(j+1<len&&i-1>=0&&(dp[j+1][i-1]==true||i-j==1)){//注意！i-j==1小细节，一开始不过就是因为没有考虑它 dp[j][i]=true; if(maxlen<i-j+1){ maxlen=i-j+1; beg=j; } } } } } if(maxlen==0&&beg==0){ return s.charAt(0)+""; } return s.substring(beg,beg+maxlen); } }
