剑指 Offer 20. 表示数值的字符串 + 有限状态自动机
2024-08-31 11:24:46
剑指 Offer 20. 表示数值的字符串
Offer 20
常规解法：
- 题目解题思路：需要注意几种情况：
- 输入的字符串前后可能有任意多个空格，这是合法的。
- 正负号：
（1）正负号只能出现一次。
（2）正负号后面一个字符必须是数字或者小数点。
（3）字符串中最多有两个正负号（正常情况下最多只有一个，但是这里有指数E的情况，其前后可以加正负号）。 - e或者E:
(1) 指数符号最多出现一次。
(2) 前一个字符必须是数字或者小数点，如果是小数点，则小数点不能出现在第一个字符的位置。
(3) 后一个字符必须是数字或者正负号。
(4) 后面的所有字符中不能包含小数点，而前面可以包含小数点。 - 小数点：
(1) 小数点最多出现一次（不论是否是指数的形式）。
(2) 小数点如果出现在最后，则其前一个字符必须是数字符号。
(3) 小数点不能出现在E或e的后面。
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/1/26 17:59
*/
/**
* 题目描述：
* 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，
* 但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
*/
public class Offer_20 {
public boolean isNormal(String s){
int index = 0;
if(s == null || s.equals(""))
return false;
char start = s.charAt(0);
//数字的首字母必须是+，-，0-9其他的都不符合
if(start != '+' && start != '-' && start != '.' && (start < '0' || start > '9'))
return false;
if(start == '+' || start == '-' || start == '.'){
if(start == '+' || start == '-')
index = 1;
if(s.length() == 1)
return false;
if (s.charAt(1) != '.' && (s.charAt(1) < '0' || s.charAt(1) > '9'))
return false;
else if(s.charAt(1) == '.' && s.length() == 2)
return false;
// if(s.charAt(1) == '.' || s.charAt(1) == 'e')
// return false;
}
//只能有一个小数点，一个+,-符号
if(s.indexOf(".") != s.lastIndexOf(".")
|| s.indexOf("+") != s.lastIndexOf("+")
|| s.indexOf("-") != s.lastIndexOf("-"))
return false;
//不可以同时存在+,-号
if(s.contains("+") && s.contains("-"))
return false;
for(int i = index; i < s.length(); i++){
//除这些特殊字符外的字符都不合法
if (s.charAt(i) != '.' && (s.charAt(i) < '0' || s.charAt(i) > '9'))
return false;
}
//最多只有一个小数点
return s.indexOf(".") == s.lastIndexOf(".");
}
public boolean isNumber(String s) {
s = s.trim();
if(s.contains("e") || s.contains("E")){
int firstIndex, lastIndex;
if(s.contains("e")){
firstIndex = s.indexOf("e");
lastIndex = s.lastIndexOf("e");
}else{
firstIndex = s.indexOf("E");
lastIndex = s.lastIndexOf("E");
}
if(firstIndex != lastIndex)//存在多个e
return false;
else{
if(firstIndex == s.length() -1)//e在最后一个字符
return false;
String before = s.substring(0, firstIndex);//前半部分
String end = s.substring(firstIndex +1);//后半部分
if(!isNormal(before) || !isNormal(end))
return false;
//后半部分不能有小数点
if(end.contains("."))
return false;
}
}else{
if(!isNormal(s))
return false;
}
return true;
}
}
有限状态机：面试题20. 表示数值的字符串（有限状态自动机，清晰图解）
class Solution {
public boolean isNumber(String s) {
Map[] states = {
new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
new HashMap<>() {{ put('d', 2); put('.', 4); }}, // 1.
new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
new HashMap<>() {{ put('d', 3); }}, // 4.
new HashMap<>() {{ put('s', 6); put('d', 7); }}, // 5.
new HashMap<>() {{ put('d', 7); }}, // 6.
new HashMap<>() {{ put('d', 7); put(' ', 8); }}, // 7.
new HashMap<>() {{ put(' ', 8); }} // 8.
};
int p = 0;
char t;
for(char c : s.toCharArray()) {
if(c >= '0' && c <= '9') t = 'd';
else if(c == '+' || c == '-') t = 's';
else if(c == 'e' || c == 'E') t = 'e';
else if(c == '.' || c == ' ') t = c;
else t = '?';
if(!states[p].containsKey(t)) return false;
p = (int)states[p].get(t);
}
return p == 2 || p == 3 || p == 7 || p == 8;
}
}
最新文章
- php安装gearman扩展实现异步分步式任务
- How to build a GUI in ROS with Qt / C++
- 解决办法：在指定的 DSN 中，驱动程序和应用程序之间的体系结构不匹配 问题解决 SQLSTATE=IM014
- java StringBuffer与StringBuilder
- RTMP流媒体播放过程(转)
- C/C++中整数与浮点数在内存中的表示方式
- hdu 2503 a/b + c/d
- git 入门教程之分支总览
- Elasticsearch学习笔记（十二）filter与query
- ztree模糊筛选展开选中节点
- Python Day 11
- python的无限循环及退出
- Java访问级别修饰符
- dubbo请求报文实例
- python 内置方法expandtabs 把字符串格式化成列表输出
- HTTPS原理简述
- unity小地图制作___按比例尺图标布局
- apache的rewrite规则来实现URL末尾是否带斜杠
- 用正则表达式修改html字符串的所有div的style样式
- linux获得命令使用帮助