算法随笔_17: 回文数

上一篇: 算法随笔_16: 找出第k小的数对距离-CSDN博客

题目描述如下:

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

算法思路:

我们这样考虑这个问题。我们把这个数从中间对折一下，如果这个数是一个回文数，那么对折后，每个位置上的数字是相同的的。如果不是一个回文数，那么对折以后，某个位置上肯定有不一样的数字。因此我们只需要把这个整数的半个区间的数字排列倒序一下，看看是否和另半个区间相同即可。

那如何对半个区间倒序呢？我们可以按照如下算法去做:

1. 把x值赋予x_new。设倒序的数字为x_rev，初始值为0。

2. 对x_new整数取余，即，x_new%10，这样我们会取到最末尾的数字。然后我们把x_rev*10，并且累加这个末尾数，最后存储到x_rev。

3.  x_new=x_new/10，这样我们就消掉了x的最后一个数。然后重复步骤2，3，最后就得到了一个倒序数字x_rev。

还有一个问题，如何判断已经反转的位数已经进行了一半呢？

我们发现我们不断的对原来的数字除以10，对倒序的数字乘以10，那我们就可以判断，只要原来的数字小于等于倒序的数字，就说明反转的位数已经进行了一半。