This is the 23rd day of my participation in the genwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

134. String conversion integer (atoi) (string-to-integer-atoi)

The label

  • string
  • automata
  • medium

The title

Leetcode portal

Let’s just open leetCode.

MyAtoi (string s) converts a string to a 32-bit signed integer (similar to atoi in C/C++).

MyAtoi (string s)

  • Read in the string and discard useless leading whitespace
  • Checks whether the next character (assuming it has not reached the end of the character) is a plus or minus sign and reads that character (if any). Determine whether the final result is negative or positive. If neither exists, the result is assumed to be positive.
  • Read the next character until the next non-numeric character is reached or the end of the input is reached. The rest of the string is ignored.
  • Convert the numbers read in the previous steps to integers (that is, “123” -> 123, “0032” -> 32).If no number is read in, the integer is 0. Change symbols as necessary (starting with Step 2).
  • If the number of integers exceeds the 32 – bit signed integer range[- 2 ^ 31, 2 ^ 31-1), you need toTruncate the integer to keep it in range. Specifically, less than- 2 ^ 31The integers should befixedfor- 2 ^ 31, is more than2^31 − 1The integer of should be fixed to2^31 − 1 。

Note:

  • Whitespace characters in this case include only the space character ‘ ‘.
  • Do not omit any characters other than those following a leading space or number

Example 1:

Input: s = "42" Output: 42 Description: Caret is the character currently read. Step 1: "42" (currently not read because there is no leading space) ^ Step 2: "42" (currently not read because there is no '-' or '+') ^ Step 3: "42" (read "42") ^ parses to the integer 42. Since "42" is in the range [-231, 231-1], the final result is 42.Copy the code

Example 2:

Input: s = "-42" Output: -42 Explanation: Step 1:" -42" (read leading space, but ignore it) ^ Step 2: "-42" (read '-' character, so result should be negative) ^ Step 3: "-42" (reading "42") ^ parses to the integer -42. Since "-42" is in the range [-231, 231-1], the final result is -42.Copy the code

Example 3:

Input: s = "4193 with words" Output: 4193 "4193 with words" (currently not read because there is no '-' or '+') ^ step 3: "4193 with words" (read "4193"; Since the next character is not a number, the reading is stopped) ^ parses to the integer 4193. Since "4193" is in the range [-231, 231-1], the final result is 4193.Copy the code

Example 4:

Input: s = "words and 987" Output: 0 Explanation: step 1: "Words and 987" (currently not read because there is no leading space) ^ Step 2: "Words and 987" (currently not read because there is no '-' or '+') ^ Step 3:" Words and 987" (reading stopped because the current character 'w' is not a number) ^ parse to the integer 0 because no number was read. Since 0 is in the range [-231, 231-1], the final result is 0.Copy the code

Example 5:

Input: s = "-91283472332" Output: -2147483648 Explanation: Step 1: "-91283472332" (currently no character is read because there is no leading space) ^ Step 2: "-91283472332" (reads the '-' character, so the result should be negative) ^ Step 3: "-91283472332" (reads "91283472332") ^ parses to the integer -91283472332. Since -91283472332 is less than the lower bound of the range [-231, 231-1], the final result is truncated to -231 = -2147483648.Copy the code

The basic idea

See this kind of topic, do not panic, but feel happy, the general long topic, explain the limitation is much, but will be simple, as long as do according to the meaning of the topic, mainly is the text understanding to be accurate, still have to add careful.

There are some easy ways to do this, but what we’re going to do in this video is talk about automata, and the easy way to do it is to just read the notes.

Determine finite state automata

The automata here generally refers to deterministic finite state automata

First understand what automata are used for:

Automata is a mathematical model for determining signal sequences.

  • A “signal sequence” is a sequence of sequential signals, such as each character from front to back in a string, each digit from 1 to n in an array, each digit from highest to lowest, etc.
  • “determine“Is a pointer that gives a true or false answer to a proposition. Sometimes we need to decide on a sequence of signals.
    • A simple example is to determine whether a binary number is odd or even, and more complex examples are to determine whether a string is palindromic, whether a string is a subsequence of a particular string, and so on.

It is important to note that an automaton is a mathematical model, not an algorithm, nor a data structure. There are many ways to implement the same automaton, which may have different temporal and spatial complexity.

In short, it has the following three characteristics

  • The total number of states is finite.
  • In one state at any one time.
  • Under certain conditions, they transition from one state to another.

A deterministic finite state automata (DFA) consists of the following five parts:

  • Character set (sigma), the automaton can only input these characters.
  • Set of states (Q). If a DFA is regarded as a directed graph, the states in the DFA are equivalent to the vertices on the graph.
  • Initial state(start),Start ∈ Q 是aSpecial state.
  • Set of accepted states(F),F ⊆ Q, it isA set ofSpecial state.
  • Transfer function (δ), δ is a function that takes two arguments and returns a value, where the first argument and the return value are both a state, and the second argument is a character in the character set. If a DFA is viewed as a directed graph, the transfer function in the DFA is equivalent to the edges between vertices, and each edge has a character.

