文档章节

剑指Offer(Java版):把字符串转换成整数

一贱书生
 一贱书生
发布于 2016/08/08 16:00
字数 1606
阅读 17
收藏 0
点赞 0
评论 0

题目:实现一个函数 stringToInt,实现把字符串转换成整数这个功能,不能使用 atoi 或者其他类似的库函数。

题目解析

这看起来是很简单的题目,实现基本功能 ,大部分人都能用10行之内的代码解决。可是,当我们要把很多特殊情况即测试用例都考虑进去,却不是件容易的事。解决数值转换问题本身并不难,但我希望在 写转换数值的代码之前,应聘者至少能把空指针,空字符串”“,正负号,溢出等方方面面的测试用例都考虑到,并且在写代码的时候对这些特殊的输入都定义好合 理的输出。当然,这些输出并不一定要和atoi完全保持一致,但必须要有显式的说明,和面试官沟通好。

这个应聘者最大的问题就是还没有养成在写代码之前考虑所有可能的测试用例的习惯,逻辑不够严谨,因此一开始的代码只处理了最基本的数值转换。后来我 每次提醒他一处特殊的测试用例之后,他改一处代码。尽管他已经做了两次修改,但仍然有不少很明显的漏洞,特殊输入空字符串”“,边界条件比如最大的正整数 与最小的负整数等。由于这道题思路本身不难,因此我希望他把问题考虑得极可能周到,代码尽量写完整。

概括起来有几种情况

1)字符串开头是“+”号或“-”号的处理

2)非法字符的判断(不是数字)

3)整数溢出问题。

看看Java函数库中的Integer.parseInt(String sting)的源码如何处理这些问题的。

/**
 * Parses the specified string as a signed decimal integer value. The ASCII
 * character \u002d ('-') is recognized as the minus sign.
 *
 * @param string
 *			the string representation of an integer value.
 * @return the primitive integer value represented by {@code string}.
 * @throws NumberFormatException
 *			 if {@code string} cannot be parsed as an integer value.
 */
public static int parseInt(String string) throws NumberFormatException {
  return parseInt(string, 10);
}
 
/**
 * Parses the specified string as a signed integer value using the specified
 * radix. The ASCII character \u002d ('-') is recognized as the minus sign.
 *
 * @param string
 *			the string representation of an integer value.
 * @param radix
 *			the radix to use when parsing.
 * @return the primitive integer value represented by {@code string} using
 *		 {@code radix}.
 * @throws NumberFormatException
 *			 if {@code string} cannot be parsed as an integer value,
 *			 or {@code radix < Character.MIN_RADIX ||
 *			 radix > Character.MAX_RADIX}.
 */
public static int parseInt(String string, int radix) throws NumberFormatException {
  if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
    throw new NumberFormatException("Invalid radix: " + radix);
  }
  if (string == null) {
    throw invalidInt(string);
  }
  int length = string.length(), i = 0;
  if (length == 0) {
    throw invalidInt(string);
  }
  boolean negative = string.charAt(i) == '-';
  if (negative && ++i == length) {
    throw invalidInt(string);
  }
 
  return parse(string, i, radix, negative);
}
 
private static int parse(String string, int offset, int radix, boolean negative) throws NumberFormatException {
  int max = Integer.MIN_VALUE / radix;
  int result = 0, length = string.length();
  while (offset < length) {
    int digit = Character.digit(string.charAt(offset++), radix);
    if (digit == -1) {
      throw invalidInt(string);
    }
    if (max > result) {
      throw invalidInt(string);
    }
    int next = result * radix - digit;
    if (next > result) {
      throw invalidInt(string);
    }
    result = next;
  }
  if (!negative) {
    result = -result;
    if (result < 0) {
      throw invalidInt(string);
    }
  }
  return result;
}

 parseInt(String string,  int  radix)判断了

1) radix进制超出范围 ( Character. MIN_RADIX  = 2, Character. MAX_RADIX )=36)

2)字符串为null

3)字符串长度为空

