每日一刷《剑指offer》字符串篇之把字符串转换成整数(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; } } }
