leetcode算法题解(Java版)-2-最长回文子串_java_weixin

一、int数字反转

题目描述
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: 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);
    }
}