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

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
简介: LeetCode(7-整数反转&&8-字符串转换整数 (atoi)&&9-回文数)

整数反转


题目描述:


给你一个 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类型就行了.就如下图所示的转换过程:


20210207202243594.png


按道理这个过程是可行的,但是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,另一种情况就是他们可能首部是一样的,但是尾部的结果超过范围了.就如下图所示:


20210222093737322.png


源代码:


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;
    }
}

20210207200929715.png


字符串转换整数


题目描述:


请你来实现一个 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;
    }
    }
}


20210207200646559.png


回文数


题目描述:


给你一个整数 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;
    }
}

20210222095701121.png


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


进阶版-数学解法


解题思路:

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


20210222105411666.png


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


源代码:

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;
    }
}

20210222112138397.png


进阶版-巧妙解法


解题思路:

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


算法的步骤如下图所示:


20210222113048454.png


源代码:

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


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;
    }
}

20210222115356393.png


这是大佬写的:


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,否则就不能是回文数.


20210222115446542.png


差距还是很明显的,1毫秒的差距.


相关文章
|
2月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
35 1
|
2月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
34 1
|
2月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
25 9
|
2月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
17 0
|
2月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
52 0
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
29 1