LeetCode刷题实战9:求解回文数

程序IT圈

共 1458字,需浏览 3分钟

 ·

2020-08-13 22:40



算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


今天和大家聊的问题叫做求解回文数,我们先来看题面:


Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.


https://leetcode-cn.com/problems/palindrome-number


翻译


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


样例


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


解题分析


在本题中,负数不作为回文数考虑范围之内,但是输入依然可能为负,此时直接返回false即可。
首先,一种容易想到的方法是:将整个数取反后看和原来的数是否相同。
class Solution {  
public:
    bool isPalindrome(int x) {
        if (x<0)
            return false;
        long long int sum =0;
        long long int origin = x;
        while(x)
        {
            int num = x %10;
            sum = sum*10 + num;
            x/=10;
        }
        if(sum == origin)
            return true;
        else  
            return false;
    }
};

另外一种方法:根据回文数的特点,我们只需要判断左边一半和翻转后的右边一半是否相等即可。代码如下:

class Solution {
public:
    bool isPalindrome(int x) {
        // 负数肯定不是,以及首尾不对称的非0数
        if(x < 0 || (x % 10 == 0 && x != 0))
            return false;

        int rev = 0;
        while ( x > rev){
            rev = rev * 10 + x % 10; //将低位一半的数取反。
            x = int (x / 10);
        }
        //有rev >= x, 奇数情况下需要除去10
        return x == rev || x == int(rev/10);
    }
};

最后还有另外一种解法:类似与采用两个指针。
在循环体中,不断地比较第i位和倒数第i位,直到遇到最中间的1个数字(输入为奇数个数字)或者遇到最中间的2个数字(输入为偶数个数字)时结束。

bool isPalindrome(int x) {
  if (x < 0) return false;
  int div = 1;
  while (x / div >= 10) {
    div *= 10;
  }
  while (x != 0) {
    int l = x / div;
    int r = x % 10;
    if (l != r) return false;
    x = (x % div) / 10; //去掉两边的数
    div /= 100;
  }
  return true;
}


如果喜欢本文,请顺手点个赞或者转发吧。



上期推文:


LeetCode刷题实战1:在数组上遍历出花样

LeetCode刷题实战2:用链表模拟加法

LeetCode刷题实战3:最长不重复子串

LeetCode刷题实战4:两个正序数组的中位数

LeetCode刷题实战5:判断回文子串

LeetCode刷题实战6:Z字形变换

LeetCode刷题实战7:整数反转

LeetCode刷题实战8:字符串转换整数


浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报