美文网首页
LeetCode第9题回文数

LeetCode第9题回文数

作者: leilifengxingmw | 来源:发表于2020-02-16 18:20 被阅读0次

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

    示例 1:

    输入: 121
    输出: true

    示例 2:

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

    示例 3:

    输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数。
    进阶:

    解体思路:

    1. 把数字转化成字符串,从中间分开,左边从前向后遍历,右边从后向前遍历,如果每个字符都相等的话,说明是回文数。

    算法实现

    Java实现

        public static boolean isPalindrome(int number) {
            //将数字转化为字符串
            String numberStr = String.valueOf(number);
            int length = numberStr.length();
            if (length == 1) {
                return true;
            }
            //标记是否为回文数
            boolean result = true;
            //获取中间位置
            int middle = length / 2;
    
            for (int i = 0; i < middle; i++) {
                char left = numberStr.charAt(i);
                char right = numberStr.charAt(length - 1 - i);
                //如果有一个字符不想等,退出循环,返回false。
                if (left != right) {
                    result = false;
                    break;
                }
    
            }
            return result;
        }
    

    Kotlin实现

        fun isPalindrome(number: Int): Boolean {
            val numberStr = number.toString()
            val length = numberStr.length
            if (length == 1) {
                return true
            }
            var result = true
    
            val middle = length / 2
    
            for (i in 0 until middle) {
                val left = numberStr[i]
                val right = numberStr[length - 1 - i]
                if (left != right) {
                    result = false
                    break
                }
            }
            return result
        }
    

    疑问

    1. 数字转化成字符串以后,长度为奇数或者偶数,我们在遍历过程中并没有区分,这样会不会有问题呢?

    答案:不会的,我们来分析一下上面的算法。

        int middle = length / 2;
        for (int i = 0; i < middle; i++) {
            char left = numberStr.charAt(i);
            //right从后向前取
            char right = numberStr.charAt(length - 1 - i);
            if (left != right) {
                result = false;
                break;
            }
        }
    

    举例来看

    当长度为奇数的情况

    121

    length = 3,middle = length / 2 =1
    左边遍历的字符依次是:1
    右边遍历的字符依次是:1
    左右相等,所以121是回文数。
    可以看到,当长度为奇数的情况下,下标为middle的字符并没有被遍历到,我们只需要判断下标为middle的字符左右两边的字符序列是一样的即可。

    当长度为偶数的情况

    1221

    length = 4
    middle = length / 2 =2
    左边遍历的字符依次是:12
    右边遍历的字符依次是:12
    左右相等,所以1221是回文数
    可以看到,当长度为偶数的情况下,下标为middle的字符会被遍历到,位于右半边遍历的区域。

    你能不将整数转为字符串来解决这个问题吗?

    参考链接:

    相关文章

      网友评论

          本文标题:LeetCode第9题回文数

          本文链接:https://www.haomeiwen.com/subject/wwcmfhtx.html