欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法之整数反转

程序员文章站 2022-05-12 22:23:26
...

算法之整数反转

最近在刷LeetCode
记录一个沙雕的日常把自己笑哭的操作
算法之整数反转
好了,下面解题

终极笨逼脑瘫解法
用字符串+char数组解决
为什么是终极笨逼脑瘫解法呢,因为这种解法有投机取巧的成分

	public int rese(int x) {
		boolean flag = false;//插旗
		if (x > 0) {
			flag = true;//x如果是正数,修改flag为true
		} else {
			x = -1 * x;//x如果是负数,则转正
		}
		String str = String.valueOf(x);//将x转成String类型
		char[] str_char = str.toCharArray();//将str转成char数组
		char[] str_rev = new char[str.length()];//定义一个用于接收反转str的char数组
		for (int i = str.length() - 1; i >= 0; i--) {
			str_rev[str.length() - i - 1] = str_char[i];//倒序遍历str,返回反转char数组
		}
		str = String.valueOf(str_rev);//将反转数组转成String
		try {
			x = Integer.parseInt(str);//捕获溢出异常,很重要,等会说
		} catch (NumberFormatException e) {
			return 0;
		}
		if (flag) {
			return x;
		} else {
			return -1 * x;//前面修改x为整数,所以如果是负数还要还原
		}
	}

好了,终极解法看完了,来看看高级笨逼脑瘫解法
思路:

while(x!=0) {
			int pop=x%10;
			x/=10;
		}

这样做,从个位开始,我们可以依次取出每位上的数字,好,到这一步了,有没有什么想法?没有想法的童鞋请面壁
我这里用了StringBulider,捂脸,不过不重要,因为这也不是最优解,看代码

public int reverse(int x) {
		boolean flag = false;
		StringBuilder sb = new StringBuilder();
		if (x > 0) {
			flag = true;
		} else {
			x = -1 * x;
		}
		while (x != 0) {
			int pop = x % 10;
			x /= 10;
			sb.append(pop + "");
		}
		String str = sb + "";
		try {
			x = Integer.parseInt(str);
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			return 0;
		}
		if (flag) {
			return x;
		} else {
			return -1 * x;
		}
	}

好了,是不是感觉比第一的代码更加简洁,优化了很多,因为StringBulider感觉效率会高很多?
哈哈,他俩耗时一样,都是用了3ms,唯一的优点就是第二种方法比第一种节省了点内存,
没想到吧,StringBulider只有在处理大量字符串拼接时才有显著提升

最优解之前,先说一下为什么要捕获溢出异常,

Integer.MAX_VALUE;//2147483647;
Integer.MIN_VALUE;//-21 4748 3648

如果输入的值是1111111119,反序后则是9111111111,显然已经溢出,所以必须要捕获或者手动排除异常

最优解代码(非原创)
耗时1ms…

public int reverse(int x) {
        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;
    }

方便理解定义now=rev * 10 + pop
now要满足溢出,则必须是rev*10+pop>Integer.MAX_VALUE,那么就会出现以下情况

  • rev>Integer.MAX_VALUE/10时,因为还要+pop,所以now必定溢出
  • 当rev==Integer.MAX_VALUE时,因为还要+pop,如果pop>7,所以now溢出

反之一样
总结,算法之路还是很漫长,多刷题吧

相关标签: 整数反转