Question: You are asked to implement a myAtoi(string s) function that converts a string to a 32-bit signed integer.
01The manual processing of each character method
The simplest method is always the first method that comes to mind, and it is also the most violent method, and in this case we just need to install the topic requirements one character at a time to deal with it, in fact, the whole solution is quite simple.
Let's sort out the solution, which can be roughly divided into the following three steps:
(1) Handle the opening space, remove all the spaces at the beginning by while loop;
(2) Handle positive and negative symbols, determine if they contain the +/- sign, and mark them down;
(3) Processing digits, first determine whether the current character is a numerical value, if so calculate its value and detect whether it overflows, in the case of non-overflow, accumulate the results by x*10+digit;
(4) Finally, the correct result is returned based on the plus or minus sign.
The specific code is as follows:
//Solution 1: Manually process each character (classic solution)
public static int MyAtoi1(string s)
{
//result
var result = 0;
//current processing character index
var index = 0; //mark positive and negative numbers
//Tagging positive and negative numbers
var sign = 1; //String length
//Length of the string
var length = ;
//remove the first space
while (index < length && s[index] == ' ')
{
//process the next character
index++;
}
// Handle positive and negative symbols
if (index < length && (s[index] == '+' || s[index] == '-'))
{
//Sign the positive and negative numbers
sign = s[index] == '-' ? -1 : 1;
// Handle the next character
index++; //handle the next character
}
// Convert numeric characters to numbers
while (index < length && (s[index]))
{
//Calculate the current character value
var digit = s[index] - '0'; //check for overflow.
//Check for overflow
if (result > ( - digit) / 10)
{
return sign == 1 ? : ;
}
//Accumulate the current character into the result
result = result * 10 + digit; // process the next character
// Process the next character
index++; }
}
//return result
return sign * result; }
}
02Regular Expression Method
There is a more concise way, you can directly through the regular expression to match the characters to meet the conditions, and then through the type conversion, the reason why I chose the BigInteger type is because all other types of values can lead to overflow situations.
Based on the solution of the previous question, let's try to realize it with regular expressions step by step.
The first thing you need to do is match the opening blank character.
^: Indicates an anchor point that matches the beginning of the string;
\s: Indicates special characters, matches blank characters, including spaces, tabs, line breaks, etc;
*: denotes a quantifier, indicating that its preceding element can occur zero or more times;
Space handling at the beginning of a string can therefore be implemented by means of ^\s*.
[]: Define a character class that represents a match for any of the characters in square brackets;
+-: Indicates plus and minus signs, i.e., positive and negative symbols;
? : denotes a quantifier, indicating that its preceding element may occur zero or one time;
Therefore it is possible to match positive and negative signs by [+-]? to achieve matching of plus and minus signs.
\d: Indicates that it matches a numeric character, ranging from 0-9;
+: denotes a quantifier, indicating that its preceding element may occur one or more times;
Therefore, consecutive numeric character matching can be achieved by \d+.
Take a look at the implementation code below:
//Solution 2: Regular Expression Method
public static int MyAtoi2(string s)
{
//Use regular expression to match the part that meets the requirements
//^\s*: means match zero or more blank characters (spaces, tabs, etc.) at the beginning of the string.
//[+-]? : Indicates that the symbol (+ or -) is optional.
//\d+: indicates one or more numbers.
var match = (s, @"^\s*[+-]? \d+");
// Match is successful and can be converted to a numeric value
if ( && (, out var result))
{
// greater than int max
if (result > )
{
return ;
}
//less than int minimum
if (result < )
{
return ;
}
//return result
return (int)result; }
}
return 0; }
}
03state machine method
There is another classic solution to this problem, the state machine method, where the core idea of a state machine is to trigger transfers between states in a finite set of states and through inputs.
Let's take this as an example, assuming that in the process of processing strings, there has always been a state state, and each processing of the current character can be triggered when the state state to transfer to the next state state1, so we just need to enumerate all the state and the current character on the state1 mapping relationship can be.
We can build the state machine shown below:
As shown above, if the current state is "start", and the current character is "space", then state1 is "start", if the current character is If the current character is "number", then state1 is "handle number", and so on, and state1 will be absolutely specific processing method of the current character.
We can also represent this state machine in the following table:
With the state machine state relationship mapping table, we can carry out the code implementation, the logic is also very simple, roughly divided into the following four steps:
(1) Construct a state machine state table;
(2) Get the state corresponding to the current character;
(3) Determine the current character processing logic by state transfer;
(4) Iterate over the string to be processed to get the final result;
The specific implementation code is as follows:
//solution (a math problem) 3：state machine method
public int MyAtoi3(string s)
{
Automaton automaton = new Automaton();
return (s);
}
public class Automaton
{
//0:"commencement"state of affairs
private const int Start = 0;
//1:"symbol"state of affairs
private const int Signed = 1;
//2:"digital processing"state of affairs
private const int InNumber = 2;
//3:"close"state of affairs
private const int End = 3;
//notation:1positive number，0negative number
private int _sign = 1;
//Numerical results
private long _answer = 0;
//记录当前处理state of affairs
private int _state = Start;
//state of affairs表
private readonly Dictionary<int, int[]> _table = new Dictionary<int, int[]>()
{
{Start,new int[]{ Start, Signed, InNumber, End}},
{Signed,new int[]{ End, End, InNumber, End}},
{InNumber,new int[]{ End, End, InNumber, End}},
{End,new int[]{ End, End, End, End}},
};
//Processing the current character
private void Handle(char c)
{
//获取当前state of affairs
var currentState = GetState(c);
//转移state of affairs
_state = _table[_state][currentState];
switch (_state)
{
//digital processing
case InNumber:
_answer = _answer * 10 + c - '0';
//overflow judgment
_answer = _sign == 1 ? (_answer, ) : (_answer, -(long));
break;
//handle both positive and negative signs (math.)
case Signed:
_sign = c == '+' ? 1 : -1;
break;
case Start:
case End:
break;
}
}
//获取当前字符对应state of affairs
private static int GetState(char c)
{
//blank space
if ((c))
{
return Start;
}
//plus or minus sign ± (math.)
if (c == '+' || c == '-')
{
return Signed;
}
//numeric
if ((c))
{
return InNumber;
}
//(sth. or sb) else
return End;
}
//String to integer conversion
public int Atoi(string s)
{
var length = ;
for (int i = 0; i < length; ++i)
{
Handle(s[i]);
}
return (int)(_sign * _answer);
}
}
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner