阿亮的算法之路——7. 整数反转

阿亮的算法之路——7. 整数反转

题目描述

这题难度是简单，的确是这样。

首次尝试

思路

其实我一开始想到了移位，因为进行移位运算，效率更高，但是没不知道要怎么移位，或者说移位能不能实现，所以就用了最笨的办法，先实现功能。

要将一个数反转，计算出他的位数，然后再依次取出每一位，乘以相应的位权即可，最后求和。

例如：12，首先计算出它又两位，然后，取出2 乘以 10^(2-1)，再取出1乘以10^(2-2)，最后将其求和。

代码

		int y = x;int count = 0;while (y != 0){y = y/10;count ++;}long re = 0;for (int i = count-1;i >=0; i--){int temp = x%10;re += temp*Math.pow(10,i);x = x/10;}if (re > Integer.MAX_VALUE || re < Integer.MIN_VALUE)  { return 0; }return (int)re;

逻辑很简单，但是可能效率不是很理想，因为用了两次循环，我想一次搞定的，但是做不到，因为需要预先知道这个数的位数，才能在取出每个数字的时候，乘以相应的位权。

提交结果

果然不是很理想，我想到了另一个办法。

换个思路

上面那种做法，需要先统计出这个数字的位数，所以需要两次循环。那我能不能直接将这个数的每个位数直接交换呢？将这个数转换成一个字符数组不就好了嘛

代码

		boolean isMinus = false;if (x < 0){if (x == Integer.MIN_VALUE) return 0;x = -x;isMinus = true;}char[] chars = (x+"").toCharArray();int len = chars.length;for (int i = 0; i < len/2; i++){char temp = chars[len-1-i];chars[len-1-i] = chars[i];chars[i] = temp;}long re = Long.valueOf(new String(chars));if (isMinus)  re = - re;if (re > Integer.MAX_VALUE || re < Integer.MIN_VALUE) return 0;return (int)re;

提交结果

内存方面提高了不少，但是效率？？效率为啥还降低了？现在遍历的次数，相当于是前一个思路的四分之一，按道理效率应该会提升诶，难道是转换成字符数组，会很耗时？

大佬思路

大佬果然是大佬，也是和我第一个方法那样的思路，但是处理得如此巧妙。我第一个方法，是先统计出有多少位，所以有了两次循环。大佬只用了一次循环，在取出每个数字的时候，就处理了。

代码

		int rev = 0;while (x != 0) {int pop = x % 10;x /= 10;if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;rev = rev * 10 + pop;}return rev;

提交结果

优秀啊！