4)字符串第一位为“-”且只有一位

  没有异常之后进行 parse(String string,  int  offset,  int  radix,  boolean  negative) 判断,参数即字符串,偏移量,进制, negative (如果开头没有“-”则offset=0,negative=false,否则为offset=1,neagtive=true)

   在 parse(String string,  int  offset,  int  radix,  boolean  negative)主要进行了溢出的判断。利用 offset++来控制移动,  在 while  (offset < length)  循环中 直到倒数 第二位的时候,如果已经 小于  max = Integer.MIN_VALUE / radix 的话表明一定会溢出。例如"-2147483648"

倒数第二位的时候 :result= -214748364,max = -214748364,max>result不成立表明 可以进行最后一位的处理。

如下代码:

package cglib;


public class jiekou {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        try {
          System.out.println(parseInt("cao21'''474fefda8364fe7"));
          //System.out.println(parseInt(""));
          System.out.println(parseInt(null));
          System.out.println(parseInt("-2147483648"));
          System.out.println(parseInt("-2147483651"));
          System.out.println(parseInt("-2147483648"));
          System.out.println(parseInt("-21474836410"));
        } catch (MyException e) {
          // TODO 自动生成的 catch 块
          e.printStackTrace();
        }
    
      }
    
      private static int parseInt(String string) throws MyException {
        /* 异常情况1:字符串为null */
        if (string == null) {
          throw new MyException("字符串为null!");
        }
        int length = string.length(), offset = 0;
        /* 异常情况2:字符串长度为0 */
        if (length == 0) {
          throw new MyException("字符串长度为0!");
        }
        boolean negative = string.charAt(offset) == '-';
        /* 异常情况3:字符串为'-' */
        if (negative && ++offset == length) {
          throw new MyException("字符串为:'-'!");
        }
        int result = 0;
        char[] temp = string.toCharArray();
        while (offset < length) {
          char digit = temp[offset++];
          if (digit <= '9' && digit >= '0') {
            int currentDigit = digit - '0';
            /*
             * 异常情况4:已经等于Integer.MAX_VALUE / 10,判断要添加的最后一位的情况:
             * 如果是负数的话,最后一位最大是8 如果是正数的话最后一位最大是7
             */
            if (result == Integer.MAX_VALUE / 10) {
    
              if ((negative == false && currentDigit > 7)
                  || (negative && currentDigit > 8)) {
                throw new MyException("溢出!");
              }
              /*
               * 异常情况5:已经大于Integer.MAX_VALUE / 10
               * 无论最后一位是什么都会超过Integer.MAX_VALUE
               */
            } else if (result > Integer.MAX_VALUE / 10) {
              throw new MyException("溢出!");
            }
    
            int next = result * 10 + currentDigit;
            result = next;
          }
        }
        if (negative) {
          result = -result;
        }
        return result;
      }
    
    }
    
    /* 自定义异常 */
    @SuppressWarnings("serial")
    class MyException extends Exception {
      /**
       *
       */
      @SuppressWarnings("unused")
    private static  long serialVersionUID = 1749149488419303367L;
      String message;
    
      public MyException(String message) {
        // TODO 自动生成的构造函数存根
        this.message = message;
      }
    
      @Override
      public String getMessage() {
        // TODO 自动生成的方法存根
        return message;
      }
    }
   输出:

147483647
cglib.MyException: 字符串为null!
    at cglib.jiekou.parseInt(jiekou.java:25)
    at cglib.jiekou.main(jiekou.java:10)

 

或者:

package cglib;


