算法 1.1 数组：实现整数的数字反转【leetcode 7】

题目描述

给出一个 32 位的有符号整数，将这个整数每位上的数字进行反转

数据结构

• 数组

算法思维

• 遍历、逆序、原地交换、数学思维：取模、累加

解题要点

• 数组的特点
• 数学思维的应用：遇到涉及数字的问题时，首先应该想到能否利用数学方法达到目标

解题思路

一. Comprehend 理解题意

可以理解为 “逆序输出” 或者 “首尾交换” 问题

二. Choose 选择数据结构与算法

数据结构：字符数组
算法思维：遍历

1. 逆序输出
   时间复杂度：O(n) -- 一次数组遍历
   空间复杂度：O(2n) -- 两个数组的内存空间
2. 首尾交换
   时间复杂度：O(n) -- 一次数组遍历
   空间复杂度：O(n) -- 一个数组的内存空间

三. Code 编码实现基本解法

以首尾交换法为例：

class Solution {
    public int reverse(int x) {
        //特殊值的处理
        if (x == Integer.MIN_VALUE){
            return 0;
        }

        // 处理符号
        int sign = x<0 ? -1 : 1;
        x *= sign;

        //1.整数 => 字符数组
        char[] arr = String.valueOf(x).toCharArray();

        //2.遍历数组，相对位置的元素交换
        int start = 0, end = arr.length -1;
        char temp;
        while(start < end){
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }

        //3.新字符数组 => 长整数
        long num = Long.parseLong(String.valueOf(arr));

        //判断溢出并返回
        boolean b = num < Integer.MAX_VALUE && num > Integer.MIN_VALUE;
        return b? (int)num * sign : 0;
    }
}

执行耗时:2 ms,击败了32.82% 的Java用户
内存消耗:35.5 MB,击败了73.56% 的Java用户

四. Consider 思考更优解

改变算法思维：操作的对象是整数，可以尝试使用数学思维解决问题

• “取模乘十”
  旧数字 /= 10 调整位数，旧数字 % 10 取末位数字，新数字 = 新数字 x 10 + 末位数字，循环
  时间复杂度：O(n) -- 一次整数的按位遍历
  空间复杂度：O(1) -- 一个长整数的内存空间（新数）

五. Code 编码实现最优解

class Solution{
  public int reverse(int x){
    long n = 0;
    while (x != 0){
      n = n * 10 + x % 10;
      x /= 10;
    }
  return (int)n == n ? (int)n : 0;
  }
}

执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:35.4 MB,击败了88.14% 的Java用户

六. Change 变形与延伸

• 长整型（long）的数字反转？
• 字符串的反转？