- 难度:
简单
- 本题涉及算法:
算数
双向指针
- 思路:
算数
双向指针
- 类似题型:
题目 9. 回文数
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗?
方法一 算数
- 解题思路:
- 数值反转
- 复杂度分析:
- 时间复杂度 $O(n)$ ,$N$ 表示数值包含元素长度
- 空间复杂度 $O(1)$
java
class Solution {
public boolean isPalindrome(int x) {
if(x < 0) // 如果为负数,直接返回 false
return false;
int cur = 0;
int num = x;
while(num != 0) {
cur = cur * 10 + num % 10;
num /= 10;
}
return cur == x; // 最后比较 数值反转前后是否相等
}
}
python
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0: # 如果为负数,直接返回 false
return False
num = x
cur = 0
while num !=0:
cur = cur*10 + num%10
num //=10
return cur == x # 最后比较 数值反转前后是否相等
方法二 双向指针
- 解题思路:
- 数值转成字符串,遍历元素
- 首尾各一个指针,向中间靠拢,每次元素是否相等
- 复杂度分析:
- 时间复杂度 $O(n/2)$ ,$N$ 表示数值包含元素长度 ,如果数值是回文数 最多需要遍历 $O(n/2)$ 次
- 时间复杂度 $O(1)$
java
class Solution {
public boolean isPalindrome(int x) {
if(x<0){ // 如果为负数,直接返回 false
return false;
}
String strNum = String.valueOf(x);
for(int i = 0;i<=strNum.length()/2;i++) {
int a = strNum.charAt(i);
int b = strNum.charAt(strNum.length()-1-i);
if(a != b) {
return false;
}
}
return true;
}
}
python
class Solution(object):
def isPalindrome(self, x):
nums = str(x)
for i in range(len(nums)):
if nums[i] != nums[len(nums)-1-i]:
return False
return True
方法三 取出后半段数字进行翻转
- 解题思路具体步骤
- 每次进行取余操作 ( %10),取出最低的数字:
y = x % 10
- 将最低的数字加到取出数的末尾:
revertNum = revertNum * 10 + y
- 每取一个最低位数字,x 都要自除以 10
- 判断 x 是不是小于
revertNum
,当它小于的时候,说明数字已经对半或者过半了 - 最后,判断奇偶数情况:如果是偶数的话,revertNum 和 x 相等;如果是奇数的话,最中间的数字就在revertNum 的最低位上,将它除以 10 以后应该和 x 相等。
- 每次进行取余操作 ( %10),取出最低的数字:
- 主要事项
- 这里需要注意的一个点就是由于回文数的位数可奇可偶,所以当它的长度是偶数时,它对折过来应该是相等的;当它的长度是奇数时,那么它对折过来后,有一个的长度需要去掉一位数(除以 10 并取整)。
- 复杂度分析:
- 时间复杂度 $O(n/2)$ ,$N$ 表示数值包含元素长度 ,如果数值是回文数 最多需要遍历 $O(n/2)$ 次
- 时间复杂度 $O(1)$
class Solution {
public boolean isPalindrome(int x) {
//思考:这里大家可以思考一下,为什么末尾为 0 就可以直接返回 false
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
}
PREVIOUS11. 盛最多水的容器