leetcode：9. 回文数

题目

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

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

示例：

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

解答 & 代码

解法一：反转数字并比较和原数是否相同

  1. class Solution {
  2. public:
  3.     bool isPalindrome(int x) {
  4.         // 如果是负数，直接返回 false
  5.         if(x < 0)
  6.             return false;
  8.         // 求反转数 reverseNum
  9.         int num = x;
  10.         long long reverseNum = 0;    // 注意要用 long long，否则可能会溢出
  11.         while(num != 0)
  12.         {
  13.             reverseNum = reverseNum * 10 + num % 10;
  14.             num = num / 10;
  15.         }
  16.         // 如果反转数和原数相同则返回 true，否则返回 false
  17.         return reverseNum == x;
  18.     }
  19. };

复杂度分析：整数 x

  • 时间复杂度[简单] 9. 回文数 - 图1：遍历 x 的所有数位
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 94.77% 的用户
  4. 内存消耗：5.9 MB, 在所有 C++ 提交中击败了 26.09% 的用户