每日一个小算法之整数中每位上的数字进行反转 20190810
原创每日一个小算法之整数中每位上的数字进行反转 20190810
原创
凯哥Java
修改于 2019-08-12 11:26:54
修改于 2019-08-12 11:26:54
题目要求：
给出一个32位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入:?123
输出:?321示例 2:
输入:?-123
输出:?-321示例 3:
输入:?120
输出:?21示例 4:
输入：9646324351
输出:?0注意：
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [?2的31次方,? 2的31次方 ? 1]。
请根据这个假设，如果反转后整数溢出那么就返回 0。
解决方案1：
最low的方法
思路：
转换成字符串。获取最后第一位和最后一位。用于判断是否是负数和是否是0
然后在进行判断，根据情况不同进行判断处理。
如下代码：
public?int?reverse(int?x)?{
???String?strX?=?Integer.valueOf(x).toString();
???char?[]?charArr?=?strX.toCharArray();
???int?length?=?charArr.length;
???String?[]?strArr?=?new?String?[length];
???for(int?i?=0;i<length;i++){
???????strArr[i]?=?String.valueOf(new?char[]{charArr[i]});
???}
???String?[]?newStrArr?=???new?String?[length];
???String?fasterStr?=??strArr[0];
???String?lastStr?=?strArr[length-1];
???int?index?=?0;
????if("-".equals(fasterStr)
????????????&&?"0".equals(lastStr)){
????????newStrArr?=???new?String?[length-1];
????????newStrArr[0]?=?fasterStr;
????????for(int?i=?length-2;?i?>0;i--){
????????????index++;
????????????String?str?=?strArr[i];
????????????newStrArr[index]?=?str;
????????}
????}else?if("0".equals(lastStr)){
???????newStrArr?=???new?String?[length-1];
???????for(int?i=?length-2;?i?>=0;i--){
???????????String?str?=?strArr[i];
???????????newStrArr[index]?=?str;
???????????index++;
???????}
???}else?if("-".equals(fasterStr)){
???????newStrArr[0]?=?fasterStr;
???????for(int?i=?length-1;?i?>0;i--){
???????????index++;
???????????String?str?=?strArr[i];
???????????newStrArr[index]?=?str;
???????}
???}else{
???????for(int?i=?length-1;?i?>=0;i--){
???????????String?str?=?strArr[i];
???????????newStrArr[index]?=?str;
???????????index++;
???????}
???}
????String?str?=?"";
????for(int?i?=?0;i<newStrArr.length;i++){
????????str+=?newStrArr[i];
????}
???try{
???????if(""!=?str?&&?null?!=?str){
???????????Integer?ix?=?Integer.parseInt(str);
???????????x=ix.intValue();
???????}
???}catch?(Exception?e){
????????return?0;
???}
????return??x;
}此方案运行结果：
运行9毫秒，消耗内存35.4M
解决方案二：
从数学思维来处理的。
例如：1234 反过来就是4321
也就是个位和千百位互换、十位和百位互换。
这些明白了吧。也就是10的x方+Y%10.
其中x是位数。Y是数据。
看懂上面的，我们就能得到下面代码：
public?int?reverse2(int?x)?{
????//用数学思维来看
????int?rpc?=?0;
????while?(x?!=?0)
????{
????????int?newrpc?=?rpc*10?+?x%10;
????????log.info("rpc*10:{},x%10:{}，newrpc：{}",(rpc*10),x%10,newrpc);
????????if?((newrpc?-?x%10)/10?!=?rpc){
????????????return?0;
????????}
????????rpc?=?newrpc;
????????x?=?x/10;
????}
????log.info("==:{}",rpc);
????return?rpc;
}运行后打印日志：
我们在来看看此方案执行结果：
耗时3毫秒,内存消耗：34.3M
再来看第三种解决方案：
思路：使用字符串的反转方法。当溢出的时候异常直接返回0
public?int?reverse3(int?x)?{
????try?{
????????if(x?>?0)?{
????????????StringBuilder?str?=?new?StringBuilder().append(x);
????????????return?Integer.parseInt(str.reverse().toString());
????????}else?{
????????????StringBuilder?str?=?new?StringBuilder().append(-x);
????????????return?Integer.parseInt(str.reverse().toString())*(-1);
????????}
????}catch?(NumberFormatException?e)?{
????????return?0;
????}
}此方案运行结果：
方案4：
使用了math函数、位运算及字符串反转的
public?int?reverse4(int?x){
????//区域?右端点
????double?start?=??Math.pow(2,?31)?-?1;
????//区域?左端点
????double?end?=?-Math.pow(2,?31);
????if(x<end?&&?x>start){
????????return?0;
????}
????//获取原始数字符号
????float?df?=?Math.signum(x);
????Integer?intDf?=?Math.round(df);
????//?取绝对值
????int?i?=?Math.abs(x);
????//使用sring的反转方式
????StringBuilder?str?=?new?StringBuilder().append(i).reverse();
????x?=?Integer.parseInt(str.toString());
????log.info("==>:{}",x*intDf);
????return??x*intDf?;
}执行结果：
方案五：
使用的是位移运输和math函数。
public?int?reverse5(int?x)?{
????int?res?=?0;
????int?of?=?((1?<<?31)?-?1)?/?10;
????while?(x?!=?0)?{
????????if?(Math.abs(res)?>?((1?<<?31)?-?1)?/?10){
????????????return?0;
????????}
????????res?=?res?*?10?+?x?%?10;
????????x?/=?10;
????}
????return?res;
}执行结果：
?
我们将5种方案进行对比：
发现第二种和第五种方案耗时最短。也就是使用数学思路和位移运行最快。
经过五中方案比较之后，我们是不是体会到：编程是一门艺术了。
本文出处：凯哥Java(kaigejava)
凯哥个人博客：www.kaigejava.com
好了，今天小算法就到这里了。《每天一个小算法》希望直接可以坚持下去。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读