当前位置:网站首页>LeetCode 8. String conversion integer (ATOI)
LeetCode 8. String conversion integer (ATOI)
2022-07-06 00:09:00 【Daylight629】
8. String conversion integers (atoi)
Please come to realize a myAtoi(string s)
function , Enable it to convert a string to a 32 Bit signed integer ( similar C/C++ Medium atoi
function ).
function myAtoi(string s)
The algorithm is as follows :
- Read in strings and discard useless leading spaces
- Check the next character ( Suppose you haven't reached the end of the character yet ) Positive or negative , Read the character ( If there is ). Determine whether the final result is negative or positive . If neither exists , Suppose the result is positive .
- Read in the next character , Until you reach the next non numeric character or the end of the input . The rest of the string will be ignored .
- Convert the numbers read in the previous steps into integers ( namely ,“123” -> 123, “0032” -> 32). If you don't read in the numbers , Then the integer is
0
. Change the symbol if necessary ( From step 2 Start ). - If the number of integers exceeds 32 Bit signed integer range
[−231, 231 − 1]
, You need to truncate this integer , Keep it in this range . say concretely , Less than−231
The integer of should be fixed to−231
, Greater than231 − 1
The integer of should be fixed to231 − 1
. - Returns an integer as the final result .
Be careful :
- The white space character in this question only includes the space character
' '
. - Except for the leading space or the rest of the string after the number , Do not ignore Any other character .
Example 1:
Input :s = "42"
Output :42
explain : The bold string is the character that has been read in , The caret is the character currently read .
The first 1 Step :"42"( No characters are currently read in , Because there are no leading spaces )
^
The first 2 Step :"42"( No characters are currently read in , Because it doesn't exist here '-' perhaps '+')
^
The first 3 Step :"42"( Read in "42")
^
Parse to get an integer 42 .
because "42" In scope [-231, 231 - 1] Inside , The final result is 42 .
Example 2:
Input :s = " -42"
Output :-42
explain :
The first 1 Step :" -42"( Read in leading space , But ignore )
^
The first 2 Step :" -42"( Read in '-' character , So the result should be negative )
^
The first 3 Step :" -42"( Read in "42")
^
Parse to get an integer -42 .
because "-42" In scope [-231, 231 - 1] Inside , The final result is -42 .
Example 3:
Input :s = "4193 with words"
Output :4193
explain :
The first 1 Step :"4193 with words"( No characters are currently read in , Because there are no leading spaces )
^
The first 2 Step :"4193 with words"( No characters are currently read in , Because it doesn't exist here '-' perhaps '+')
^
The first 3 Step :"4193 with words"( Read in "4193"; Because the next character is not a number , So read in stop )
^
Parse to get an integer 4193 .
because "4193" In scope [-231, 231 - 1] Inside , The final result is 4193 .
Example 4:
Input :s = "words and 987"
Output :0
explain :
The first 1 Step :"words and 987"( No characters are currently read in , Because there are no leading spaces )
^
The first 2 Step :"words and 987"( No characters are currently read in , Because it doesn't exist here '-' perhaps '+')
^
The first 3 Step :"words and 987"( Because of the current character 'w' It's not a number , So read in stop )
^
Parse to get an integer 0 , Because I didn't read in any numbers .
because 0 In scope [-231, 231 - 1] Inside , The final result is 0 .
Example 5:
Input :s = "-91283472332"
Output :-2147483648
explain :
The first 1 Step :"-91283472332"( No characters are currently read in , Because there are no leading spaces )
^
The first 2 Step :"-91283472332"( Read in '-' character , So the result should be negative )
^
The first 3 Step :"-91283472332"( Read in "91283472332")
^
Parse to get an integer -91283472332 .
because -91283472332 Less than range [-231, 231 - 1] Lower bound of , The final result is truncated to -231 = -2147483648 .
Tips :
0 <= s.length <= 200
s
By the English letters ( Uppercase and lowercase )、 Numbers (0-9
)、' '
、'+'
、'-'
and'.'
form
Two 、 Method 1
automata
class Solution {
public int myAtoi(String str) {
Automaton automaton = new Automaton();
int length = str.length();
for (int i = 0; i < length; ++i) {
automaton.get(str.charAt(i));
}
return (int) (automaton.sign * automaton.ans);
}
}
class Automaton {
public int sign = 1;
public long ans = 0;
private String state = "start";
private Map<String, String[]> table = new HashMap<String, String[]>() {
{
put("start", new String[]{
"start", "signed", "in_number", "end"});
put("signed", new String[]{
"end", "end", "in_number", "end"});
put("in_number", new String[]{
"end", "end", "in_number", "end"});
put("end", new String[]{
"end", "end", "end", "end"});
}};
public void get(char c) {
state = table.get(state)[get_col(c)];
if ("in_number".equals(state)) {
ans = ans * 10 + c - '0';
ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
} else if ("signed".equals(state)) {
sign = c == '+' ? 1 : -1;
}
}
private int get_col(char c) {
if (c == ' ') {
return 0;
}
if (c == '+' || c == '-') {
return 1;
}
if (Character.isDigit(c)) {
return 2;
}
return 3;
}
}
Complexity analysis
Time complexity :O(n), among n Is the length of the string . We just need to process all the characters in turn , The time required to process each character is O(1).
Spatial complexity :O(1). The state of automata only needs constant space to store .
边栏推荐
- Effet Doppler (déplacement de fréquence Doppler)
- Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
- 【二叉搜索树】增删改查功能代码实现
- 第16章 OAuth2AuthorizationRequestRedirectWebFilter源码解析
- 7.5 decorator
- Detailed explanation of APP functions of door-to-door appointment service
- mysql-全局锁和表锁
- What are Yunna's fixed asset management systems?
- DEJA_VU3D - Cesium功能集 之 055-国内外各厂商地图服务地址汇总说明
- Determinant learning notes (I)
猜你喜欢
Key structure of ffmpeg - avframe
Laser slam learning record
How to rotate the synchronized / refreshed icon (EL icon refresh)
【在线聊天】原来微信小程序也能回复Facebook主页消息!
Mysql - CRUD
Problem solving win10 quickly open ipynb file
【DesignMode】装饰者模式(Decorator pattern)
多普勒效应(多普勒频移)
Hardware and interface learning summary
亲测可用fiddler手机抓包配置代理后没有网络
随机推荐
My colleagues quietly told me that flying Book notification can still play like this
教你在HbuilderX上使用模拟器运行uni-app,良心教学!!!
What are the functions of Yunna fixed assets management system?
China Jinmao online electronic signature, accelerating the digitization of real estate business
Tools to improve work efficiency: the idea of SQL batch generation tools
Use CAS instead of synchronized
Detailed explanation of APP functions of door-to-door appointment service
硬件及接口学习总结
用列表初始化你的vector&&initializer_list简介
After summarizing more than 800 kubectl aliases, I'm no longer afraid that I can't remember commands!
转:未来,这样的组织才能扛住风险
There is no network after configuring the agent by capturing packets with Fiddler mobile phones
QT QPushButton details
从底层结构开始学习FPGA----FIFO IP核及其关键参数介绍
7.5 decorator
【DesignMode】适配器模式(adapter pattern)
Gd32f4xx UIP protocol stack migration record
mysql-全局锁和表锁
单商户V4.4,初心未变,实力依旧!
Problem solving win10 quickly open ipynb file