題目描述(困難難度)
給定一個字元串,判斷它是否代表合法數字,當然題目描述的樣例不夠多,會使得設計算法中出現很多遺漏的地方,這裡直接參考評論區@yeelan0319給出的更多測試樣例。
test(1, "123", true);
test(2, " 123 ", true);
test(3, "0", true);
test(4, "0123", true); //Cannot agree
test(5, "00", true); //Cannot agree
test(6, "-10", true);
test(7, "-0", true);
test(8, "123.5", true);
test(9, "123.000000", true);
test(10, "-500.777", true);
test(11, "0.0000001", true);
test(12, "0.00000", true);
test(13, "0.", true); //Cannot be more disagree!!!
test(14, "00.5", true); //Strongly cannot agree
test(15, "123e1", true);
test(16, "1.23e10", true);
test(17, "0.5e-10", true);
test(18, "1.0e4.5", false);
test(19, "0.5e04", true);
test(20, "12 3", false);
test(21, "1a3", false);
test(22, "", false);
test(23, " ", false);
test(24, null, false);
test(25, ".1", true); //Ok, if you say so
test(26, ".", false);
test(27, "2e0", true); //Really?!
test(28, " .8", true);
test(29, " 005047e 6", true); //Damn = =|||
解法一 直接法
什麼叫直接法呢,就是沒有什麼通用的方法,直接分析題目,然後寫代碼,直接貼兩個 leetcode Disscuss 的代碼吧,供參考。
想法一。
把目前的輸入分成幾類,再用幾個标志位來判斷目前是否合法。
public boolean isNumber(String s) {
s = s.trim();
boolean pointSeen = false;
boolean eSeen = false;
boolean numberSeen = false;
boolean numberAfterE = true;
for(int i=0; i<s.length(); i ) {
if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
numberSeen = true;
numberAfterE = true;
} else if(s.charAt(i) == '.') {
if(eSeen || pointSeen) {
return false;
}
pointSeen = true;
} else if(s.charAt(i) == 'e') {
if(eSeen || !numberSeen) {
return false;
}
numberAfterE = false;
eSeen = true;
} else if(s.charAt(i) == '-' || s.charAt(i) == ' ') {
if(i != 0 && s.charAt(i-1) != 'e') {
return false;
}
} else {
return false;
}
}
return numberSeen && numberAfterE;
}
時間複雜度:O(n)。
空間複雜度:O(1)。
想法二,周遊過程中,把遇到不符合的都傳回 false,到最後成功到達末尾就傳回 true。C 的代碼,可以參考一下思想。
bool isNumber(const char *s)
{
int i = 0;
// skip the whilespaces
for(; s[i] == ' '; i ) {}
// check the significand
if(s[i] == ' ' || s[i] == '-') i ; // skip the sign if exist
int n_nm, n_pt;
for(n_nm=0, n_pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i )
s[i] == '.' ? n_pt :n_nm ;
if(n_pt>1 || n_nm<1) // no more than one point, at least one digit
return false;
// check the exponent if exist
if(s[i] == 'e') {
i ;
if(s[i] == ' ' || s[i] == '-') i ; // skip the sign
int n_nm = 0;
for(; s[i]>='0' && s[i]<='9'; i , n_nm ) {}
if(n_nm<1)
return false;
}
// skip the trailing whitespaces
for(; s[i] == ' '; i ) {}
return s[i]==0; // must reach the ending 0 of the string
}
時間複雜度:O(n)。
空間複雜度:O(1)。
解法二 自動機
自己最開始想到的就是這個,編譯原理時候在學到的自動機,就是一些狀态轉移。這一塊内容很多,自己也很多東西都忘了,但不影響我們寫算法,主要參考這裡。
如上圖,從 0 開始總共有 9 個狀态,橙色代表可接受狀态,也就是表示此時是合法數字。總共有四大類輸入,數字,小數點,e 和 正負号。我們隻需要将這個圖實作就夠了。
public boolean isNumber(String s) {
int state = 0;
s = s.trim();//去除頭尾的空格
//周遊所有字元,當做輸入
for (int i = 0; i < s.length(); i ) {
switch (s.charAt(i)) {
//輸入正負号
case ' ':
case '-':
if (state == 0) {
state = 1;
} else if (state == 4) {
state = 6;
} else {
return false;
}
break;
//輸入數字
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
//根據目前狀态去跳轉
switch (state) {
case 0:
case 1:
case 2:
state = 2;
break;
case 3:
state = 3;
break;
case 4:
case 5:
case 6:
state = 5;
break;
case 7:
state = 8;
break;
case 8:
state = 8;
break;
default:
return false;
}
break;
//小數點
case '.':
switch (state) {
case 0:
case 1:
state = 7;
break;
case 2:
state = 3;
break;
default:
return false;
}
break;
//e
case 'e':
switch (state) {
case 2:
case 3:
case 8:
state = 4;
break;
default:
return false;
}
break;
default:
return false;
}
}
//橙色部分的狀态代表合法數字
return state == 2 || state == 3 || state == 5 || state == 8;
}
時間複雜度:O(n)。
空間複雜度:O(1)。
解法三 責任鍊模式
解法二看起來已經很清晰明了了,隻需要把狀态圖畫出來,然後實作代碼就很簡單了。但是缺點是,如果狀态圖少考慮了東西,再改起來就會很麻煩。
這裡作者提出來,利用責任鍊的設計模式,會使得寫出的算法擴充性以及維護性更高。這裡用到的思想就是,每個類隻判斷一種類型。比如判斷是否是正數的類,判斷是否是小數的類,判斷是否是科學計數法的類,這樣每個類隻關心自己的部分,出了問題很好排查,而且互不影響。
//每個類都實作這個接口
interface NumberValidate {
boolean validate(String s);
}
//定義一個抽象類,用來檢查一些基礎的操作,是否為空,去掉首尾空格,去掉 /-
//doValidate 交給子類自己去實作
abstract class NumberValidateTemplate implements NumberValidate{
public boolean validate(String s)
{
if (checkStringEmpty(s))
{
return false;
}
s = checkAndProcessHeader(s);
if (s.length() == 0)
{
return false;
}
return doValidate(s);
}
private boolean checkStringEmpty(String s)
{
if (s.equals(""))
{
return true;
}
return false;
}
private String checkAndProcessHeader(String value)
{
value = value.trim();
if (value.startsWith(" ") || value.startsWith("-"))
{
value = value.substring(1);
}
return value;
}
protected abstract boolean doValidate(String s);
}
//實作 doValidate 判斷是否是整數
class IntegerValidate extends NumberValidateTemplate{
protected boolean doValidate(String integer)
{
for (int i = 0; i < integer.length(); i )
{
if(Character.isDigit(integer.charAt(i)) == false)
{
return false;
}
}
return true;
}
}
//實作 doValidate 判斷是否是科學計數法
class SienceFormatValidate extends NumberValidateTemplate{
protected boolean doValidate(String s)
{
s = s.toLowerCase();
int pos = s.indexOf("e");
if (pos == -1)
{
return false;
}
if (s.length() == 1)
{
return false;
}
String first = s.substring(0, pos);
String second = s.substring(pos 1, s.length());
if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
{
return false;
}
return true;
}
private boolean validatePartBeforeE(String first)
{
if (first.equals("") == true)
{
return false;
}
if (checkHeadAndEndForSpace(first) == false)
{
return false;
}
NumberValidate integerValidate = new IntegerValidate();
NumberValidate floatValidate = new FloatValidate();
if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
{
return false;
}
return true;
}
private boolean checkHeadAndEndForSpace(String part)
{
if (part.startsWith(" ") ||
part.endsWith(" "))
{
return false;
}
return true;
}
private boolean validatePartAfterE(String second)
{
if (second.equals("") == true)
{
return false;
}
if (checkHeadAndEndForSpace(second) == false)
{
return false;
}
NumberValidate integerValidate = new IntegerValidate();
if (integerValidate.validate(second) == false)
{
return false;
}
return true;
}
}
//實作 doValidate 判斷是否是小數
class FloatValidate extends NumberValidateTemplate{
protected boolean doValidate(String floatVal)
{
int pos = floatVal.indexOf(".");
if (pos == -1)
{
return false;
}
if (floatVal.length() == 1)
{
return false;
}
NumberValidate nv = new IntegerValidate();
String first = floatVal.substring(0, pos);
String second = floatVal.substring(pos 1, floatVal.length());
if (checkFirstPart(first) == true && checkFirstPart(second) == true)
{
return true;
}
return false;
}
private boolean checkFirstPart(String first)
{
if (first.equals("") == false && checkPart(first) == false)
{
return false;
}
return true;
}
private boolean checkPart(String part)
{
if (Character.isDigit(part.charAt(0)) == false ||
Character.isDigit(part.charAt(part.length() - 1)) == false)
{
return false;
}
NumberValidate nv = new IntegerValidate();
if (nv.validate(part) == false)
{
return false;
}
return true;
}
}
//定義一個執行者,我們把之前實作的各個類加到一個數組裡,然後依次調用
class NumberValidator implements NumberValidate {
private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();
public NumberValidator()
{
addValidators();
}
private void addValidators()
{
NumberValidate nv = new IntegerValidate();
validators.add(nv);
nv = new FloatValidate();
validators.add(nv);
nv = new HexValidate();
validators.add(nv);
nv = new SienceFormatValidate();
validators.add(nv);
}
@Override
public boolean validate(String s)
{
for (NumberValidate nv : validators)
{
if (nv.validate(s) == true)
{
return true;
}
}
return false;
}
}
public boolean isNumber(String s) {
NumberValidate nv = new NumberValidator();
return nv.validate(s);
}
時間複雜度:
空間複雜度:
總
解法二中自動機的應用,會使得自己的思路更清晰。而解法三中,作者提出的對設計模式的應用,使自己眼前一亮,雖然代碼變多了,但是維護性,擴充性變的很強了。比如,題目新增了一種情況,“0x123” 16 進制也算是合法數字。這樣的話,解法一和解法二就沒什麼用了,完全得重新設計。但對于解法三,我們隻需要新增一個類,專門判斷這種情況,然後加到執行者的數組裡就夠了,很棒!
更多詳細通俗題解詳見 leetcode.wang 。