【LeetCode】 #9:回文数 C语言

最近打算练习写代码的能力,所以从简单题开始做。

大部分还是用C语言来解决。

@

题目

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121

输出: true

示例 2:

输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10

输出: false

解释: 从右向左读, 为 01 。因此它不是一个回文数。

具体链接 https://leetcode-cn.com/problems/palindrome-number/

思路

这与#7很相似,但是需要考虑方法的效率问题。

初步想法

初步的想法就是用一个while循环,在循环里面解决取余和倒序相加的工作。之后再用一个循环进行首尾比较。

具体代码如下:

bool isPalindrome(int x) {
if (x < 0 || x%10 == 0 && x != 0) return 0;
if (x / 10 == 0) return 1;
int a[20] = { 0 }, n = 0;
while (x) {
a[n] = x % 10;
x = x / 10;
n++;
} for (int i = 0; i < n / 2; i++){
if (a[i] != a[n-1-i]) return 0;
}
return 1;
}

需要注意的是,我们可以预先对数据进行判断,比如负数一定不是回文数,数字末尾为0的非0数也一定不是回文数,只有一位的数字一定是回文数。、

进一步想法

在看了官方题解后,提到了将数字本身反转,然后将反转后的数字与原始数字进行比较,如果它们是相同的,那么这个数字就是回文。

bool isPalindrome(int x) {
if (x < 0 || x%10 == 0 && x != 0) return 0;
if (x / 10 == 0) return 1;
int rev = 0;
while (x > rev) {
rev = x % 10 + rev * 10;
x = x / 10;
}
return x == rev || x == rev / 10;
}

需要注意的是由于预先不知道x是奇数位还是偶数位,所以最后的比较条件里出现了 x==rev/10.

最后想法

题目中也有提到将数字转换为字符串,我一开始想到用itoa,但是leetcode不支持这个函数,所以选用了sprintf来进行转换。

bool isPalindrome(int x) {
if (x < 0 || x % 10 == 0 && x != 0) return 0;
char a[20] = { 0 };
sprintf_s(a,"%d",x); for (int i = 0; i< (strlen(a) / 2); i++){
if (a[i] != a[strlen(a) - 1 - i]) return 0;
}
return 1;
}

参考链接

http://www.cnblogs.com/sddai/p/5774121.html

https://blog.csdn.net/xiaotaiyangzuishuai/article/details/79205773

总结

在简单问题上,不仅要注意到问题的解决,还要注重方法的效率问题,尝试用多种方法来解决。

上一篇:【LeetCode】9、Palindrome Number(回文数)


下一篇:[LeetCode] 906. Super Palindromes 超级回文数