Leetcode -65- a significant number
[Blog link]
A path to learning at ๐
The nuggets home page
[B].
Significant digits (in order) can be divided into the following parts: a decimal or integer (optional) an 'e' or 'e' followed by an integer Decimal (in order) can be divided into the following parts: (Optional) a signed character ('+' or '-') one of the following formats: At least one digit followed by a dot '.' at least one digit followed by a dot '.' At least one digit Integers (in order) can be divided into the following parts: (Optional) One sign character ('+' or '-') with at least one digit part valid digits are listed as follows: [" 2 ", "0089", "0.1", "+ 3.14", "4", "- 9", "2 e10", "- 90 e3", "3 e + 7", "+ 6 e - 1", "53.5 e93", "123.456 e789]" invalid part Numbers listed below: [" ABC ", "1 a", "1 e", "e3", "99 e2. 5", "- 6", "- + 3", "95 a54e53"] to give you a string s, if s is a valid number, please return true. Example 1: Input: s = "0" Output: true Example 2: Input: s = "e" output: false Example 3: Input: s = "." Output: false Example 4: Input: s = ".1" Output: true Hint: 1 <= s.length <= 20 s contains only letters (uppercase and lowercase), digits (0-9), plus '+', minus '-', or the dot '.'. Related Topics Math string ๐ 212 ๐ 0Copy the code
[็ญ ๆก]
Leetcode topic link
[making address]
Code link
[introduction]
Idea 1: Multi-condition matching
- There are too many validation conditions if you debug step by step
- Given a few test cases here, the T/F classification should cover most scenarios
True: String [] s = new String [] {46. E3 ""," 2 ", "0089", "0.1", "+ 3.14", "4", "- 9", "2 e10", "- 90 e3", "3 e + 7", "+ 6 e - 1", "53.5 e93", "123.456 e789", "- 1"}; False: String s = new String [] [] {", "+ E3" e1 ", "ABC", "1 a", "E3", "99 e2. 5", "- 6", "- + 3", "95 a54e53", "6 e +", "e1", "+"};Copy the code
public boolean isNumber(String s) {
char[] chars = s.toCharArray();
boolean sf = false;
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
// If it is not e/ e,+/-,., the number can return false directly
if(! checkAll(c)) {return false;
}
// Digits starting with e must be followed by a signed integer
if (checkE(c)) {
if (i == 0 || checkS(chars[i - 1]) {return false;
}
// Check if it is a signed integer
return checkInt(s.substring(i + 1));
}
// Check if there is a signed number
if (checkS(c)) {
if (i == chars.length - 1) {
return false;
}
if (i == 0 || checkE(chars[i - 1]) || checkP(chars[i - 1]) {continue;
} else {
return false; }}// Check whether integer bits are included
if (checkN(c)) {
continue;
}
// Determine if there are decimal places
if (checkP(c)) {
// The decimal point is in the first place
if (i == 0 || checkS(chars[i - 1]) {// The following position requires e or an integer containing e
return checkEInteger(s.substring(i + 1));
} else {
if (checkN(chars[i - 1]) {return i == s.length() - 1 || checkPInteger(s.substring(i + 1)); }}}}return true;
}
public boolean checkAll(char c) {
return checkE(c) || checkS(c) || checkN(c) || checkP(c);
}
public boolean checkN(char c) {
return c >= '0' && c <= '9';
}
public boolean checkE(char c) {
return c == 'e' || c == 'E';
}
public boolean checkS(char c) {
return c == '+' || c == The '-';
}
public boolean checkP(char c) {
return c == '. ';
}
public boolean checkInt(String s) {
if ("".equals(s)) {
return false;
}
char[] c = s.toCharArray();
for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
if(! checkN(c[i])) {return false; }; }return checkN(c[s.length() - 1]);
}
public boolean checkPInteger(String s) {
if ("".equals(s)) {
return false;
}
char[] c = s.toCharArray();
if (checkS(c[0]) {return false;
}
for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
if(! checkN(c[i])) {if (checkE(c[i])) {
return checkInt(s.substring(i + 1));
} else {
return false; }}}return true;
}
public boolean checkEInteger(String s) {
if ("".equals(s)) {
return false;
}
char[] c = s.toCharArray();
if (checkE(c[0]) || checkS(c[0]) {return false;
}
for (int i = checkS(c[0])?1 : 0; i < s.length(); i++) {
if(! checkN(c[i])) {if (checkE(c[i])) {
return checkInt(s.substring(i + 1));
} else {
return false; }}}return true;
}
Copy the code
Time complexity O(n)
Idea 2:Water palace antithesis
Time complexity O(n)
Idea 3: Automata
- This is the subject I flunked in college. I hate to think about it
- Interested can view the official solution
Time complexity O(n)