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


        }

    }
};

全部评论

相关推荐

01-17 10:48
门头沟学院 Java
xxxxOxo:这公司幽默得很,要了简历半天一点动静都没有,过一会就给你发个邮件让你做测试,做完又没后文了,纯溜人
点赞 评论 收藏
分享
咩咩子_:项目和图形引擎岗没啥关系,最好还是项目和岗位有相关度好点,不然真有面也不一定会问很多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务