[数据结构与算法]LeetCode 7. 整数反转

示例 1：
输入：x = 123
输出：321

示例 2：
输入：x = -123
输出：-321

示例 3：
输入：x = 120
输出：21

示例 4：
输入：x = 0
输出：0

提示：

-2^31 <= x <= 2^31 - 1
->挑战链接<-
方法一：将整数转换位字符串在比较
题目描述很简单，但是由于考虑到x的范围问题，我们反转过后的整数有可能超出int所能存储的范围，况且题目也明确要求了，不能使用64位整型来存储；这时我们可以像字符串考虑，将输入的整数转换为字符串；字符串不存在溢出吧：然后再用字符串与字符串的比较来判断是否溢出；
首先int的范围是：-2147483648~2147483647
除去-2147483648这个点，所有值的绝对值<=2147483647对吧，也就是说当我们输入的x反转过后的绝对值如果是小于等于2147483647的那么说明我们反转过后的数据是没有发生溢出的，我们可以直接返回，如果是大于的，那么我们就直接返回0；
我们可以观察到输入的x最多有10位，反转过后也就最多有10位，加上\0,我们就需要开辟11个char类型的空间；也就是大小为11字节的char类型数组；
一个用于存放INT_MAX转换过后的字符串；//MAX
一个用于存放反转过后的X的字符串；//tmp
tmp需要先用’0’初始化，当然保证最后一个元素为\0
比如：

然后我们就可以利用strcmp函数比较两个字符串；
如果strcmp（MAX，tmp）<0,表示转换过后的x发生了溢出，直接返回0即可；
如果strcmp（MAX，tmp）>=0,表示转换过后未发生溢出，属于正常转换，我们把字符串转换回来就行了，同时乘以一个符号标识值（标识这个x是正数还是负数）；
具体代码实现：

void reverse_(char* s)
{
    int left = 0;
    int right = strlen(s) - 1;
    while (left < right)
    {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
        left++;
        right--;
    }
}
int reverse(int x) {
    if (x == INT_MIN)//如果输入进来的是int类型最小值，直接返回0
        return 0;
    int flag = 1;//标识输入的x是正数还是负数，最后返回的时候还需要乘上它
    if (x < 0)
        flag = -1;
    x = abs(x);//将x转换为正数来处理
    char tmp[11] = { 0 };//保存x反转过后的数字从最低位开始使用
    for (int i = 0; i <10; i++)//初始化临时数组；
        tmp[i] = '0';
    char MAX[11] = { 0 };//存放INT_MAX字符串
    sprintf(MAX, "%d", INT_MAX);//将最大值转换为字符串
    sprintf(tmp,"%d",x);//先将x转换为字符串，还未反转//sprintf会自动加上\0
    int len = strlen(tmp);//计算当前数字位数
    if (len < 10)//如果长度没到到10位将该位字符改为‘0’；//确保tmp数组始终与MAX数组一样长
        tmp[len] = '0';
    reverse_(tmp);//反转字符串//得到反转过后的x所对应的字符串
    if (strcmp(MAX, tmp) < 0)//与MAX作比较
        return 0;
    int ret = atoi(tmp);//将反转过后的字符串转换为整数
    return ret * flag;//带上正负号返回
}

时间复杂度：O（N）
空间复杂度：O（1）常数个额外空间

方法二：
我们也可以不用转换为字符串，直接进行判断：
直接上代码：

int reverse(int x){
 int tmp=0;//保留个位数
 int sum=0;//存储反转过后的值
 while(x)
 {
     tmp=x%10;
     int prev=sum;//保留上一次sum的值
     sum=prev*10+tmp;//如果这一步执行完了，sum没发生溢出，那么我根据这个公式逆算回去：既(sum-tmp)/10==prev一定是成立的；反之，如果sum发生溢出，那么(sum-tmp)/10==prev,一定是不成立的，因此我们每次跟新一次sum，就往回算一次，看看是否能得到上一次sum的值，如果能，则说明sum没发生溢出；如果不能则说明sum发生了溢出；
     if((sum-tmp)/10!=prev)//
     return 0;
     x/=10;
 }
 return sum;
}

但是很可惜的是，使用这个方法的话，在LeetCode上跑不过去，主要是由于Leetcode对于超出范围的数据不会保存进去，而是直接报错，这就导致我们这个方法跑不过去，但是这个方法真的很棒！！！

在vs上可以跑：

时间复杂度：O（N）
空间复杂度: O (1)