回文问题

leetcode 9. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:  输入: 121 输出: true

示例 2:  输入: -121  输出: false  解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

对于数字的末位，直接取余就可以了，对于数字的首位，我们可以这么算。
首先用一个变量记录数字的最高位
比如12321，可以标记为help为10000
第一个末位为1，第一个首位为12321/10000=1
接下来我们需要计算232是否为回文。怎么计算呢。
我们需要去掉首位和末位。
可以采用x % help / 10的方式
12321%10000==2321可以将最高位去掉，然后2321/10==232可以将最低为去掉。
最后不要忘记将help/100

 public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int help = 1;
        int tmp = x;
        while (tmp >= 10) {
            help *= 10;
            tmp /= 10;
        }
        while (x != 0) {
            if (x % 10 != x / help) {
                return false;
            }
            x = x % help / 10;
            help /= 100;
        }
        return true;
    }

leetcode 5. 最长回文子串

中心扩散法

public String longestPalindrome(String s) {

        if(s == null || s.length() == 0){
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxstart = 0;
        int maxlen = 0;

        for(int i = 0;i<strLen;i++){
            left = i - 1;
            right = i + 1;
            while(left >= 0 && s.charAt(left) == s.charAt(i)){
                len++;
                left--;
            }
            while(right < strLen && s.charAt(right) == s.charAt(i)){
                len++;
                right++;
            }
            while(left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)){
                len = len + 2;
                left--;
                right++;
            }
            if(len > maxlen){
                maxlen = len;
                maxstart = left;
            }
            len = 1;
        }
        return s.substring(maxstart+1,maxstart+maxlen+1);

    }

动态规划法

public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxend = 0;    //最长回文串的终点
        int maxlen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxlen) {
                        maxlen = r - l + 1;
                        maxStart = l;
                        maxend = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxend + 1);

    }