LeetCode(7-整数反转&&8-字符串转换整数 (atoi)&&9-回文数)

萌萌哒的瓤瓤

发布于 2022-01-06 14:16:31

2750

发布于 2022-01-06 14:16:31

整数反转

题目描述:

给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。示例 1：输入：x = 123 输出：321 示例 2：输入：x = -123 输出：-321 示例 3：输入：x = 120 输出：21 示例 4：输入：x = 0 输出：0

解题思路: 说实话,UP自己一开始是准备直接将还数据转换成String

然后再转换成StringBuilder的,然后直接通过StringBuilder的反转函数直获得反转之后的数据的.

再重新将StringBuilder转换成Int类型就行了.就如下图所示的转换过程:

按道理这个过程是可行的,但是UP在测试代码的过程中发现自己忽略了一点,那就是我们最后将字符串转换成Int的时候,数据可能已经超过int的数据范围了.并且题目中也明确说了我们需要判断是否超过了int的数据范围,所以这种方案是不可行的.那么我们只能换种方法了.

那这样我们选择通过 %取余以及*乘法这两个操作来帮助我们解决问题.其实我们可以发现 n进行%10操作后的数就是我们反转数据的队头元素,所以我们可以循环下面的操作

 int ans = 0;
        while(x != 0){
            //获得源数据的最后一位数
            int pop = x % 10;
            //开始获得反转数据
            ans = ans * 10 + pop;
            //最后一位已经添加完毕,所以源数据需要去除最后一位
            x /= 10;
        }
return ans;

到这里我们大部分的操作就已经完成了,但是题目中说了,我们最后的数据是可能超过int的数据范围的,所以我们还需要增加判断的步骤.但是呢我们又不可能直接将数据与MAX以及MIN比较,因为此时编译的过程就就会直接报错.所以我们只能选择其他的方法.

既然我们无法直接判断,那么我们就退而求其次,比较MAX/10以及MIN/10,这样我们就能直接判断了,这里我们只需要再注意一下判断的条件就行了.

一种情况就是直接大于MAX/10或者小于MIN/10,另一种情况就是他们可能首部是一样的,但是尾部的结果超过范围了.就如下图所示:

源代码:

class Solution {
   public int reverse(int x) {
        int ans = 0;
        while(x != 0){
            int pop = x % 10;
            //判断溢出的方法
            if(ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if(ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            ans = ans * 10 + pop;
            x /= 10;
        }
        return ans;
    }
}

字符串转换整数

题目描述:

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：读入字符串并丢弃无用的前导空格检查第一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。返回整数作为最终结果。注意：本题中的空白字符只包括空格字符 ’ ’ 。除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。示例 1：输入：s = “42” 输出：42 解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。第 1 步：“42”（当前没有读入字符，因为没有前导空格）第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）第 3 步：“42”（读入 “42”）解析得到整数 42 。由于 “42” 在范围 [-231, 231 - 1] 内，最终结果为 42 。示例 2：输入：s = " -42" 输出：-42 解释：第 1 步：" -42"（读入前导空格，但忽视掉）第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）第 3 步：" -42"（读入 “42”）解析得到整数 -42 。由于 “-42” 在范围 [-231, 231 - 1] 内，最终结果为 -42 。示例 3：输入：s = “4193 with words” 输出：4193 解释：第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）第 3 步：“4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）解析得到整数 4193 。由于 “4193” 在范围 [-231, 231 - 1] 内，最终结果为 4193 。示例 4：输入：s = “words and 987” 输出：0 解释：第 1 步：“words and 987”（当前没有读入字符，因为没有前导空格）第 2 步：“words and 987”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）第 3 步：“words and 987”（由于当前字符 ‘w’ 不是一个数字，所以读入停止）解析得到整数 0 ，因为没有读入任何数字。由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。示例 5：输入：s = “-91283472332” 输出：-2147483648 解释：第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）第 2 步："-91283472332"（读入 ‘-’ 字符，所以结果应该是负数）第 3 步："-91283472332"（读入 “91283472332”）解析得到整数 -91283472332 。由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648

解题思路: 这题目主要的就是我们需要分情况讨论,大几其实自己想想就知道我们应该分哪几种情况讨论了,主要有下面这几种情况: 直接就是正数 带+号的正数 负数在这几种情况下虽然我们截取数据的方式都是差不多的,但是还有一个过程我们需要考虑那就是我们还需要判断数据是否会越界,所以我们需要分情况进行讨论.

分完情况之后我们就好操作了.我们第一步就是先删除所有的前置空格,保留出我们剩下的有效数据.之后我们的操作就和我们上面反转数据的操作及其的类似,上面是反转,我们这里是正数截取. 大致的过程都是一样的,所以这里的逻辑以及代码都大差不差.并且这其中的数据越界的判断也是一样的. 所以这里就不过多讲解了. 源代码:

class Solution {
  //正数
	public int Intercept1(char[]ch) {
		int i=0;
		int res=0;
		while (i<ch.length) {
			if(ch[i]>='0'&&ch[i]<='9')
			{
				//超出Int的最大值
				if(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&& Integer.parseInt(""+ch[i])>7)) {
					return Integer.MAX_VALUE;
				}
				res=res*10+Integer.parseInt(""+ch[i]);
				i++;
			}	
			else 
				break;
		}
		return res;
	}
	//负数
	public int Intercept2(char[]ch) {
		int i=0;
		int res=0;
		while (i<ch.length) {
			if(ch[i]>='0'&&ch[i]<='9')
			{
				//超出Int的最小值	
				if(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&& Integer.parseInt(""+ch[i])>8)) {
					return Integer.MIN_VALUE;
				}
				res=res*10+Integer.parseInt(""+ch[i]);
				i++;
			}	
			else 
				break;
		}
		return 0-res;
	}
	public  int myAtoi(String s) {
		//先去除字符串前面可能存在的空格
		int l=0;
		while(l<s.length()) {
			if(s.charAt(l)==' ')
				l++;
			else 
				break;
		}
		s=s.substring(l);
		if(s.equals(""))
			return 0;
		if(s.charAt(0)=='-') {
			char []ch=s.substring(1).toCharArray();
			return Intercept2(ch);
			
		}
		if(s.charAt(0)=='+') {
			char []ch=s.substring(1).toCharArray();
			return Intercept1(ch);
		}
		if(s.charAt(0)>='0'&&s.charAt(0)<='9') {
			char []ch=s.toCharArray();
			return Intercept1(ch);
		}
		else {
			return 0;
		}
    }
}

