当前位置：首页 > news >正文

【牛客-算法】NC57 反转数字

news 来源：原创 2024/5/19 13:53:13

文章目录

🚩写在前面
题目描述
算法设计思路
算法实现（C语言）
- bug记录：一个负数取相反数运算，结果不变
运行结果
结束语：

🚩写在前面

🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！
🔥 推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

题目描述

原题：NC57 反转数字

描述
给定一个32位的有符号整数num，将num中的数字部分反转，最后返回反转的结果
1.只反转数字部分，符号位部分不反转
2.反转后整数num超过 32 位的有符号整数的范围 $2^{31}, 2^{31} − 1]$ ，返回 0
3.假设本题不允许存储 64 位整数(有符号或无符号，即C++不能使用long long ，Java不能使用long等)

数据范围:
$2^{31} <= x <= 2^{31}-1$

算法设计思路

反转思路：先计算整数的位数，然后通过除法、取模得到首位和末尾的数字，再交换数字。
先减一个数将原来的数字置零，然后加上新数与对应数位的乘积，就可以替换掉一个数位。

不反转符号位：新建一个变量 flag 保留符号位信息，将原数取绝对值，再反转。

超过32位有符号整数范围：若原数 num 满足：

数量级为 10 亿，个位大于 2
数量级为 10 亿，个位为 1 ~ 2，反转后数量级小于 10 亿

则可判断发生了溢出，返回 0。

算法实现（C语言）

#include<limits.h>


int reverse(int x ) {
    if(x == INT_MIN)//INT_MIN取相反数运算，数将不变
    {
        return 0;
    }

    bool fu = false;//x是否为负
    if(x < 0)
    {
        x = -x;
        fu = true;
    }
    int t = x;//x绝对值的备份

    bool big = false;//x的数量级是否为10亿
    if(x > 1000000000)
    {
        big = true;
    }
    
    int f = 1;//f数量级指向首位，e数量级指向末位；将向中间迭代
    int e = 1;
    while(x / f / 10 > 0) //得到x首位的数量级
    {
        f *= 10;
    }

    while(f > e)
    {
        int fNum = x / f % 10;//得到首、末位数字
        int eNum = x / e % 10;
        x = x - f * fNum + f * eNum;//交换数字
        x = x - e * eNum + e * fNum;
        f /= 10;//向中间迭代
        e *= 10;
    }

    int eNum = t % 10;
    if(big && (eNum > 2 || (eNum != 0 && x < 1000000000)))//反转后溢出
    {
        return 0;
    }

    if(fu)
    {
        x = -x;
    }

    return x;
}

bug记录：一个负数取相反数运算，结果不变

感觉这是一个不太容易意识到的 bug，还是数据边界的问题。int 的范围为 $2^{31}, 2^{31} − 1]$ ，而如果 x 为 $2^{31}$ ，则它的相反数为 $2^{31}$ ，已经超过了 int 的最大值 $2^{31}-1$ 。

在这里插入图片描述

#include<iostream>
#include<climits>
using namespace std;
int main(){
	int x = INT_MIN;
	cout << x << endl;
	int y = -x;
	cout << "取相反数：" << y << endl;
	return 0;
}