首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >不转字符串判断——LeetCode题目9:回文数

不转字符串判断——LeetCode题目9:回文数

作者头像
二环宇少
发布2020-08-13 15:27:20
4480
发布2020-08-13 15:27:20
举报

原题描述

+

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。但你不能使用转字符串后判断的方法。

示例 1

输入:121

输出:true

示例 2

输入:-121

输出:false

示例 3

输入:10

输出:false

原题链接:https://leetcode-cn.com/problems/palindrome-number

思路解析

+

这是一道简单题,通过率在50%以上。

其实字符串转数字的方式反而麻烦。在之前的LeetCode题目7:整数反转中你已经知道了怎么把一个整数数字做反转,现在依然可以利用它来做回文判断。

示例中你已经知道了有两种情况是不可能返回true的:

1. 负数;

2. 尾数为0的数。

那么你可能还需要知道的是,回文的判断只需要搜索一半数字即可。比如4554,当你不断把尾数截取,并迭代构造反转整数的过程中,一定会经历下面的过程:

origin: 4554  -> 455  -> 45  -> 4   -> 0
reverted: 0   -> 4    -> 45  -> 455 -> 4554

其实revert反转到45的时候,就可以停下来了。因为此时origin正是整数前半部分,如果是回文,那么reverted和origin应该是相等的。

另外你需要注意的是:奇数位的整数是否是回文与正中间的数字无关。

好了,自己写写代码试试吧~

复杂度分析

+

  • 时间复杂度:
  • 空间复杂度:

C++参考代码

+

public:
    bool isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;

        int revert = 0;
        while(x > revert) {
            revert = revert * 10 + x % 10;
            x /= 10;
        }

        return revert == x || revert / 10 == x ? true: false;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 互联网西门二少 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档