回文数

题目描述:

给你一个整数 x ，如果 x 是一个回文整数，返回 ture ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。示例 1：输入：x = 121 输出：true 示例 2：输入：x = -121 输出：false 解释：从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。示例 3：输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。示例 4：输入：x = -101 输出：false

`普通解法`

解题思路: 回文串这个概念我们已经遇到好几次了,所以我们处理的方法也相应的就会有很多.这里一开始我们遇到这种问题的时候一般都是会选择通过一次遍历序列,主次的破案首尾元素是否相同.如果出现不同,那么我们就可以直接返回false.代码如下:

源代码:

class Solution {
public boolean isPalindrome(int x) {
		if(x<0)
			return false;
		char[] ch=String.valueOf(x).toCharArray();
		for(int i=0;i<ch.length/2;i++) {
			if(ch[i]!=ch[ch.length-1-i])
				return false;
		}
		return true;
    }
}

这个方法只遍历了一次我们的数据,并且只需要遍历一般的元素,速度也还可以.但是看了别人的题解之后发现也很不错,这里也推荐给大家.

`进阶版-数学解法`

解题思路: 这里面我们主要运用的操作还是我们上面用到的操作即取余以及取整操作.大体的思路如我下图所示:

其实在时间复杂度上啊,上述两者的区别可能没多大的区别.只是思维方式上的确有点创新

源代码:

class Solution {
public boolean isPalindrome(int x) {
		if(x<0)
			return false;
		int div=1;
		while(x/div>=10)
			div*=10;
		while(x>0) {
			int begin=x/div;
			int end=x%10;
			if(begin!=end)
				return false;
			//截取中间剩余的数据
			x=x%div/10;
			//因为已经截取了中间的数字
			//所以相应的div也应该排除首尾两位,所以对100进行取整
			div/=100;
		}
		return true;
    }
}

`进阶版-巧妙解法`

解题思路: 这种解法的思路其实主要就是来源于我们上面关于反转数字的题目.我们之前的所有解法都是每次只比较两位,但是相应的我们是不是可以直接将我们后半段的数据直接进行反转,那么很显然我们只需要将后半段反转的数据直接与我们前半段的数据直接比较就可以判断是否是回文串了.可能我们只要稍微注意一下数据的长度,因为长度是奇数或者偶数的情况是稍微有点不一样的.所以我们需要加以区分.

算法的步骤如下图所示:

源代码: 这是我自己按照该算法思想写的代码

class Solution {
public boolean isPalindrome(int x) {
		if(x<0)
			return false;
		int length=String.valueOf(x).length();
		int right=0;
		for(int i=0;i<length/2;i++) {
		    right*=10;
		    right+=x%10;
			x/=10;
		}
		if(length%2!=0)
			x/=10;
		if(x!=right)
			return false;
		return true;
    }
}

这是大佬写的:

class Solution {
    public boolean isPalindrome(int x) {
        //思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

不知道大家有没有去想过大佬注释中的问题.这里我想了一下,就说一下我的看法吧:

首先我们要知道我们这是我们第一步的判断并不是之后所有的操作都要进行这个判断

其次我们再来分析,既然是第一次判断那么肯定是在对原来整个数据进行判断,那么我们就能知道了,因为显然如果一开始的数据的末尾是0的话,那么很显然根据回文数的定义,源数据的首位那么对应的也应该是0,既然这样首位既然都是0的话,那么很显然这个这个数只能是0,否则就不能是回文数.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/02/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度