Palindrome Number
Palindrome Number
叶枫啦啦 发表于4个月前
Palindrome Number
  • 发表于 4个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

问题:

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

【注】问题要求O(1)空间复杂度,负数不是回文数

解决:

①每次提取头部和尾部的两个数,判断它们是否相等,判断后去掉头尾继续。采用除数和取余实现。暂时不能查看提交信息!耗时337ms。

public class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        int len = 1;
        while(x / len >=10) len *= 10;
        while(x > 0){
            int head = x / len;//获取头部
            int tail = x % 10;//获取尾部

            if (head != tail) {
                return false;
            }else{//去掉头部和尾部
                x = (x % len) / 10;
                len /= 100;

            }
        }
        return true;
    }
}

进化版:

public class Solution { //206ms
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        int div = 1;
        while(x / div >= 10) div = div * 10;  //位数
        while(x > 0) {
            if(x / div != x % 10) return false;
            x = x % div;  //去除头部
            x = x / 10;  //去除尾部
            div = div / 100;  //位数减2位
        }
        return true;
    }
}

③ 用tempx保存数字x的头部,用reverse保存除头部之外x位数的翻转,对比整个x的头尾两位,以及中间所有位reverse以后是否与不reverse时一致,即可得到结果。

public class Solution { //207ms
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int tempX = x;
        int reverse = 0;        
        while (tempX >= 10) { //// 当tempX剩下一位数的时候停下来
            reverse = reverse * 10 + tempX % 10; //将除了最高位之外的位数翻转
            tempX /= 10; //取得最高位
        }    
   
        return tempX == x % 10 && reverse == x / 10; ////对比整个x的头尾两位,以及中间所有位reverse以后是否与不reverse时一致
    }
}

共有 人打赏支持
粉丝 0
博文 213
码字总数 96569
×
叶枫啦啦
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: