乐趣区

关于java:offer-20-表示数值的字符串-有限状态自动机

jiezi

示意数值的字符串

字符串匹配算法：无限状态自动机


只有有进来的边能力对应变换状态，否则就会报错。

  • 例子：
    设置初始节点为 0，接管节点为 1，当进行一系列的输出，使得状态机的状态一直变动，只有最初一个输出使得状态机处于接管节点，那么就表明以后输出能够被状态机接管。例如对应字符串”abaaa”, 从初始节点 0 开始，状态机依据该字符串的输出所造成的状态变动序列为：{0，1，0，1，0，1}。因为最初状态机处于状态 1，所以该字符串能够被状态机接管。如果输出的字符串是:abbaa, 那么状态机的变动序列为：{0，1，0，0，1，0}，因为最初状态机处于非接管状态，因而这个字符串被状态机回绝。
    无限状态自动机 本题解说

    重点

    每次输出都会引起状态的扭转或者不变。再次输出一个值，状态又会扭转。，这种状况就用限状态自动机。

    本题思路

  • 找到所有状态列举进去，建设每次输出都扭转他状态的状态转移。如果最初的状态是非法的，那么证实这个输出符合条件。非法的状态就是满足题目要求
  • 依据题目要求找到状态: 也就是字符类型：
  • 依据字符类型定义不同的状态，本题分为 9 个状态
  • 完结状态
    非法的完结状态有 2, 3, 7, 8。
    满足题目要求

  • 状态非法之后再从新起点判断后续是否非法

  • 算法流程，首先定义一个状态数组，而后每个状态定义一个 HashMap，其中输出键值对，键对应输出的字符，值对应输出这个字符之后跳转到的新状态，而后把状态的 HashMap 放到状态数组里。

    留神

    • Map 生成一个外部类, 在结构器外面执行 put 办法
    private Map<Character,Character> map = new HashMap<Character,Character>(){
  {put('(',')');
      put('{','}');
      put('[',']');
  }
};

题解



这个是首先把字符串两端的空格符、制表符、换行符用 trim 函数删除，而后外面就只剩下数字 +-. 和 e 了，如果外面还有空格符的话那也不合乎数值的题目要求了，就能够间接 return false

退出移动版