文档章节

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

一贱书生
 一贱书生
发布于 2016/08/08 16:00
字数 1606
阅读 25
收藏 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
博文 724
码字总数 600123
作品 0
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0
剑指offer之字符串是否为数值

题目 这是《剑指offer》上的一道题,刚开始觉得这是一道挺简单的题目,后来发现自己太年轻了,考虑的因素太少了,思考了而是分钟还是无从下手,看了作者的思路深深被他折服了,题目如下: 请...

firepation
09/05
0
0
剑指offer:2.二维数组的查找(Java版)

备注:本文参照《剑指offer第二版》 题目: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数, 输入这样的一个二维数组和一个整...

Tom-shushu
07/28
0
0
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
07/03
0
0
一起学Java7新功能扩展——深入历险分享(一)

特此声明:因网友疑问,这里声明一个重要的安全,就是大家所知的java惊现0day漏洞!8月30日,Oralce紧急发布了新版本的JDK和JRE,原因是发现了一个严重的0day漏洞CVE-2012-4681,远程攻击者可...

Beyond-Bit
2012/09/03
0
26

没有更多内容

加载失败,请刷新页面

加载更多

Java提高班(六)反射和动态代理(JDK Proxy和Cglib)

反射和动态代理放有一定的相关性,但单纯的说动态代理是由反射机制实现的,其实是不够全面不准确的,动态代理是一种功能行为,而它的实现方法有很多。要怎么理解以上这句话,请看下文。 一、...

王磊的博客
20分钟前
1
0
Ext grid 渲染

// 单元格字体颜色渲染function renderer_Meta_useStatus(value, cellmeta, record,rowIndex, columnIndex, store){ var color = ""; if("空闲"==value){ color = "green";......

MoksMo
30分钟前
4
0
log4j2在spring中的配置

<?xml version="1.0" encoding="UTF-8"?><!--日志级别以及优先级排序: OFF > FATAL > ERROR > WARN > INFO > DEBUG > TRACE > ALL --><!--Configuration后面的status,这个用于设置l......

TonyTaotao
36分钟前
3
0
java 中间变量缓存机制(i++,++i)

public class Test { public static void main(String[] args) { int i = 0; i = i ++ ; System.out.println(i); } } 答案是 0 如果是 i = ++......

shzwork
43分钟前
5
0
初识多线程及其原理-笔记

什么情况下应该使用多线程? 通过并行计算提高程序执行性能 需要等待网络、I/O响应导致耗费大量的执行时间, 可以采用异步线程的方式来减少阻塞 tomcat7 以前的io模型 客户端阻塞 线程级别阻...

Java搬砖工程师
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部