C++判断回文数詳細版(超簡潔で面白い考え方)【元の数字が逆転し、2つの数字が同じかどうかを比較するとオーバーフローする】解決策
855 ワード
【考え方1】:既存の数字を逆転し、2つの数字が同じかどうかを比較する.(安全でない)
ただしintの制限により、正方向の数字が溢れていない可能性が高いが、逆方向の数字が溢れてしまう場合がある
(例:2147483647、回してオーバーフロー)
Intオーバーフロー後は、整数範囲が-21147483648~2147483647になるまで4294967296を減算または加算するので、直接回転すると整数値の変化を招き、比較が正しくない可能性があります.
【考え方2】整数を1ビットずつ配列中に存在させ、1ビットずつ比較するが、比較に関わる回数が多く、補助メモリとして配列も用いられる.
考え方は価値がある:全体の数を反転するのではなく、半分しか反転していない(利用条件:x>sum)ので、whileサイクルを出す可能性は2つしかない:1.xはsumと同桁であるがsum>=x(元の整数が偶数桁の場合)2.sumはxより1ビット高い(元の整数が奇数ビットの場合)
これにより,最終判断条件は2つ(x=sum)‖(x=sum/10)となる.
半分をひっくり返す方法で、整数が範囲外になることを徹底的に回避するのは、非常に機知に富んでいる.
ただしintの制限により、正方向の数字が溢れていない可能性が高いが、逆方向の数字が溢れてしまう場合がある
(例:2147483647、回してオーバーフロー)
Intオーバーフロー後は、整数範囲が-21147483648~2147483647になるまで4294967296を減算または加算するので、直接回転すると整数値の変化を招き、比較が正しくない可能性があります.
【考え方2】整数を1ビットずつ配列中に存在させ、1ビットずつ比較するが、比較に関わる回数が多く、補助メモリとして配列も用いられる.
class Solution {
public:
bool isPalindrome(int x) {
if(x<0|| (x!=0 && x%10==0)) return false;
int sum=0;
while(x>sum)
{
sum = sum*10+x%10;
x = x/10;
}
return (x==sum)||(x==sum/10);
}
};
考え方は価値がある:全体の数を反転するのではなく、半分しか反転していない(利用条件:x>sum)ので、whileサイクルを出す可能性は2つしかない:1.xはsumと同桁であるがsum>=x(元の整数が偶数桁の場合)2.sumはxより1ビット高い(元の整数が奇数ビットの場合)
これにより,最終判断条件は2つ(x=sum)‖(x=sum/10)となる.
半分をひっくり返す方法で、整数が範囲外になることを徹底的に回避するのは、非常に機知に富んでいる.