public class jiekou {
    /**
     * 题目:实现一个函数stringToInt,实现把字符串转换成整数这个功能,
     * 不能使用atoi或者其他类似的库函数。
     *
     * @param num
     * @return
     */
    public static int stringToInt(String num) {
        if (num == null || num.length() < 1) {
            throw new NumberFormatException(num);
        }
        char first = num.charAt(0);
        if (first == '-') {
            return parseString(num, 1, false);
        } else if (first == '+') {
            return parseString(num, 1, true);
        } else if (first <= '9' && first >= '0') {
            return parseString(num, 0, true);
        } else {
            throw new NumberFormatException(num);
        }
    }
    /**
     * 判断字符是否是数字
     *
     * @param c 字符
     * @return true是,false否
     */
    private static boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }
    /**
     * 对字符串进行解析
     *
     * @param num      数字串
     * @param index    开始解析的索引
     * @param positive 是正数还是负数
     * @return 返回结果
     */
    private static int parseString(String num, int index, boolean positive) {
        if (index >= num.length()) {
            throw new NumberFormatException(num);
        }
        int result;
        long tmp = 0;
        while (index < num.length() && isDigit(num.charAt(index))) {
            tmp = tmp * 10 + num.charAt(index) - '0';
            // 保证求的得的值不超出整数的最大绝对值
            if (tmp > 0x8000_0000L) {
                throw new NumberFormatException(num);
            }
            index++;
        }
        if (positive) {
            if (tmp >= 0x8000_0000L) {
                throw new NumberFormatException(num);
            } else {
                result = (int) tmp;
            }
        } else {
            if (tmp == 0x8000_0000L) {
                result = 0x8000_0000;
            } else {
                result = (int) -tmp;
            }
        }
        return result;
    }
    public static void main(String[] args) {
      //System.out.println(Integer.parseInt(Integer.MIN_VALUE + ""));
     //   System.out.println(0x8000_0000L);
     //   System.out.println(stringToInt(""));
        System.out.println(stringToInt("123"));
        System.out.println(stringToInt("+123"));
        System.out.println(stringToInt("-123"));
        System.out.println(stringToInt("aaa"));
        System.out.println(stringToInt("+2147483647"));
        System.out.println(stringToInt("-2147483647"));
        System.out.println(stringToInt("+2147483648"));
        System.out.println(stringToInt("-2147483648"));
      System.out.println(stringToInt("+2147483649"));
      System.out.println(stringToInt("-2147483649"));
       System.out.println(stringToInt("+"));
        System.out.println(stringToInt("-"));
    }
    }
    


输出:
Exception in thread "main" java.lang.NumberFormatException: aaa
    at cglib.jiekou.stringToInt(jiekou.java:24)
    at cglib.jiekou.main(jiekou.java:80)
123
123
-123

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
Java开发每日复盘2018_0514

