从0打卡leetcode之day9--字符串转整型

前言

好久没更新了,今天是开学的第一天,这学期选了门算法的课,打算好好刷下《算法导论》这本书,可能接下来会一边分享leetcode的刷题贴,一边分享自己在书上所学的一些算法。欢迎你一起和我学习坚持下去

题目描述

实现 atoi,将字符串转为整数。

在找到第一个非空字符之前,需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号,选取该符号,并将其与后面尽可能多的连续的数字组合起来,这部分字符即为整数的值。如果第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

字符串可以在形成整数的字符后面包括多余的字符,这些字符可以被忽略,它们对于函数没有影响。

当字符串中的第一个非空字符序列不是个有效的整数;或字符串为空;或字符串仅包含空白字符时,则不进行转换。

若函数不能执行有效的转换,返回 0。

说明:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。如果数值超过可表示的范围,则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:

输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231)

解题

说真,有时候遇到这道题目描述很长的题,真的有点不想去看它,读个题意都花了好久,不过这也间接说明了自己刷的题实在是少。偷偷透露一下,有时候都不知道题目要我们干什么…..

刚开始的时候,以为像”0003333aaa”这样的字符串也返回0,提交的时候,根据系统的判断,前面的0也要像空格一样被忽略去掉。

对于这道题,我的想法很简单也很暴力,就是根据题目给的那些条件与限制,一条一条着去判断,虽然这道题不难,但觉得细节是真的挺多的,提交了好几次错误。

就是按照题目说的:

  1. 先去掉空格
  2. 判断正负数
  3. 用一个long的变量来保存目标整数,主要是为了方便判断该整数有没有越界。

直接上代码吧:

public int myAtoi(String str) {
        if(str == null){
            return 0;
        }
        int i = 0;//用来遍历字符串
        int flag = 1;
        long num = 0;

        //去除空格
        while(i < str.length() && str.charAt(i) == ' '){
            i++;
        }
        if(i < str.length() && str.charAt(i) == '-'){
            i++;
            flag = -1;
        }else if(i < str.length() && str.charAt(i) == '+'){
            i++;
            flag = 1;
        }

        while(i < str.length()){
            if(str.charAt(i) <= '9'&&str.charAt(i)>= '0'){
                num = num * 10 + (str.charAt(i) - 48)*flag;
                i++;
            }else{
                break;
            }
            //本来是放到最后来判断的,但是发现这个值还有可能超出long范围
            if(num > Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }else if(num < Integer.MIN_VALUE){
                return Integer.MIN_VALUE;
            }
        }
        return (int)num;
    }

本来我是把num放到最后来判断正负数,有没有超出最大整数,但发现题目给出的整数,连long类型也存不下,所以就只能一遍处理一边判断了。

下面是我把这些代码处理了一下,感觉看起来简洁点,也放出来给大家参考,同时欢迎大家能给出更见简洁的代码。

public int myAtoi2(String str) {
        if(str == null )return 0;
        int len = str.length();//由于多次用到,用一个变量存起来
        int i = 0;//用来遍历字符串
        int flag = 1;//用来判断正负数
        long num = 0;//存放目标数
        char[] arr = str.toCharArray();
        //去除空格
        while(i < len && arr[i] == ' ')i++;
        //判断正负数
        if(i < len && (arr[i] == '-' || arr[i] == '+')){
            flag = arr[i]=='-'? -1 : 1;
            i++;
        }
        while(i < len){
            if(arr[i] <= '9'&&arr[i]>= '0'){
                num = num * 10 + (arr[i] - '0')*flag;
                i++;
            }else{
                break;
            }
            //本来是放到最后来判断的,但是发现这个值还有可能超出long范围
            if(num > Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }else if(num < Integer.MIN_VALUE){
                return Integer.MIN_VALUE;
            }
        }
        return (int)num;
    }

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-09-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

经典算法学习之分治法(以排列、组合程序为例)

分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后再合并这些子问题的解来建立原问题的解。 分治法在每层递归是遵循的三个步...

43870
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

26560
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法

Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

54780
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

19650
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day09-重构随机点名器

Java基础-day09-重构随机点名器 1.案例介绍与演示 随机点名的案例由之前简单的Person对象,重构为相对完整的Person对象并使用。 2.案例回顾...

51460
来自专栏chenjx85的技术专栏

leetcode-31-下一个排列

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

14720
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

10240
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

30740
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

6310
来自专栏zaking's

用js来实现那些数据结构03(数组篇03-排序及多维数组)

  终于,这是有关于数组的最后一篇,下一篇会真真切切给大家带来数据结构在js中的实现方式。那么这篇文章还是得啰嗦一下数组的相关知识,因为数组真的太重要了!不要怀...

38550

扫码关注云+社区

领取腾讯云代金券