题解 | #牛的回文编号III#
知识点
字符串(回文),计算机基础(负数二进制补码,反码)
思路
此题难点不在于判断回文,而在于对负数的二进制处理。
非负数二进制
对一个数,如果其为非负整数,对其求二进制,只需不断将取模的结果作为放在高位(数组下标从大到小),并对原数除2即可,即:
int idx=1;
while (x) {
a[32 - idx] = x % 2;
x /= 2;
idx++;
}
负数二进制
如果其为负整数,对其求二进制,则需要进行如下操作:
1 把这个负数的绝对值转换为二进制,即求原码
2 把原码取反,即求反码
3 把反码加1,即求补码
以题目中的-5为例:(注意此题数据范围为二进制下32位)
1 求原码:即把-5的绝对值5转换为二进制 为 0000·····00000101
2 求反码:为 1111·······11111010
3 求补码:为 ······11111011
所以,为了求反码,我们可以先将全为0的二进制数组初始化为全为1,并在形如非负数取模的时候,将取模的结果取反依次放在数组高位(数组下标从大到小),
然后再进行求补码操作:对最后一位+1,不断向前进位,形如竖式加法。
for (int i = 0; i <= 33; i++)a[i] = 1;
int idx = 1;
while (x) {
a[32 - idx] = 1- (x % 2);//取反操作
x /= 2;
idx++;
}
int t = 1;//t为进位
for (int i = 31; i >= 0; i--) {
if (t == 0)break;//t为0时不再进位了,可以退出循环
if (a[i] == 1)a[i] = 0;//当前位置+1后对前一位产生进位
else {
a[i] = 1;//当前位置+1后不产生进位。
t = 0;
}
}
完成求二进制操作后,对a[0~31]判断是否为回文即可,判断回文可以去看前面几题。
完整代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param x int整型
* @return bool布尔型
*/
bool isPalindromeNumberIII(int x) {
// write code here
int a[35] = {0};
if (x == 0)return true;
else if (x < 0) {
x = -x;
for (int i = 0; i <= 33; i++)a[i] = 1;
int idx = 1;
while (x) {
a[32 - idx] = 1- (x % 2);
x /= 2;
idx++;
}
int t = 1;
for (int i = 31; i >= 0; i--) {
if (t == 0)break;
if (a[i] == 1)a[i] = 0;
else {
a[i] = 1;
t = 0;
}
}
//for(int i=0;i<=31;i++) cout<<a[i]<<" ";
for (int i = 0, j = 31; i < j; i++, j--) {
if (a[i] != a[j])return false;
}
return true;
} else {
int idx = 1;
while (x) {
a[32 - idx] = x % 2;
x /= 2;
idx++;
}
//for(int i=0;i<=31;i++) cout<<a[i]<<" ";
for (int i = 0, j = 31; i < j; i++, j--) {
if (a[i] != a[j])return false;
}
return true;
}
}
};