Abnerの技术小栈
0%

LeetCode.9 - 回文数

发表于 更新于 分类于

题目描述

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number

解题思路

个人思路：将整型数字转为字符串，再逆转字符串后，每个字符一一比较
解决方案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func isPalindrome(_ x: Int) -> Bool {

        let number = String(x)
        let number_reversed = String(number.reversed())
        var isPalindrome = true

        for index in number.indices {
            if (number[index] != number_reversed[index]) {
                isPalindrome = false
            }
        }

        return isPalindrome

    }
}

算法问题：虽然能够解决问题，但遍历了整个字符串，时间复杂度为O(n)

算法优化

基本思路：将数字本身反转
特殊限制：
1、数字大小限制：<0的数不满足回文，0到9的数字直接满足回文，>=10的数需有分偶数位和奇数位
2、内存限制：int.Max=2^31-1=2147483647->7463847421，反转整个数字会超过整型内存限制，因此只转一半
（对于非负数x，num为偶数位，则迭代终止条件为num=revertedNumber；若x为奇数位，中间的数字转完即结束，因此迭代终止条件为num<revertedNumber）
主要思路：
1、判断是否转了一半数字（利用上面的迭代终止条件num<=revertedNumber）
1、取余拿到最低位
2、整除拿到除最低位的其他高位
3、revertedNumber原本的位数升一位+最低位
4、其他高位变为num
5、继续迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func isPalindrome(_ x: Int) -> Bool {
      var num = x;
      var revertedNumber = 0;
      
      // x 为非负数，或x大于等于10时，最后一位数字为0肯定不是回文
      if (x < 0 || (x >= 10 && x % 10 == 0)) {
        return false;
      }
      
      // 数字反转
      while (revertedNumber < num) {
        let onesPlace = num % 10;
        let tensPlace = num / 10;
        revertedNumber = revertedNumber * 10 + onesPlace;
        num = tensPlace;
      }
      
      // 满足（偶数位相同条件 || 奇数位相同条件）则是回文
      return (num == revertedNumber) || (num == (revertedNumber / 10));
    }
}