每日一刷《剑指offer》字符串篇之把字符串转换成整数(atoi)
今日题目链接:把字符串转换成整数(atoi)
把字符串转换成整数(atoi)
难度：中等
描述
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
- 若干空格
- （可选）一个符号字符（'+' 或 '-'）
- 数字，字母，符号，空格组成的字符串表达式
- 若干空格
转换算法如下:
1.去掉无用的前导空格
2.第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数
3.判断整数的有效部分：
3.1 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0
3.2 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响
3.3 整数超过 32 位有符号整数范围 [−2****31 , 2****31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231的整数应该被调整为 −2****31 ，大于 2****31 − 1 的整数应该被调整为 2****31 − 1
4.去掉无用的后导空格
举例
解题思路
方法一：遍历法;既然是将字符串转化为数字，那我们可以遍历字符串，一个字符串，一个字符地检查，然后取出掉无用的，取出数字，利用如下代码，一个数字一个数字地转换，前面的扩大十倍加上后面一位。 res = res * ``10 + sign * (c - ``'0'``);
- step 1：遍历字符串，用index记录全程的下标。
- step 2：首先要排除空串，然后越过前导空格，以及前导空格后什么都没有就返回0.
- step 3：然后检查符号，没有符号默认为正数。
- step 4：再在后续遍历的时候，将数字字符转换成字符，遇到非数字则结束转换。
- step 5：与Int型最大最小值比较，检查越界情况。
方法二：状态机;字符串无非就是这些类型：[ ' '（空格）, 0（前导或者数字中间的）, 1-9, 其它非法字符，'-/+' ]，我们可以将其映射成数字： 0,1,2,3,4，一共有4种状态 0，1，2，3， 其中3退出状态机且返回当前保存的结果。
//状态转移矩阵
int[][] states = {
{0,1,2,3,1},
{3,1,2,3,3},
{3,2,2,3,3}}; - step 1：利用常数矩阵保存状态机。
- step 2：遍历字符串，根据当前的字符类型，进入相应的状态。
- step 3：数字状态要进行转换，并判断是否超过int型上下界。
实现代码（java）
方法一：
import java.util.*;
public class Solution {
public int StrToInt (String s) {
//空串
if(s.isEmpty())
return 0;
int res = 0;
int index = 0;
int n = s.length();
//去掉前导空格，如果有
while(index < n){
if(s.charAt(index) == ' ')
index++;
else
break;
}
//去掉空格就什么都没有了
if(index == n)
return 0;
int sign = 1;
//处理第一个符号是正负号的情况
if(s.charAt(index) == '+')
index++;
else if(s.charAt(index) == '-'){
index++;
sign = -1;
}
//去掉符号就什么都没有了
if(index == n)
return 0;
while(index < n){
char c = s.charAt(index);
//后续非法字符，截断
if(c < '0' || c > '9')
break;
//处理越界
if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (c - '0') > Integer.MAX_VALUE % 10))
return Integer.MAX_VALUE;
if(res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (c - '0') > -(Integer.MIN_VALUE % 10)))
return Integer.MIN_VALUE;
res = res * 10 + sign * (c - '0');
index++;
}
return res;
}
}方法二：
import java.util.*;
public class Solution {
public int StrToInt (String s) {
//状态转移矩阵
int[][] states = {
{0,1,2,3,1},
{3,1,2,3,3},
{3,2,2,3,3},
};
long res = 0;
//与int边界比较
long top = Integer.MAX_VALUE;
long bottom = Integer.MIN_VALUE;
int n = s.length();
int sign = 1;
//状态从“ ”开始
int state = 0;
for(int i = 0; i < n; i++){
char c = s.charAt(i);
if(c == ' ')
//空格
state = states[state][0];
else if(c == '0')
//前导0或者中间的0
state = states[state][1];
else if(c >= '1' && c <= '9')
//数字
state = states[state][2];
else if(c == '-' || c == '+'){
//正负号
state = states[state][4];
if(state == 1)
sign = (c == '-') ? -1 : 1;
else
break;
}else
//非法字符
state = states[state][3];
if(state == 2){
//数字相加
res = res * 10 + (c - '0');
//越界处理
res = (sign == 1) ? Math.min(res, top) : Math.min(res, -bottom);
}
if(state == 3)
break;
}
return (int)(sign * res);
}
}学习完本题的思路你可以解决如下题目：
表示数值的字符串
难度：中等
描述
请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。
科学计数法的数字(按顺序）可以分成以下几个部分:
1.若干空格
2.一个整数或者小数
3.（可选）一个 'e' 或 'E' ，后面跟着一个整数(可正可负)
4.若干空格
小数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（'+' 或 '-'）
3.可能是以下描述格式之一:
3.1 至少一位数字，后面跟着一个点 '.'
3.2 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
3.3 一个点 '.' ，后面跟着至少一位数字
4.若干空格
整数（按顺序）可以分成以下几个部分：
- 若干空格
- （可选）一个符号字符（'+' 或 '-')
- 至少一位数字
- 若干空格
例如，字符串"+100","5e2","-123","3.1416","-1E-16"都表示数值。
但是"12e","1a3.14","1.2.3","+-5","12e+4.3"都不是数值。
举例
解题思路
方法一：
- 定义3个布尔类型的标识位，分别表示之前是否遇到过数字、小数点、‘e’或'E'
- 对转为字符数组的 arr 进行每个字符的遍历，并判断以下几种情况：
- 1、当前字符是否为 **0~9**
- 2、如果是小数点，则小数点之前不能重复出现**小数点**、或出现‘e’、'E'
- 3、如果当前字符位 **‘e’ 或 ‘E’**，‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
- 4、**正负号**只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置如果满足以上四种情况，则最后根据最后字符是否为数字，返回 true 或 false实现代码（java）
import java.util.*;
public class Solution {
// 例子：str = -123.45e+6
public boolean isNumeric (String str) {
if(str == null || str.length() == 0) {
return false;
}
// 标记之前是否遇到过数字、小数点、‘e’或'E'
boolean isNum = false, isDot = false, isE = false;
// 删除字符串头尾的空格，转为字符数组
char[] arr = str.trim().toCharArray();
for(int i = 0; i < arr.length; i++) {
// 判断当前字符是否为 0~9
if(arr[i] >= '0' && arr[i] <= '9') {
isNum = true;
} else if(arr[i] == '.') {
// 小数点之前不能重复出现小数点、或出现‘e’、'E'
if(isDot || isE) {
return false;
}
// 标记已经遇到小数点
isDot = true;
} else if(arr[i] == 'e' || arr[i] == 'E') { // 遇到‘e’或'E'
// ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
if(!isNum || isE) {
return false;
}
// 标记已经遇到‘e’或'E'
isE = true;
// 重置isNum，因为‘e’或'E'之后必须接上整数，因为最后返回isNum，因此需要重置
isNum = false;
} else if(arr[i] == '-' || arr[i] == '+') {
// 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
if(i != 0 && arr[i-1] != 'e' && arr[i-1] != 'E') {
return false;
}
} else {
// 其它情况均为不合法字符
return false;
}
}
// 最后一位必须是数字
return isNum;
}
}学习完本题的思路你可以解决如下题目：
字典树的实现
难度：中等
描述
字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。
假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。
- void insert(String word)：添加word，可重复添加；
- void delete(String word)：删除word，如果word添加过多次，仅删除一次；
- boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
- int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。
现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。
对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。
举例
解题思路
方法一：TrieNode实现； 首先构建一个TrieNode结构，包括一个TrieNode类型的child数组，用于记录所有子节点，一个整型变量pre_number，用于表示插入单词时，当前节点被访问次数，一个boolean型变量end，用于标记当前节点是否是某个单词的结尾。
然后初始化一个根节点，根节点是空心的，即不包含任何字符。
- 添加word：将单词转为字符数组，从根节点出发，遍历输入的单词，如果子节点不包含当前字符，则新建对应子节点，如果包含，则跳到对应子节点，同时访问次数加一。单词遍历完成后，当前节点标识改为true。
- 删除word：相当于添加的反向操作，不断往子节点方向移动，同时访问次数减一。遍历完成后，如果访问次数为0，则将标识改为false。
- 查询word：将单词转为字符数组，从根节点出发，遍历输入的单词，如果子节点不包含当前字符，说明不存在该单词，返回false，如果包含，就往子节点方向移动。遍历完成后，标识为true，说明存在该单词。
- 查询以pre为前缀的单词数量：将单词转为字符数组，从根节点出发，遍历输入的单词，如果子节点不包含当前字符，说明不存在该前缀，返回0，如果包含，就往子节点方向移动。遍历完成后，pre_number的值即为所求的前缀数量（因为如果某个单词以pre为前缀，插入节点的时候，必然访问过pre结尾处节点）。
实现代码（java）
import java.util.*;
public class Solution {
/**
*
* @param operators string字符串二维数组 the ops
* @return string字符串一维数组
*/
public String[] trieU (String[][] operators) {
//计算结果集长度，并进行初始化
int len=0;
for(String[] opera:operators){
if(opera[0].equals("3")||opera[0].equals("4")){
len++;
}
}
String[] res=new String[len];
Trie trie=new Trie();
int id=0;
for(String[] opera:operators){
if(opera[0].equals("1")){
//添加单词
trie.insert(opera[1]);
}
else if(opera[0].equals("2")){
//删除单词
trie.delete(opera[1]);
}
else if(opera[0].equals("3")){
//查询单词是否存在
res[id++]=trie.search(opera[1])?"YES":"NO";
}
else if(opera[0].equals("4")){
//查找以word为前缀的单词数量
String preNumber=String.valueOf(trie.prefixNumber(opera[1]));
res[id++]=preNumber;
}
}
return res;
}
class Trie{
//构建字典树节点
class TrieNode{
//child数组记录所有子节点
TrieNode[] child;
//pre_number表示插入单词时，当前节点被访问次数
int pre_number;
//end表示当前节点是否是某个单词的末尾
boolean end;
TrieNode(){
child=new TrieNode[26];
pre_number=0;
end=false;
}
}
Trie(){}
//初始化根节点
TrieNode root=new TrieNode();
//添加单词
void insert(String word){
TrieNode node=root;
char[] arr=word.toCharArray();
for(char c:arr){
//如果子节点不存在，则新建
if(node.child[c-'a']==null){
node.child[c-'a']=new TrieNode();
}
//往子节点方向移动
node=node.child[c-'a'];
node.pre_number++;
}
node.end=true;
}
void delete(String word){
TrieNode node=root;
char[] arr=word.toCharArray();
for(char c:arr){
//往子节点方向移动，将访问次数减一
node=node.child[c-'a'];
node.pre_number--;
}
//如果访问次数为0，说明不存在该单词为前缀的单词，以及该单词
if(node.pre_number==0){
node.end=false;
}
}
boolean search(String word){
TrieNode node=root;
char[] arr=word.toCharArray();
for(char c:arr){
//如果子节点不存在，说明不存在该单词
if(node.child[c-'a']==null){
return false;
}
node=node.child[c-'a'];
}
//如果前面的节点都存在，并且该节点末尾标识为true，则存在该单词
return node.end;
}
int prefixNumber(String pre){
TrieNode node=root;
char[] arr=pre.toCharArray();
for(char c:arr){
//如果子节点不存在，说明不存在该前缀
if(node.child[c-'a']==null){
return 0;
}
node=node.child[c-'a'];
}
//返回以该单词为前缀的数量
return node.pre_number;
}
}
}我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
腾讯云开发者
