This is the 17th day of my participation in Gwen Challenge

Topic describes

This is the significant number 65 on LeetCode. Difficulty is difficult.

Tag: “Simulation”

Significant numbers (in order) can be broken down into the following parts:

  1. A decimal or whole number
  2. (Optional) an ‘e’ or ‘e’ followed by an integer

Decimals (in order) can be divided into the following parts:

  1. (Optional) a symbolic character (‘+’ or ‘-‘)
  2. One of the following formats:
    1. At least one digit followed by a dot ‘.’
    2. At least one digit, followed by a dot ‘.’, followed by at least one digit
    3. A dot ‘.’ followed by at least one digit

Integers (in order) can be divided into the following parts:

  1. (Optional) a symbolic character (‘+’ or ‘-‘)
  2. At least one digit

Some significant figures are listed below:

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

Some invalid numbers are listed below:

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

Given the string s, return true if s is a valid number.

Example 1:

Input: s = 0 Output: trueCopy the code

Example 2:

Input: s = "e" Output: falseCopy the code

Example 3:

Input: s = "." Output: falseCopy the code

Example 4:

Input: s = ".1" Output: trueCopy the code

Tip:

  • 1 <= s.length <= 20
  • S contains only uppercase and lowercase letters, digits (0-9), plus ‘+’, minus ‘-‘, or the dot ‘.’.

simulation

String large simulation, according to the “significant number definition” comb rules.

There are many solutions to this problem: “regular”, “DFA”, “simulation”…

“Simulation” is the easiest way to implement it in all kinds of scenarios, as long as the brain is not hot to write.

When dividing a string by e/ e, the rule is quite simple:

  • If there ise/E: The left side can be integer or floating point, and the right side must be integer
  • If it doesn’t existe/E: The whole segment can be “integer” or “floating point”

The key is how to implement a check function to determine “integer” or “floating point” :

  • +/-Only in the head
  • .At most once
  • At least one number exists

Code:

class Solution {
    public boolean isNumber(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int idx = -1;
        for (int i = 0; i < n; i++) {
            if (cs[i] == 'e' || cs[i] == 'E') {
                if (idx == -1) idx = i;
                else return false; }}boolean ans = true;
        if(idx ! = -1) {
            ans &= check(cs, 0, idx - 1.false);
            ans &= check(cs, idx + 1, n - 1.true);
        } else {
            ans &= check(cs, 0, n - 1.false);
        }
        return ans;
    }
    boolean check(char[] cs, int start, int end, boolean mustInteger) {
        if (start > end) return false;
        if (cs[start] == '+' || cs[start] == The '-') start++;
        boolean hasDot = false, hasNum = false;
        for (int i = start; i <= end; i++) {
            if (cs[i] == '. ') {
                if (mustInteger || hasDot) return false;
                hasDot = true;
            } else if (cs[i] >= '0' && cs[i] <= '9') {
                hasNum = true;
            } else {
                return false; }}returnhasNum; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: WilltoCharArrayReplace withcharAt 为
    O ( 1 ) O(1)     , or for
    O ( n ) O(n)

The last

This is the 65th article in our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions in LeetCode, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.