题解 | #牛的回文编号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;


        }

    }
};