今天主要跟大家分享3个部分: 一、「Java的核心机制」 二、「Java命名规范」 三、「Java数据类型相关」 下面我们来一个一个的说: 「Java核心机制」 Java是一种强制面向对象的解释型语言(O...

ZeroOSTalk ⋅ 05/14 ⋅ 0

Java核心技术卷1 重读经典小记

Java基础 java中的int类型固定为32位 三个特殊的浮点值:正无穷大(),负无穷大()和NaN()。 在java中,char类型用UTF-16编码描述一个代码单元.不建议在程序中使用char类型. boolean类型的f...

java_龙 ⋅ 02/27 ⋅ 0

Java小白进阶笔记(2)-变量和数据类型

1.Java有多少种数据类型,数据类型的分类? 两种数据类型: 基本数据类型 引用数据类型 除了八种基本数据类型,其他的都是引用数据类型。 2.Java的工作机制? Java程序的源代码(.java)编译...

阿里云云栖社区 ⋅ 05/25 ⋅ 0

飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙 ⋅ 2016/01/15 ⋅ 0

JNI开发流程与引用数据类型的处理

今天我们来看下Java JNI,先看下维基百科给的定义, JNI, Java Native Interface, Java本地接口,是一种编程框架,使得Java虚拟机中的Java程序可以调用本地应用或库,也可以被其他程序调用。...

juexingzhe ⋅ 05/04 ⋅ 0

Java编程语言:Java的类型转换与多态

对于Java语言应该都不陌生,今天我们就将Java中的入门部分概念做一具体的讲解一下。 1.什么叫JVM,JRE,JDK? JRE 全称为JavaRunningEnvironment,就是我们所说的java运行环境,由java虚拟机和一...

启示录是真的 ⋅ 05/22 ⋅ 0

java编程学习常见面试题及答案

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/22 ⋅ 0

关于Java编程基础学习输入输出IO的问题

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/23 ⋅ 0

新浪、百度、好未来3offer到手全记录 | 牛客面经

新浪、百度、好未来3offer到手全记录 牛客面经 原创 2017-09-19 牛友 招聘消息汇总 渣渣的秋招之路 附上新浪,百度,好未来面经 作者:offer快到碗里来?。! 来源:牛客网 楼主是本科渣渣,...

公子只识黛玉 ⋅ 04/17 ⋅ 0

理解Java Integer的缓存策略

本文将介绍 Java 中 Integer 缓存的相关知识。这是 Java 5 中引入的一个有助于节省内存、提高性能的特性。首先看一个使用 Integer 的示例代码,展示了 Integer 的缓存行为。接着我们将学习这...

analogous_love ⋅ 04/26 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring Cloud构建微服务架构—创建“服务注册中心”

创建一个基础的Spring Boot工程,命名为eureka-server,并在pom.xml中引入需要的依赖内容: <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-par......

itcloud ⋅ 1分钟前 ⋅ 0

拖动

<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>event</title> <style> #box { width: 100px; height: 100px; background-color: aquamarine; position: absolute; } </style......

fyliujj ⋅ 4分钟前 ⋅ 0

es6 polyfill array

polyfill之javascript函数的兼容写法——Array篇 1. Array.isArray(obj) if (!Array.isArray) { Array.isArray = function(arg) { return Object.prototype.toString.call(arg) === '[objec......

球球 ⋅ 6分钟前 ⋅ 0

kibana启动异常

检查一下:kibana.yml 每一对key:value中,冒号之后应有空格。

增删改查1 ⋅ 8分钟前 ⋅ 0

js修改img的src属性刷新图片时的图片缓存问题

问题:上传一张图片,通过js更新src属性刷新图片使其即时显示时, 当img的src当前的url与上次地址无变化时(只更改图片,名称不变,不同图片名称相同)图片不变化(仍显示原来的图片) 但通过...

HaierBrother ⋅ 8分钟前 ⋅ 0

Mysql

1.Jdbc Url 设置allowMultiQueries为true和false mysql的批量更新是要我们主动去设置的, 就是在数据库的连接url上设置一下,加上* &allowMultiQueries=true *即可。 参数名称 参数说明 缺省...

瑟青豆 ⋅ 11分钟前 ⋅ 0

mysql导出导入表结构与数据

当我们需要进行数据迁移时,mysql自带的mysqldump会是最好的方式。 1.导出某张表的结构和数据 首先,我们应当使用服务器,打开终端,连接到所需要导出的表所在的服务器上。执行命令: mysqld...

hengbao5 ⋅ 11分钟前 ⋅ 0

世界杯也走向“比拼”大数据的时代

《日本经济新闻》6月19日报道称,俄罗斯足球世界杯已于6月14日揭开战幕。作为第21次举办的足球世界杯,如何活用大数据有可能成为决定各支球队胜负的重要因素。从对阵球队的分析到战术建议,还...

加米谷大数据 ⋅ 12分钟前 ⋅ 0

金额转为千分制,金额转中文大写

金额转关为大写 js /** 数字金额大写转换(可以处理整数,小数,负数) */ function digitUppercase(n){ if(!n) reutrn "" let fraction = ['角', '分']; let digit = ['零', '壹', '贰', '叁', ...

YXMBetter ⋅ 14分钟前 ⋅ 0

开发利器JRebel部署SpringBoot项目

不要以为年纪轻轻就跌倒了人生谷底,未来还有更大的下降空间等着你。 idea下载和安装JRebel 激活JRebel 访问https://my.jrebel.com/ 使用facebook或twitter登录 勾选 Build project automati...

郑龙飞 ⋅ 20分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部