0%

[0009] 回文数

发表于 更新于 分类于 ， 本文字数： 1.2k 阅读时长 ≈ 1 分钟
...

[0009] 回文数

题目描述

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

Related Topics
  • 数学

    • 题目解析

    • 本题是一道模拟题，关键是如何将整数翻转过来，与原数进行比较

    不确定性

    • 整数翻转后，值溢出的情况

    方法一：字符比较法

    分析

    • 将整数变为字符串，逐位进行比较

    思路

    • 先利用to_string()函数将整数转化为字符串
    • 由字符串两端开始分别进行对比

    注意

    • 在进行逐位比较时，可以同时从两端开始

    知识点

    • 字符串的遍历以及下角标的应用

    复杂度

    • 时间复杂度O(1)
    • 空间复杂度O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool isPalindrome(int x) {
    	if (x < 0){
    		return false;
    	}
    	string str = to_string(x);
    	for (string::size_type i = 0; i < str.size() / 2; i++){
    		if (str[i] == str[str.size() - 1 - i]){
    			continue;
    		}
    		else{
    			return false;
    		}
    	}
    	return true;
    }

    方法二：整数翻转法

    分析

    • 直接对整数进行翻转

    思路

    • 对整数进行翻转
    • 比较翻转后整数与原数是否一致

    注意

    • 整数类型的取值范围为[−2^31^, 2^31^ − 1] ，因此在翻转时需要注意溢出的情况

    知识点

    • 将整数从最低位到最高位进行翻转
    • 整数类型的取值范围

    复杂度

    • 时间复杂度O(1)
    • 空间复杂度O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    bool isPalindrome(int x){
    	if (x < 0){
    		return false;
    	}
    	long reverse = 0;
    	int temp = x;
    	while (temp){
    		reverse = reverse * 10 + temp % 10;
     		temp /= 10;
    	}
    	return reverse == static_cast<long>(x);
    }

    相关题目

    相关文章