一、题目

有效数字（按顺序）可以分成以下几个部分：

  1.   1. 一个 **小数** 或者 **整数**
  2.   1. （可选）一个 'e' 或 'E' ，后面跟着一个 **整数**

小数（按顺序）可以分成以下几个部分：

  1.   1. （可选）一个符号字符（'+' 或 '-'）
  2.   1. 下述格式之一：
  3.      1. 至少一位数字，后面跟着一个点 '.'
  4.      1. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
  5.      1. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1.   1. （可选）一个符号字符（'+' 或 '-'）
  2.   1. 至少一位数字

部分有效数字列举如下：

  • ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

  • ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

点击查看原题
难度级别：困难（实际感觉不是很难）

二、思路

1）分段处理

这个思路很简单，就是根据题意分段去验证是否符合题意。
先找到e的下标，整体分为两段进行验证。
前半段：
找到小数点，又分为两段验证
后半段：
直接验证

2）确定有限状态自动机（摘自官方题解）

挖掘出所有状态：

  1.      1. 初始状态
  2.      1. 符号位
  3.      1. 整数部分
  4.      1. 左侧有整数的小数点
  5.      1. 左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
  6.      1. 小数部分
  7.      1. 字符 e
  8.      1. 指数部分的符号位
  9.      1. 指数部分的整数部分

65. 有效数字-每日一题 - 图1

三、代码

1）分段处理

  1. class Solution {
  2.     public boolean isNumber(String s) {
  3.         char[] cs = s.toCharArray();
  4.         int eLoc = findELocation(cs);    // 找到e所在的下标，如果没有e，eLoc的值就为cs.length
  5.         return checkPre(cs, 0, eLoc) && checkBack(cs, eLoc + 1);
  6.     }
  7.     private boolean checkBack(char[] cs, int eLoc) {
  8.         if (eLoc == cs.length) {    // 有e，但后面没有数字的情况
  9.             return false;
  10.         } else if (eLoc > cs.length) {    // 没有e
  11.             return true;
  12.         }
  13.         if (cs[eLoc] == '+' || cs[eLoc] == '-') {    // 去掉有符号的情况
  14.             eLoc++;
  15.         }
  16.         return isAllNumber(cs, eLoc, cs.length);    // 验证（eLoc, cs.length）部分是否全为数字
  17.     }
  18.     private boolean checkPre(char[] cs, int s, int eLoc) {
  19.         int dotLoc = findDotLocation(cs, s, eLoc);
  20.         if (cs[s] == '+' || cs[s] == '-') {    // 去掉有符号的情况
  21.             s++;
  22.         }
  23.         if (eLoc - s >= 2)    // 2个或更多个字符（包含了.前或后有数字的情况）
  24.             return isAllNumberOrNone(cs, s, dotLoc) && isAllNumberOrNone(cs, dotLoc + 1, eLoc);
  25.         else
  26.             return isSingleNum(cs[s]);    // 只有一个字符的情况进行判断
  27.     }
  28.     private int findDotLocation(char[] cs, int s, int e) {
  29.         for (; s < e; s++) {
  30.             if (cs[s] == '.') {
  31.                 break;
  32.             }
  33.         }
  34.         return s;
  35.     }
  36.     private boolean isAllNumberOrNone(char[] cs, int s, int e) {
  37.         while (s < e) {
  38.             if (!isSingleNum(cs[s])) {
  39.                 return false;
  40.             }
  41.             s++;
  42.         }
  43.         return true;
  44.     }
  45.     private boolean isAllNumber(char[] cs, int s, int e) {
  46.         if (s == e) {
  47.             return false;
  48.         }
  49.         while (s < e) {
  50.             if (!isSingleNum(cs[s])) {
  51.                 return false;
  52.             }
  53.             s++;
  54.         }
  55.         return true;
  56.     }
  57.     private int findELocation(char[] cs) {
  58.         int loc = 0;
  59.         for (; loc < cs.length; loc++) {
  60.             if (cs[loc] == 'e' || cs[loc] == 'E') {
  61.                 break;
  62.             }
  63.         }
  64.         return loc;
  65.     }
  66.     private boolean isSingleNum(char c) {
  67.         return (c >= '0' && c <= '9');
  68.     }
  70. }

时间复杂度为O(n)，空间复杂度为O(n)

