题解 | #反转数字#

解题思路

• 由于是带符号整数，所以为了统一处理过程先取得参数x的符号位，记为flag;
• 如果x是正数则flag = 1， 如果x位负数则flag = -1， 同时将x取绝对值(x = -x);
• 通过将取x的余数将reverse的值从0开始不断增大： reverse = reverse*10 + x%10;; 通过取商不断将参数x的值缩小：x /= 10; x为0时结束循环
  • 边界判断：由于参数x反转后的值可能溢出，所以在每次将reverse增大后都要对reverse的值进行判断：如果当前reverse的值已经大于等于INT_MAX/10了，且参数x此时的值大于INT_MAX最后一位的值，则反转后的x必溢出，此时可直接返回0； 否则继续循环
• 循环结束表明x反转后的值未溢出，直接返回reverse与符号位flag的乘积即可。

代码

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int reverse(int x) {
        int flag;
        if(x > 0)
            flag = 1;
        else  {
            flag = -1;
            x = -x;            
        }
        int reverse = 0;
        while(x > 0)  {
            reverse = reverse*10 + x%10;
          	// 边界条件判断
            if(reverse >= INT_MAX/10 && x > INT_MAX%10)
                return 0;
            x /= 10;
        }
        
        return flag*reverse;
    }
};

复杂度分析

• 时间复杂度：O(logn)，每次都将x除以10，x循环到0的次数为：以10为底x的对数。
• 空间复杂度：O(1)