回文数

問題

整数xを指定します。xが回文数の場合はtrueを返し、それ以外の場合はfalseを返します。
回文数とは、左から右の順番と右から左の順番でどっち読んでも同じ整数になります。 たとえば、121は回文数ですが、123はそうではありません。

サンプル1:
入力:x = 121
出力: true
サンプル2:
入力:x = -121
出力: false
説明: 左から右には-121です。右から左には121-になりますので、回文数ではありません。
サンプル3:
入力: x = 10
出力: false
説明: 右から左には01です 。ですので、回文数ではありません。
サンプル4:
入力:x = -101
出力:false

Tips:
* -2^31^ <= x <= 2^31^ - 1

上級：整数を文字列に変換せずにこの問題を解決できますか？

ここで確認できます

->LeetCode 9 Palindrome Number

考え

最も直接な考えはもちろん回文数の定義で、数字を文字列に変換して、逆順に出力して、元の文字列と比較するのです。なので、Pythonで行くとすごく簡単にできそうです。例えば、以下のような解決とか。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

実行時間: 84ms,すべての Python3 で送信提出した中に88.59%のユーザを勝ちました
メモリ消費: 14.1MB,すべての Python3 で送信提出した中に5.01%のユーザを勝ちました

問題の中に上級な条件が付いてます。それは文字列は使用せずです。公式的な解決方法は半分反転ということです。すごいと思っています。

公式的な解決方法以下のように書いてあります。

数字自体を反転させて、反転された数字を元数字と比較します。同じであれば、この数字は回文数です。ただ、反転した後の数字がInt.MAXを超える可能性があります。

上のやり方だと、反転した後の数字がInt.MAXを超える可能性があるので、Int数字の半分だけを反転すれば、行けそうです。理由は元数字もし回文数だったら、後半を反転すると元数字の前半と同じはずです。

解答についての思考

公式的な解決方法は以下のステップになります。
まず、数字はマイナスの場合、直接にfalseを返します。0から9の間の数字だと、1桁しかないから、trueを返します。
次、数字を反転し始め、%10してから/10すれば、最後の1桁を得られます。この操作をループします。元数字の最後の1桁を削除します。
最後に、元数字は反転した数字より小さい時、ループを終了させて、結果をチェックできます。

Python

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        if x < 10:
            return True

        x1 = x % 10
        x = x // 10

        if 0 == x1:
            return False

        while(x > x1):
            tmp = x % 10
            x = x // 10
            x1 = x1 * 10 + tmp

        return x == x1 or x == (x1 // 10)

実行時間:76 ms, すべての Python3 で送信提出した中に58.47%のユーザを勝ちました
メモリ消費:14.8 MB, すべての Python3 で送信提出した中に77.86%のユーザを勝ちました

C++

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)   return false;
        if(x < 10)  return true;

        int x1 = x % 10;
        x = x / 10;

        if(0 == x1) return false;

        while(x > x1){
            int tmp = x % 10;
            x1 = x1 * 10 + tmp;
            x = x / 10;
        }

        return (x == x1) || (x == (x1 / 10));
    }
};

実行時間:12 ms, すべての C++ で送信提出した中に76.03%のユーザを勝ちました
メモリ消費:5.7 MB, すべての C++ で送信提出した中に80.47%のユーザを勝ちました

Kotlin

class Solution {
    fun isPalindrome(x: Int): Boolean {
        if(x < 0) return false
        if(x < 10) return true

        var x1: Int = x % 10
        var tmpX: Int = x / 10

        if(0 == x1) return false

        while(tmpX > x1){
            var tmp = tmpX % 10
            tmpX = tmpX / 10
            x1 = x1 * 10 + tmp
        }

        return tmpX == x1 || tmpX == (x1 / 10)
    }
}

実行時間:264 ms, すべての Kotlin で送信提出した中に48.48%のユーザを勝ちました
メモリ消費:33.9 MB, すべての Kotlin で送信提出した中に99.24%のユーザを勝ちました