2）确定有限状态自动机

  1. class Solution {
  2.     public boolean isNumber(String s) {
  3.         Map<State, Map<Symbol, State>> record = new HashMap();
  4.         Map<Symbol, State> initialMap = new HashMap() {{
  5.             put(Symbol.NUM, State.BASE_INTEGER);
  6.             put(Symbol.SIGN, State.SIGN);
  7.             put(Symbol.DOT, State.DOT_LNONE);
  8.         }};
  9.         record.put(State.INITIAL, initialMap);
  10.         Map<Symbol, State> signMap = new HashMap() {{
  11.             put(Symbol.NUM, State.BASE_INTEGER);
  12.             put(Symbol.DOT, State.DOT_LNONE);
  13.         }};
  14.         record.put(State.SIGN, signMap);
  15.         Map<Symbol, State> baseIntegerMap = new HashMap() {{
  16.             put(Symbol.NUM, State.BASE_INTEGER);
  17.             put(Symbol.DOT, State.DOT_LEXIST);
  18.             put(Symbol.E, State.E);
  19.             put(Symbol.END, State.END);
  20.         }};
  21.         record.put(State.BASE_INTEGER, baseIntegerMap);
  22.         Map<Symbol, State> dotLExistMap = new HashMap() {{
  23.             put(Symbol.NUM, State.BASE_DECIMAL);
  24.             put(Symbol.E, State.E);
  25.             put(Symbol.END, State.END);
  26.         }};
  27.         record.put(State.DOT_LEXIST, dotLExistMap);
  28.         Map<Symbol, State> dotLNoneMap = new HashMap() {{
  29.             put(Symbol.NUM, State.BASE_DECIMAL);
  30.         }};
  31.         record.put(State.DOT_LNONE, dotLNoneMap);
  32.         Map<Symbol, State> baseDecimalMap = new HashMap() {{
  33.             put(Symbol.NUM, State.BASE_DECIMAL);
  34.             put(Symbol.E, State.E);
  35.             put(Symbol.END, State.END);
  36.         }};
  37.         record.put(State.BASE_DECIMAL, baseDecimalMap);
  38.         Map<Symbol, State> eMap = new HashMap() {{
  39.             put(Symbol.SIGN, State.INDEX_SIGN);
  40.             put(Symbol.NUM, State.INDEX_NUM);
  41.         }};
  42.         record.put(State.E, eMap);
  43.         Map<Symbol, State> indexSignMap = new HashMap() {{
  44.             put(Symbol.NUM, State.INDEX_NUM);
  45.         }};
  46.         record.put(State.INDEX_SIGN, indexSignMap);
  47.         Map<Symbol, State> indexNumMap = new HashMap() {{
  48.             put(Symbol.NUM, State.INDEX_NUM);
  49.             put(Symbol.END, State.END);
  50.         }};
  51.         record.put(State.INDEX_NUM, indexNumMap);
  53.         // System.out.println(record.toString());
  54.         Map<Symbol, State> curruntStateMap = initialMap;
  55.         for (char c : s.toCharArray()) {
  56.             Symbol curruntSymbol = checkSymbol(c);
  57.             if (!curruntStateMap.containsKey(curruntSymbol)) {
  58.                 return false;
  59.             }
  60.             curruntStateMap = record.get(curruntStateMap.get(curruntSymbol));
  61.         }
  62.         return curruntStateMap.containsKey(Symbol.END);    // 判断该截至节点是否可以作为end节点
  63.     }
  64.     private Symbol checkSymbol(char c) {
  65.         if (c >= '0' && c <= '9') {
  66.             return Symbol.NUM;
  67.         } else if (c == 'e' || c == 'E') {
  68.             return Symbol.E;
  69.         } else if (c == '.') {
  70.             return Symbol.DOT;
  71.         } else if (c == '+' || c == '-') {
  72.             return Symbol.SIGN;
  73.         }
  74.         return Symbol.OTHER;
  75.     }
  76.     enum State {
  77.         INITIAL,
  78.         SIGN,
  79.         BASE_INTEGER,
  80.         DOT_LEXIST,
  81.         DOT_LNONE,
  82.         BASE_DECIMAL,
  83.         E,
  84.         INDEX_SIGN,
  85.         INDEX_NUM,
  86.         END
  87.     }
  88.     enum Symbol {
  89.         NUM,
  90.         E,
  91.         DOT,
  92.         SIGN,
  93.         OTHER,
  94.         END
  95.     }
  96. }

时间复杂度为O(n)，空间复杂度为O(1)