“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

In addition, when reading the source code, the lack of understanding of algorithms and data structures makes it difficult to understand why the author wrote the way he did.

In today’s environment, algorithms have become an indispensable skill for front-end engineers. If we want to move beyond being application engineers writing business code, we need to understand algorithms and data structures.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

65. Significant figures

Difficult difficult

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

  1. A decimal or whole number
  2. (Optional) One'e' 或 'E'“Followed by oneThe integer

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

  1. (Optional) A symbolic character ('+' 或 The '-')
  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 point'. ', followed by at least one digit

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

  1. (Optional) A symbolic character ('+' 或 The '-')
  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
  • sContains only English letters (uppercase and lowercase), digits (0-9), plus'+'A minus sign,The '-', or some'. ' 。

🌵

  • This problem can be solved by using the determinated finite state machine (DFA) in Principles of Compilation.
  • Switches to the next state based on the characters each state receives.

How to solve the problem 🐂

  • Use the data structure of the graph to represent the state. (JS can use objects to simulate diagrams)

  • Iterate through the string and follow the graph, returning false if there is no way out at some point.

  • When traversal is complete, return true if 3/5/6 is reached, false otherwise.

Source 🔥

/ * * *@param {string} s
 * @return {boolean}* /
var isNumber = function(s) {
    const graph={
        0: {'blank':0.'. ':2.'digit':6.'sign':1},
        1: {'digit':6.'. ':2},
        2: {'digit':3},
        3: {'digit':3.'e':4.'E':4},
        4: {'digit':5.'sign':7},
        5: {'digit':5},
        6: {'digit':6.'. ':3.'e':4.'E':4},
        7: {'digit':5}};let state=0;

    for(c of s.trim()){
      // Convert characters
        if(c >=0 && c<=9){
            c='digit'
        }else if(c===' '){
            c='blank'
        }else if(c==='+'||c===The '-'){
            c='sign';
        }
      // Switch state
        state=graph[state][c]
           if(state===undefined) {return false}}if(state===3||state===6||state===5) {return true
        }
    return false
  
};
Copy the code

Time complexity :O(n) (n is the length of the string)

Space complexity :O(1)

Conclusion 🌞

So the “LeetCode” 65- effective number ⚡️ of Yu Yu’s LeetCode algorithm is over. There is no shortcut to the algorithm, so we can only write and practice more and summarize more. The purpose of this article is actually very simple, which is to urge myself to complete the algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.

Add me on wechat: Sudongyuer, invite you into the group and learning the front together, become a better engineer ~ (group of qr code here – > front to go to bed early, qr code has expired, see the links to the boiling point in the comments, I will put the latest qr code in the comments section, of course, can also add me WeChat I pull you into the group, after all, I also am interesting front end, I also not bad 🌟 ~