算法 1.1 数组:实现整数的数字反转【leetcode 7】
2020-12-27 本文已影响0人
珺王不早朝
题目描述
给出一个 32 位的有符号整数,将这个整数每位上的数字进行反转
数据结构
- 数组
算法思维
- 遍历、逆序、原地交换、数学思维:取模、累加
解题要点
- 数组的特点
- 数学思维的应用:遇到涉及数字的问题时,首先应该想到能否利用数学方法达到目标
解题思路
一. Comprehend 理解题意
可以理解为 “逆序输出” 或者 “首尾交换” 问题
二. Choose 选择数据结构与算法
数据结构:字符数组
算法思维:遍历
- 逆序输出
时间复杂度:O(n) -- 一次数组遍历
空间复杂度:O(2n) -- 两个数组的内存空间 - 首尾交换
时间复杂度: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)的数字反转?
- 字符串的反转?