In this case, we consider that:

  1. We input the state machine character by character.
  • How do we define the set of states
  1. How the input character causes the state machine to transition (how the transition function is written)
  • Does it have to do with what character to type
  • It has to do with the original state

So, how do we draw this picture? So if you take a piece of paper and follow my lead first of all we have an initial state start, which is nothing

start
Copy the code
  • If we come in with an empty string “”, then we’re not doing anything, and we’re still starting, which means we’re starting fromstart --(' ')--> start
The input' 'Is equal to no change or start state _(' ')___
    |        |
    |        |
    --start <-
Copy the code
  • If there’s a number, it’s going to be a number right now, and that number is the first digit,Start --(number)--> in_number status
  • If there’s a special character or a letter or something, it looks like it’s just finished, and it prints 0, which isendstatestart ---(other)-->end
  • If it’s a sign(+ / -)Because it is nowstartThe first one is the sign bit ok, go insignedState,Start --(+, -)--> signed state

We found that there was no other route, so we decided on these four states, and here is the transition from the start state

...... (digital) _____ > [in_number] | | (' ') [start] - (+ / -) -- - > "signed" | | - -- -- -- -- -- -- -- -- -- (other special/letter) - > 【 end 】 【 】 in said state, () indicates the input character, and -> indicates the status after the transferCopy the code

You can then want to transfer the arrow from the in_number state input, from the signed state, etc., and finally draw the following diagram.

And then you can also use tables

If you look at the table like this, the left column represents the current state, the table header represents the input parameter, and the bar where the columns and columns meet represents the state after the transition. It’s very clear.

The code implementation looks at the very clear comments below.

Writing implement

ParseInt method

Using the parseInt API notice that the second argument is base

var myAtoi = function (str) {
    const res = parseInt(str, 10);
    const MAX_VALUE = 2六四屠杀31 - 1    
    const MIN_VALUE = -(2六四屠杀31)
    
    // NAN cannot be converted
    if (isNaN(res)) {
        return 0;
    }

    // Out of range, truncate
    if (res < MIN_VALUE || res > MAX_VALUE) {
        return res < 0 ? MIN_VALUE : MAX_VALUE;
    }
    return res;
};
console.log(myAtoi('123'))
console.log(myAtoi('123ss'))
console.log(myAtoi('ss123'))
Copy the code

The regular method

Use regular expression to match the string required by the question, and then turn to integer.

var myAtoi = function (str) {
    // Regex matches at least one digit starting with +/-
    let reg = new RegExp(/ ^ [\ + \]? \d+/);
    // Remove whitespace trim()
    let res = str.trim().match(reg);
    if (res) {
        / / plastic
        if (res[0] *1 < 0) {
            return Math.max(res[0] *1, -2六四屠杀31))}else {
            return Math.min(res[0] *1.2六四屠杀31 - 1)}}else {
        return 0}}console.log(myAtoi('123'))
console.log(myAtoi('123ss'))
console.log(myAtoi('ss123'))
Copy the code

automata

class Automaton{
  constructor() {
    // Execution phase, which is in the start execution phase by default
    this.state = 'start';
    // symbol, the default is positive
    this.sign = 1;
    // A numeric variable is used for intermediate accumulative use
    this.res = 0;
    // 
    this.autoMap = new Map([['start'['start'.'signed'.'in_number'.'end']],
      ['signed'['end'.'end'.'in_number'.'end']],
      ['in_number'['end'.'end'.'in_number'.'end']],
      ['end'['end'.'end'.'end'.'end']]])}getIndex(char) {
    // Get autoMap's index based on char
    if (char === ' ') {
      return 0;
    } else if (char === The '-' || char === '+') {
      return 1;
    } else if (typeof Number(char) === 'number'&&!isNaN(char)) {
      return 2;
    } else {
      return 3; }}// character conversion executes the function
  transform(char) {
    // this.automap. get(this.state) retrieves the current state
    // Converts to the next state based on the incoming char and overrides the current state
    this.state = this.autoMap.get(this.state)[this.getIndex(char)];

    if(this.state === 'in_number') {
      
      // char is used as the ones bit
      this.res = this.res * 10 + char * 1;

      // Also do border truncation
      if (this.sign === 1) {
        this.res = Math.min(this.res, 2六四屠杀31 - 1)}else {
        // Note the - sign
        this.res = - Math.max(-this.res, -(2六四屠杀31))}}else if (this.state === 'signed') {
      this.sign = char === '+' ? 1 : -1; }}}var myAtoi = function(str) {
  
  // Generate an instance of the automata
  let automaton = new Automaton();

  // Input a sequence of characters into the automaton for state conversion
  for(let char of str) {
    automaton.transform(char);
  }
  // The automaton outputs the final state
  return automaton.sign * automaton.res;
};

console.log(myAtoi('123'))
console.log(myAtoi('123ss'))
console.log(myAtoi('ss123'))
console.log(myAtoi("91283472332"))
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference

  • Oi-wiki.org/string/auto…
  • Github.com/jakesgordon…