LeetCode第九题：回文数

题目来源：LeetCode第九题

1.题目描述

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

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

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

示例 1：

输入：x = 121

输出：true

提示：

• -231 <= x <= 231 - 1

2.解题思路

解法一：字符串反转

• 描述：将数字转化为字符串，然后反转字符串，比较两者的不同。
• 时间复杂度：O(n)。n是数字的长度。
• 空间复杂度：O(n)。n是数字的长度。
• 参考代码：

java版：

class Solution {
    public boolean isPalindrome(int x) {
    // 小于0肯定不是回文，因为有符号
    if (x < 0)
    return false;

    // int转为string
    String s = Integer.toString(x);

    // 反转string
    String reversed = new StringBuilder(s).reverse().toString();

    // 返回比对的值
    return s.equals(reversed);
    }
}

C++版：

class Solution {
public:
    bool isPalindrome(int x) {
	// 小于0肯定不是回文，因为有符号
	if (x < 0)
		return false;
	// int转为string
	string s = to_string(x);

	string reversed = s;
	// 反转string
	reverse(reversed.begin(), reversed.end());

	return s == reversed;
    }
};

C版：

bool isPalindrome(int x) {
	// 负数不可能是回文数
	if (x < 0) {
		return false;
	}

	char s[50];  // 足够大的缓冲区存储整数转换为的字符串
	snprintf(s, sizeof(s), "%d", x);  // 将整数转换为字符串

	int length = strlen(s);

	// 判断是否为回文字符串
	for (int i = 0; i < length / 2; i++) {
		if (s[i] != s[length - 1 - i]) {
			return false;
		}
	}

	return true;
}

解法二：取反整数法

• 描述：对整数的每一位进行操作，从低位到高位取出数字并构建一个反转的整数，我们只需要反转整数的一半就行了，如何判断是否反转到了一半，可以通过比较反转后的数字是否大于或等于剩下的数字来实现。
• 时间复杂度：O(log(n))。我们并没有完全反转整个整数，而是只反转了其一半。所以我们就处理了n的一半位数。
• 空间复杂度：O(1)。我们只使用了常量级别的额外空间来存储反转的一半整数，并未使用与输入大小相关的额外空间。
• 参考代码：

java版：

class Solution {
    public boolean isPalindrome(int x) {
        // 如果x是负数或者x的最后一位等于0而且x又不是0的话，肯定不是回文
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversedNumber = 0;

        // 我们只反转一半的数，防止反转后的数字溢出
        // 例如 1221 当re变为21 x变为12时，循环结束
        // 12321 当re变为123 x变为12时，循环结束
        while (x > reversedNumber) {
            reversedNumber = reversedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当x的长度为偶数时，reversedNumber和x应完全相等
        // 当x的长度为奇数时，只需要考虑reversedNumber/10的值和x是否相等（中间的数不影响回文性）
        return x == reversedNumber || x == reversedNumber / 10;
    }
}

C++版：

class Solution {
public:
    bool isPalindrome(int x)
    {
        // 如果x是负数或者x的最后一位等于0而且x又不是0的话，肯定不是回文
        if (x < 0 || (x % 10 == 0 && x != 0))
        {
            return false;
        }

        int reversedNumber = 0;
        // 我们只反转一半的数，防止反转后的数字溢出
        // 例如 1221 当re变为21 x变为12时，循环结束
        // 12321 当re变为123 x变为12时，循环结束
        while (x > reversedNumber)
        {
            reversedNumber = reversedNumber * 10 + x % 10;
            x /= 10;
        }
        // 当x的长度为偶数时，reversedNumber和x应完全相等
        // 当x的长度为奇数时，只需要考虑reversedNumber/10的值和x是否相等（中间的数不影响回文性）
        return x == reversedNumber || x == reversedNumber / 10;
    }
};

C版：

bool isPalindrome(int x)
{
	// 如果x是负数或者x的末位是0（除了0这种情况），那么x不可能是回文数
	if (x < 0 || (x % 10 == 0 && x != 0))
	{
		return false;
	}

	int reversedNumber = 0; // 用于存储反转后的数字

	// 只反转一半，这样可以防止反转后的数字溢出
	while (x > reversedNumber)
	{
		reversedNumber = reversedNumber * 10 + x % 10; // 取出x的末位数字并添加到反转数字的末位
		x /= 10; // 去掉x的末位数字
	}

	// 当x的长度为偶数时，reversedNumber和x应完全相等
	// 当x的长度为奇数时，只需要考虑reversedNumber/10的值和x是否相等（中间的数不影响回文性）
	return x == reversedNumber || x == reversedNumber / 10;
}

解法三：双端队列法

• 描述：利用双端队列的特性，将整数的每一位都存进队列中，然后比较两端的数字是否相同，移除两端的数字，继续比较。
• 时间复杂度：O(n)。n是整数的位数。
• 空间复杂度：O(n)。创建了一个双端队列来存储整数的每一位数字。
• 参考代码：

java版：

class Solution {
public boolean isPalindrome(int x) {
        // 如果x是负数或者x的最后一位等于0而且x又不是0的话，肯定不是回文
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        Deque<Integer> deque = new LinkedList<>();

        int temp = x;

        // 将整数的每一位都入队
        while (temp != 0) {
            deque.addLast(temp % 10);
            temp /= 10;
        }

        // 从双端队列的前端和后端取出元素进行比较
        // 保证队列中至少两个元素
        while (deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }
        return true;
    }
}

C++版：

class Solution {
public:
	bool isPalindrome(int x)
	{
		// 如果x是负数或者x的最后一位等于0而且x又不是0的话，肯定不是回文
		if (x < 0 || x % 10 == 0 && x != 0)
		{
			return false;
		}

		deque<int> d;
		// 将整数的每一位都入队
		while (x != 0)
		{
			d.push_back(x % 10);
			x /= 10;
		}
		// 从双端队列的前端和后端取出元素进行比较
		// 保证队列中至少两个元素
		while (d.size() > 1)
		{
			if (d.front() != d.back())
			{
				return false;
			}
			d.pop_back();
			d.pop_front();
		}
		return true;
	}
};

C版：没有现成的双端队列，可以建一个数组，用两个指针从两端取值比较。这里只给出思路。