LC 9、回文数

superJade / 2023-08-01 / 原文

LC 9、回文数

LeetCode上的 9、回文数，难度为简单

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

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

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

示例：

输入：x = 121

输出：true

字符串解法

将整数转换为字符串，并且判断是否为回文串，老生常谈的问题，直接给出代码：

class Solution{
	bool isPalindrome(int x){
		string str = to_string(x);
        int l = 0, r = str.size() - 1;
        while(l < r){
			if(str[l] != str[r]) return false;
            l++;
            r--;
        }
        return true;
    }
}

时间复杂度：数字n的位数，时间复杂度为O(log₁₀ⁿ)
空间复杂度：是哦那个了字符串作为存储，复杂度为O(log₁₀ⁿ)

非字符串解法（完全翻转）

原来 x 的不超过int 的表示范围，反转后值可能会有变化，所以我们使用long 类型的值来接收新的值。

class Solution{
	bool isPalindrome(int x){
		long long ans = 0;
        int t = x;
        while(t > 0){
			ans = ans * 10 + t % 10;
            t /= 10;
        }
        return ans - x == 0;
	}
}

时间复杂度：数字n的位数，时间复杂度为O(log₁₀ⁿ)
空间复杂度：O(1)

进阶（部分翻转）

我们只需要利用回文字符串的性质，前半部分和后半部分相同即可。

但是我们需要考虑一个情况，就是数字的位数问题：

奇数：需要考虑中间数字。
偶数：我们只需保证数字停在中间就可

所以，我们的数字的末尾，不可以是0，一定要保证产生位数压制。

class Solution{
	bool isPalindrome(int x){
		if(x < 0 || (x % 10 == 0 && x != 0)) return false;
		int t = 0;
		while(x > t){
			t = t * 10 + x % 10;
			x /= 10;
		}
		// 返回值，前者是指，为偶数的情况，后者是指，我们忽略掉了最中间一位
		return x == t || x == t / 10;
	}
}