Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Palindrome Number

Leetcode algorithms 第 9 题:Palindrome Number 。

题目

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

解答

直观上可以把数字转换成字符串,然后使用首尾两个指针向中间遍历判断是否是回文子串。但这样空间复杂度为O(n)。

为了不使用额外空间,对于一个数x,可以求得其第一位和最后一位,然后判断是否相等,然后在减去第一位和最后一位,对剩下的数以同样方法判断即可。

具体代码如下:

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return 0; //负数不可能回文
        if (x < 10) return 1;//一位数一定回文
        
        int q = 10; //最多有多少位
        while (x / q > 9) q *= 10; 
        while (x)
        {
            if (x/q != x%10) return 0; //最高位和最低位不等
            x -= x / q * q; //减去最高位
            x /= 10;        //减去最低位
            q /= 100;       //位数减2
        }
        return 1;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论