剑指offer(C++)-JZ67:把字符串转换成整数atoi(算法-模拟)
作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:
写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
1.若干空格
2.(可选)一个符号字符('+' 或 '-')
3. 数字,字母,符号,空格组成的字符串表达式
4. 若干空格
转换算法如下:
1.去掉无用的前导空格
2.第一个非空字符为+或者-号时,作为该整数的正负号,如果没有符号,默认为正数
3.判断整数的有效部分:
3.1 确定符号位之后,与之后面尽可能多的连续数字组合起来成为有效整数数字,如果没有有效的整数部分,那么直接返回0
3.2 将字符串前面的整数部分取出,后面可能会存在存在多余的字符(字母,符号,空格等),这些字符可以被忽略,它们对于函数不应该造成影响
3.3 整数超过 32 位有符号整数范围 [−231, 231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231的整数应该被调整为 −231 ,大于 231 − 1 的整数应该被调整为 231 − 1
4.去掉无用的后导空格
数据范围:
1.0 <=字符串长度<= 100
2.字符串由英文字母(大写和小写)、数字(0-9)、' '、'+'、'-' 和 '.' 组成
示例:
输入:
"4396 clearlove"
返回值:
4396
说明:
6后面的字符不属于有效的整数部分,去除,但是返回前面提取的有效部分
解题思路:
本题考察算法场景模拟。两种解题思路。
1)遍历法
首先过滤前置空格;再判断正负号;之后判断连续数字,过程中注意正负极限判断;每找到一个新数字,就把之前的数字*10再累加上去,遍历完即可得到答案。复杂度O(n)。
2)状态机
基于状态转移矩阵对字符串遍历过程的状态进行分析。
状态分为4种,空格、符号、数字和无效,对应0123,根据题目条件设立矩阵如下:
- 起始状态为0,分析第一行:如果碰到空格,那下一个状态还是0;如果碰到符号,则状态转为1;如果碰到数字,则状态转为2;如果碰到无效字符,状态转为3。
- 假设状态转为1,分析第二行:如果碰到空格,即+空格,则无效,因此第二行第一列为3;如果又碰到符号,例如+-,也无效,所以第二行第二列为3;如果碰到数字,例如-3,则状态转为2;碰到无效字符状态转为3。
- 假设状态转为2,分析第三行:如果碰到空格,例如+8空格或者8空格,后续均无效,因此第三行第一列为3;如果碰到符号,例如+8+或者8+,后续也是均无效,因此第三行第二列为3;如果碰到数字,例如+89或者89,则后续是有效的,因此第三行第三列为2;无效字符同理无效。
- 当状态为2时,对数字进行累加和越界判断;当状态为3时,break退出即可。
总的来说,状态机就是基于题目要求,将可能发生的情形和状态的转变,以矩阵形式表示,进而解题。复杂度O(n)。
测试代码:
1)遍历法
#include <climits>
class Solution {
public:// 字符串转为整数int StrToInt(string s) {int sign = 1;int idx = 0;int size = int(s.size());// 前空格过滤,过滤完如果没有后续则退出while(idx < size){if(s[idx] == ' ')idx++;elsebreak;}if(idx == size)return 0;// 判断符号,如果没有后续则退出if(s[idx] == '+')idx++;else if(s[idx] == '-'){idx++;sign = -1;}if(idx == size)return 0;// 继续遍历寻找目标数字int result = 0;while(idx < size){// 遇到非数字退出if(s[idx] < '0' || s[idx] > '9')break;// 判断极限if(result > INT_MAX / 10 || (result == INT_MAX / 10 && (s[idx] - '0') >= (INT_MAX % 10)))return INT_MAX;if(result < INT_MIN / 10 || (result == INT_MIN / 10 && (s[idx] - '0') >= -(INT_MIN % 10)))return INT_MIN;// 字符转为数字result = result * 10 + sign * (s[idx] - '0');idx++;}return result;}
};
2)状态机
class Solution {
public:// 字符串转为整数int StrToInt(string s) {// 状态转移矩阵vector<vector<int>> states = {{0,1,2,3},{3,3,2,3},{3,3,2,3},}; // 定义long result = 0;long top = INT_MAX; long bottom = INT_MIN;int sign = 1;int size = int(s.length());// 状态从0开始int state = 0; for(int i = 0; i < size; ++i){// 空格if(s[i] == ' '){state = states[state][0]; }// 正负号 else if(s[i] == '-' || s[i] == '+'){ state = states[state][1]; if(state == 1){sign = (s[i] == '-') ? -1 : 1;} }// 数字else if(s[i] >= '0' && s[i] <= '9'){state = states[state][2]; } // 非法字符else{state = states[state][3]; }// 状态为2时,表明在连续数字状态,进行数字累加if(state == 2){// 数字相加result = result * 10 + s[i] - '0'; // 越界处理result = (sign == 1) ? min(result, top) : min(result, -bottom); }// 状态为3时,说明后续无效,退出即可else if(state == 3)break;}return (int)sign * result;}
};
相关文章:
剑指offer(C++)-JZ67:把字符串转换成整数atoi(算法-模拟)
作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。…...
嵌入式笔试面试刷题(day15)
文章目录 前言一、Linux中的主设备号和次设备号1.查看方法2.主设备号和次设备号的作用 二、软件IIC和硬件IIC的区别三、变量的声明和定义区别四、static在C和C中的区别五、串口总线空闲时候的电平状态总结 前言 本篇文章继续讲解嵌入式笔试面试刷题,希望大家坚持跟…...
【Docker】Dockerfile构建镜像
一、编写Dockerfile文件 编写镜像需要的运行环境(Linux、java等), Dockerfile文件内容如下: # 使用官方的 Ubuntu 16.04 镜像作为基础镜像 FROM ubuntu:16.04# 更新包列表 RUN apt-get update# 安装所需的软件包 RUN apt-get ins…...
fota升级,可卸载apk也进行更新
首先如题目要求 可卸载apk是通过刷机或恢复出厂设置之后执行脚本安装的 然后fota升级后,在判断是否“是第一次刷机和恢复出厂设置”时候会返回false,就导致脚本没有执行。导致apk升级不成功 所以我们要完成这个就是,确定fota什么时候升级完…...
ASP.NET dotnet 3.5 实验室信息管理系统LIMS源码
技术架构:ASP.NET dotnet 3.5 LIMS作为一个信息管理系统,它有着和ERP、MIS之类管理软件的共性,如它是通过现代管理模式与计算机管理信息系统支持企业或单位合理、系统地管理经营与生产,最大限度地发挥现有设备、资源、人、技术的…...
2023!6招玩转 Appium 自动化测试
Appium是个什么鬼 Appium是一个移动端的自动化框架,可用于测试原生应用,移动网页应用和混合型应用,且是跨平台的。可用于IOS和Android以及firefox的操作系统。原生的应用是指用android或ios的sdk编写的应用,移动网页应用是指网页…...
WireShark抓包分析TCP三次握手过程,TCP报文解析
「作者主页」:士别三日wyx 「作者简介」:CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」:对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 使用WireShark工具抓取TCP协议三次握手的数据包&am…...
【C语言】指针和数组笔试题解析
大家好,我是苏貝,本篇博客带大家了解指针和数组笔试题解析,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 1.前言2.一维数组2.字符数组2.12.22.32.42.52.6 1.前言 本篇文章是讲述在不同数…...
Vue的模板语法(下)
一.事件处理 事件修饰符 Vue通过由点(.)表示的指令后缀来调用修饰符, .stop, .prevent,.capture,.self,.once .stop:阻止事件冒泡。当一个元素触发了事件,并且该元素包含嵌套的父元素时&#…...
Zookeeper客户端——I0Itec-zkClient
dubbo使用了zkClient而不是使用zookeeper本身的客户端与zookeeper进行交互,为什么呢? 先看看zookeeper本身自带的客户端的问题。 1)ZooKeeper的Watcher是一次性的,用过了需要再注册; 2) session的超时后…...
火山引擎 ByteHouse:ClickHouse 如何保证海量数据一致性
背景 ClickHouse是一个开源的OLAP引擎,不仅被全球开发者广泛使用,在字节各个应用场景中也可以看到它的身影。基于高性能、分布式特点,ClickHouse可以满足大规模数据的分析和查询需求,因此字节研发团队以开源ClickHouse为基础&…...
hashmap使用
hashmap作为dao对象存储数据库数据 list是把每一个数据库的字段都映射了,而hashmap则是唯一id:数据库字段作为key hashmap遍历方式 public class Main {//使用迭代器(Iterator)EntrySetpublic static void main(String[] args) {// 创建并赋…...
Centos7配置国内yum源
目录 备份原系统中的repo文件配置国内开源镜像重新生成yum缓存 备份原系统中的repo文件 cd /etc/yum.repos.d/mkdir repo_bakmv *.repo repo_bak/配置国内开源镜像 到网易和阿里开源镜像站点下载系统对应版本的repo文件 curl -O http://mirrors.aliyun.com/repo/Centos-7.re…...
C#中async/await的线程ID变化情况
一、简单的起步 Console.WriteLine($"主线程开始ID:{Thread.CurrentThread.ManagedThreadId}");//aawait Task.Delay(100);//cConsole.WriteLine($"主线程结束ID:{Environment.CurrentManagedThreadId}");//b 结果: …...
网络安全—黑客技术—自学笔记
目录梗概 一、自学网络安全学习的误区和陷阱 二、学习网络安全的一些前期准备 三、网络安全学习路线 四、学习资料的推荐 想自学网络安全(黑客技术)首先你得了解什么是网络安全!什么是黑客! 网络安全可以基于攻击和防御视角来…...
功夫再高也怕菜刀。多年经验,会独立开发的机器视觉工程师,技术太强,但是找工作能力差劲
功夫再高也怕菜刀,专业的事情交给专业的人去做。 今年7月份中旬的时候,遇到一位老朋友,向我咨询某公司的信息,其实我根本不了解这家公司的情况与实力,向他说了,抱歉,我查下,等我晚上…...
numpy的多项式函数: `poly1d`
Python numpy.poly1d() numpy.poly1d()函数有助于定义一个多项式函数。它使得在多项式上应用 "自然操作 "变得容易。 语法: numpy.poly1d (arr, root, var) 参数 : arr : [array_like] 多项式系数按照幂的递减顺序给出。如果第二个参数(根)被…...
Python灰帽编程——错误异常处理和面向对象
文章目录 1. 错误和异常1.1 基本概念1.1.1 Python 异常 1.2 检测(捕获)异常1.2.1 try except 语句1.2.2 捕获多种异常1.2.3 捕获所有异常 1.3 处理异常1.4 特殊场景1.4.1 with 语句 2. 内网主机存活检测程序2.1 scapy 模块2.1.1 主要功能2.1.2 scapy 安装…...
【20230919】win11无法删除Chrome注册表项
win11无法删除Chrome注册表项 删除以下注册表项发生错误: 计算机\HKEY_LOCAL_MACHINE\SOFTWAR\Google计算机\HKEY_CURRENT_USER\Software\Google 尝试了很多删除注册表方法(例如:编辑remove.reg文件),都不行。 无法…...
TCP/IP客户端和服务器端建立通信过程
客户端和服务器端建立通信过程 使用Qt提供的类进行基于TCP的套接字通信需要用到两个类: QTcpServer:服务器类,用于监听客户端连接以及和客户端建立连接。 QTcpSocket:通信的套接字类,客户端、服务器端都需要使用。服务…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
