题目：给出一个32 位的有符号整数，将这个整数每位上的数字进行反转，具体见 Leetcode 7：https://leetcode-cn.com/problems/reverse-integer/

1. 解法一：暴力解法

1.1 解题思路

解法一，暴力解法 思路：
1.整数转字符串，再转字符数组
2.反向遍历字符数组，并将元素存储到新数组中
3.将新数组转成字符串，再转成整数输出

注意事项：
  边界问题
      数组索引越界
      数值溢出边界：溢出则返回0
细节问题
  首位不为0
  符号处理

1.2 具体代码：

public class Solution {
    // 暴力解法
    public int reverse(int x) {
        if (x == Integer.MIN_VALUE ) {
            // 整数类型的最小值的绝对值 比 最大值的绝对值 大1
            return 0;
        }
        int sign = x > 0 ? 1 : -1;
        x  = x < 0 ? x * -1 :x;
        // 1.整数转字符串
        String str = String.valueOf(x);
        char[] chars = str.toCharArray();
        int len = chars.length;
        char[] array = new char[len];
        // 2. 反向遍历数组，并将元素存储到新数组中
        for(int i=0;i< len;i++){
            array[i] = chars[len - 1 -i ];
        }

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
        // 3. 将数组转成字符串，再转成整数输出
        long value = Long.parseLong(String.valueOf(array));
        System.out.println("转成字符串:"+value);
        boolean b = value > Integer.MAX_VALUE;
        int result = b ? 0 : (int) value;
        return result * sign;

    }
}

View Code

1.3 复杂度分析

 

(1) 时间复杂度

• 将整数转成字符串O(n)
• 遍历数组O(n)
• O(n)+O(n)=O(2n) ====>忽略常数：O(n)

(2) 空间复杂度 

• 一个字符串O(n)
• 一个新数组O(n)
• O(n)+O(n)=O(2n) ====>忽略常数：O(n)

(3) leetcode执行结果

 

 

 

2. 解法二：优化(两端对应位置的数字进行交换)

2.1 解题思路

解法二，优化解法 思路：
1.整数转字符串，再转字符数组
2.交换首位(start)和末位(end)数字
3.循环操作：依次交换第二(start++)和倒数第二个(end--)
直到数组剩下1个或0个元素
4.将原数组转成字符串，再转成整数输出

注意事项：
  边界问题
      数组索引越界：数组长度为偶数，反转完成标志为start>end；
          为奇数时反转完成标志为start==end
      数值溢出边界：溢出则返回0
  细节问题
      首位不为0
      符号处理

 

2.2 具体代码：

 1 public class Solution {
 2     public int reverse(int x) {
 3         if (x == Integer.MIN_VALUE ) {
 4             // 整数类型的最小值的绝对值 比 最大值的绝对值 大1
 5             return 0;
 6         }
 7         int sign = x > 0 ? 1 : -1;
 8         x  = x < 0 ? x * -1 :x;
 9         // 1.整数转字符串
10         String str = String.valueOf(x);
11         char[] chars = str.toCharArray();
12         int start = 0;
13         int end = chars.length - 1;
14         // 2. 反向遍历数组，并将元素存储到新数组中
15         while(start < end){
16             char mid = chars[start];
17             chars[start] = chars[end];
18             chars[end] = mid;
19             start ++;
20             end --;
21         }
22         // 3. 将数组转成字符串，再转成整数输出
23         long value = Long.parseLong(String.valueOf(chars));
24         boolean b = value > Integer.MAX_VALUE;
25         int result = b ? 0 : (int) value;
26         return result * sign;
27     }
28 }

View Code

 

2.3 复杂度分析

(1) 时间复杂度

• 将整数转成字符串O(n)
• 遍历数组O(n)
• O(n)+O(n)=O(2n) ====>忽略常数：O(n)

(2) 空间复杂度 

• 一个字符串O(n)
• 一个新数组O(n)
• 绝对空间消耗降低：O(n)

(3) leetcode执行结果

 

 

 

3. 解法三：数学思维解法

3.1 解题思路

最优解法 数学解法思路：
  1.尝试拿个位数字
      对10取模运算得到个位数字
  2.让每一位数字变成个位数字
      先除以10，再对10取模得到十位数字
      循环上述操作
  3.将每一位数字计算累加
      将上次累加结果*10 + 新数字

注意事项：
  边界问题：
    从低位到高位处理，最高位结束
          最高位 / 10 == 0
          最高位 % 10 == 最高位
     数值溢出边界：溢出则返回0
          用long类型存放，溢出int则返回0
          新整数补充最后一位前判断溢出
  细节问题：
          首位不为0
          符号处理

 

 

 

3.2 具体代码：

public class Solution {
    public int reverse(int x) {
        if (x == Integer.MIN_VALUE ) {
            // 整数类型的最小值的绝对值 比 最大值的绝对值 大1
            return 0;
        }
        int sign = x > 0 ? 1 : -1;
        x  = x < 0 ? x * -1 :x;
        int result = 0; // 返回结果
        // 1.尝试拿个位数字：对10取模运算
        // 2.让每一位数字变成个位数字：先除以10，再对10取模得到十位数字
        int last = 0; // 末位
        while ((last = x % 10) != x) {
            // 3.将每一位数字计算累加：将上次累加结果*10 + 新数字
            result = result * 10 + last;
            x /= 10;
        }
        if (last != 0) { // 此时last是最高位，单独处理
            long re = result;
            re = re * 10 + last;
            if (re > Integer.MAX_VALUE || re < Integer.MIN_VALUE) {
                result = 0;
            } else {
                result = (int)re;
            }
        }
        return result * sign;
    }
}

View Code

2.3 复杂度分析

(1) 时间复杂度

• 遍历整数的每一位：O(n)

(2) 空间复杂度 

• 只需要一个整数变量O(1)

(3) leetcode执行结果

 

 

总结: 考虑更优解的两个方向

1. 剔除无效代码或优化空间消耗   

• 操作是必须的吗？
• 数据结构是必须的吗？

2. 寻找更好的算法思维   

• 既然是整数，能否用数学思维？
• 借鉴其它算法

      此题的解法二就是省去一个新的数组，解法三利用的就是数学思维