leetcode 9 | 回文数 （两种不同的解决方式）
leetcode 9 | 回文数 （两种不同的解决方式）
ACM算法日常
修改于 2019-01-23 16:40:45
修改于 2019-01-23 16:40:45
note：本文采用Java和C两中语言实现，文末是C语言。
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。分析：是不是跟笔者一样，看到第一眼，想到的是将这个整数转化为字符串，然后用一个循环判断从第一字符开始与从最后一个字符开始是否是相同的字符~这种方法是可行的。tip：字符串的charAt(int index)方法返回字符串在index索引处的字符值。
代码1（使用字符串）实现：
public static boolean isPalindrome(int x) {
if (x < 0) { //如果为负数，则一定不是回文数
return false;
}
boolean result = true; //定义结果变量
String str = new Integer(x).toString(); //将x转化为整数
int length = str.length();
for (int i = 0; i < length; i++) { //判断字符串从头到尾与从尾到头是否相同
if (str.charAt(i) != str.charAt(length - 1 - i)) {
return false;
}
}
return result; //返回结果
}第一种实现代码执行时间为：241ms
进阶：但我们发现代码的执行时间较长，因为我们调用字符串对象的各种方法，增加了系统开销，让我们可以想想可不可以不用字符串来解决这个问题呢？当然可以，我们可以先将这个要判断的整数先反转一下，即个位变成最高位。。以此类推。那我们怎么进行反转呢？我们一起来看一张示意图，来看看反转的过程，从中总结出反转一个整数的实现过程。
比如我们要对整数1234516进行反转
我们可以观察得到，每次从数字中取出最后一位，放到res中，我们都需要将res中之前的数乘以10，并且本身在不断地减小，直到为0。这样，我们总结出了这两点，我们就可以得到如下的算法。
代码2（不使用字符串）实现：
public boolean isPalindrome(int x) {
if (x < 0) return false;
if (x == reverse(x)) return true; //如果原数与反转数相等，则是回文数
return false;
}
public int reverse(int x) { //反转方法
int result = 0;
do { //从最高位开始，逐个变为个位，十位....
int a = x % 10; //取最后一位
x = x / 10; //自身除以10(注意整数除以整数仍为整数)
result = result * 10 + a; //result之前的结果乘以10，再加上原数字的最后一位
} while (x > 0);
return result;
}第二种实现代码执行时间为：91ms
C语言版：
int isPalindrome(int x) {
if (x < 0)
return 0;
if (x == reverse(x))
return 1; //如果原数与反转数相等，则是回文数
return 0;
}
int reverse(int x) { //反转方法
int result = 0;
do { //从最高位开始，逐个变为个位，十位....
int a = x % 10; //取最后一位
x = x / 10; //自身除以10(注意整数除以整数仍为整数)
result = result * 10 + a; //result之前的结果乘以10，再加上原数字的最后一位
} while (x > 0);
return result;
}
int main(){ //此处为一个测试例子
int num = 12321;
printf("%d\n", isPalindrome(num));
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-12-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读