上一篇:?算法隨筆_16: 找出第k小的數(shù)對(duì)距離-CSDN博客

題目描述如下:

給你一個(gè)整數(shù)?x?，如果?x?是一個(gè)回文整數(shù)，返回?true?；否則，返回?false?。

回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

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

示例 1：

輸入：x = 121
輸出：true

算法思路:

我們這樣考慮這個(gè)問題。我們把這個(gè)數(shù)從中間對(duì)折一下，如果這個(gè)數(shù)是一個(gè)回文數(shù)，那么對(duì)折后，每個(gè)位置上的數(shù)字是相同的的。如果不是一個(gè)回文數(shù)，那么對(duì)折以后，某個(gè)位置上肯定有不一樣的數(shù)字。因此我們只需要把這個(gè)整數(shù)的半個(gè)區(qū)間的數(shù)字排列倒序一下，看看是否和另半個(gè)區(qū)間相同即可。

那如何對(duì)半個(gè)區(qū)間倒序呢？我們可以按照如下算法去做:

1.?把x值賦予x_new。設(shè)倒序的數(shù)字為x_rev，初始值為0。

2. 對(duì)x_new整數(shù)取余，即，x_new%10，這樣我們會(huì)取到最末尾的數(shù)字。然后我們把x_rev*10，并且累加這個(gè)末尾數(shù)，最后存儲(chǔ)到x_rev。

3.? x_new=x_new/10，這樣我們就消掉了x的最后一個(gè)數(shù)。然后重復(fù)步驟2，3，最后就得到了一個(gè)倒序數(shù)字x_rev。

還有一個(gè)問題，如何判斷已經(jīng)反轉(zhuǎn)的位數(shù)已經(jīng)進(jìn)行了一半呢？

我們發(fā)現(xiàn)我們不斷的對(duì)原來的數(shù)字除以10，對(duì)倒序的數(shù)字乘以10，那我們就可以判斷，只要原來的數(shù)字小于等于倒序的數(shù)字，就說明反轉(zhuǎn)的位數(shù)已經(jīng)進(jìn)行了一半。