本文主要是介绍第九题:回文数字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给定一个整数 x ,编写一个函数来判断 x 是否为回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的数。例如,121 是回文,而 123 不是。
注意:
- 不能转换整数为字符串来处理。
- -2^31 <= x <= 2^31 - 1
实现思路
为了不将整数转换为字符串,可以考虑通过数学的方式来解决这个问题。一种方法是反转一半的数字,然后比较反转的部分是否与另一半相同。对于奇数位数的数字,在中间位上不需要做比较。
算法实现
C语言实现
#include <stdbool.h>bool isPalindrome(int x) {if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int reversedHalf = 0;while (x > reversedHalf) {int pop = x % 10;x /= 10;reversedHalf = (reversedHalf * 10) + pop;if (reversedHalf / 10 == x) { // 奇数位的情况break;}}return x == reversedHalf || x == reversedHalf / 10;
}
Python实现
def isPalindrome(x):if x < 0 or (x % 10 == 0 and x != 0):return Falsereversed_half = 0while x > reversed_half:reversed_half = (reversed_half * 10) + (x % 10)x //= 10if reversed_half // 10 == x:breakreturn x == reversed_half or x == reversed_half // 10
Java实现
public class Solution {public boolean isPalindrome(int x) {if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int reversedHalf = 0;while (x > reversedHalf) {reversedHalf = (reversedHalf * 10) + (x % 10);x /= 10;if (reversedHalf / 10 == x) { // Odd number of digitsbreak;}}return x == reversedHalf || x == reversedHalf / 10;}
}
时间复杂度
时间复杂度为 O(log n),其中 n 是输入数字 x 的大小。这是因为每次循环都会将 x 除以 10,直到 x 减少到小于反转的一半。由于我们是在处理整数的每一位,所以循环次数不会超过整数的位数,即 log(n)。
这篇关于第九题:回文数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!