title: 回文数-每天1LeetCode
date: 2024-07-16 11:05:16
tags: [算法]
categories: [每天1LeetCode]
题目
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
- -231 <= x <= 231 - 1
进阶：你能不将整数转为字符串来解决这个问题吗？
基础解法
使用索引的解法
#include <string>
using namespace std;
class Solution {
public:
bool isPalindrome(int x) {
// 特定值是回文数
if (x >= 0 && x < 10) { return true; }
// 小于10的肯定不是回文数
if (x < 0) { return false; }
// 先将x转换为字符串
string str = to_string(x);
for (int i = 0; i < str.length(); i++)
{
if (str[i] != str[str.length() - i - 1])
{
return false;
}
}
return true;
}
};
直接从两边开始比较就好了
使用指针的解法
#include <string>
using namespace std;
class Solution {
public:
bool isPalindrome(int x) {
// 0-9是回文数而小于0的肯定不是回文数
if (x < 0 || (x >= 0 && x < 10)) { return x >= 0; }
// 先将x转换为字符串
string str = to_string(x);
int left = 0, right = str.length() - 1;
while (left < right)
{
if (str[left] != str[right])
{
return false;
}
left++;
right--;
}
return true;
}
};
这种解法要比上一种解法快不少,因为经过的判断不是很多
进阶解法
#include <string>
using namespace std;
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int y = 0;
while (x > y) {
y = y * 10 + x % 10;
x = x / 10;
}
if (x == y || x == y / 10) { return true; }
else { return false; }
}
};
这种方法是取数字的一半,最后比较这两个一半是否相等,如果感觉不好理解的话可以看下面的表
| reversedHalf | x |
| :—: | :—: |
| 输入12321的情况 |
| 0 | 12321 |
| 1 | 1232 |
| 12 | 123 |
| 123 | 12 |
| 输入11的情况 |
| 0 | 11 |
| 1 | 1 |