LeetCode-Palindrome Number
1720 ワード
タイトル
Determine whether an integer is a palindrome. Do this without extra space.
このような返信タイプの問題は以前にも行われていました.例えば、文字列が返信されたかどうか、一般的なアルゴリズムは以下の通りです.
本題を読んで、厳しい要求を加えた.余分な空間は使用できないので,第1の反応で文字配列に変換するスキームは塞がれる.もう一つの考え方は、数字の逆順序を話して、2つの数字が等しいかどうかを比較することです.整数逆シーケンスのコードは次のとおりです.
コードはかなり精錬されており,逸脱することもない.
Determine whether an integer is a palindrome. Do this without extra space.
このような返信タイプの問題は以前にも行われていました.例えば、文字列が返信されたかどうか、一般的なアルゴリズムは以下の通りです.
public boolean isPalindrome(String x) {
char[] chars = x.toCharArray();
for (int i = 0, j = chars.length -1; i < j; i++, j--) {
if (chars[i] != chars[j]) {
return false;
}
}
return true;
}
は、2つのポインタiおよびjを定義し、1つはフロントエンドを指し、後方に移動する.1つは末端を指し、前に移動します.終了条件は、2つが重なるか、真ん中に1つの数字があることです.本題を読んで、厳しい要求を加えた.余分な空間は使用できないので,第1の反応で文字配列に変換するスキームは塞がれる.もう一つの考え方は、数字の逆順序を話して、2つの数字が等しいかどうかを比較することです.整数逆シーケンスのコードは次のとおりです.
public int reverse(int x) {
long result = 0;
while (x != 0) {
result = result * 10 + x % 10;
x /= 10;
}
return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE ? -1 : (int)result;
}
逆順後の整数型逸脱を防止するために、long値を使用して、逸脱時に-1を返すなどの処理を行った.したがって、上記の方法によれば、本題はこのようにして解くことができる.public boolean isPalindrome(int x) {
if (x < 0)
return false;
int reverse = reverse(x);
if (reverse < 0) {
return false;
}
return x == reverse;
}
この方法は間違いなく可能であるが、十分に簡潔で、最適化できるかどうか.文字列の例を先に見ることができます.もちろん、文字列を逆順序にして比較することもできますが、上記の2つのポインタの方法は明らかに簡潔で効率的です.同じように、これは値で一部逆順にしなくてもいいですか?public boolean isPalindrome(int x) {
if (x < 0 || x != 0 && x % 10 == 0)
return false;
int y = 0;
while (y < x) {
y = y*10 + (x%10);
x /= 10;
}
return (x == y || y / 10 == x ? true : false);
}
コードはかなり精錬されており,逸脱することもない.