剑指offer(C++)-JZ67:把字符串转换成整数atoi(算法-模拟)

简介: 剑指offer(C++)-JZ67:把字符串转换成整数atoi(算法-模拟)

题目描述:

写一个函数 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,根据题目条件设立矩阵如下:

  1. 起始状态为0,分析第一行:如果碰到空格,那下一个状态还是0;如果碰到符号,则状态转为1;如果碰到数字,则状态转为2;如果碰到无效字符,状态转为3。
  2. 假设状态转为1,分析第二行:如果碰到空格,即+空格,则无效,因此第二行第一列为3;如果又碰到符号,例如+-,也无效,所以第二行第二列为3;如果碰到数字,例如-3,则状态转为2;碰到无效字符状态转为3。
  3. 假设状态转为2,分析第三行:如果碰到空格,例如+8空格或者8空格,后续均无效,因此第三行第一列为3;如果碰到符号,例如+8+或者8+,后续也是均无效,因此第三行第二列为3;如果碰到数字,例如+89或者89,则后续是有效的,因此第三行第三列为2;无效字符同理无效。
  4. 当状态为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++;
            else
                break;
        }
        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;
    }
};


相关文章
|
13天前
|
存储 监控 算法
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
|
13天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
41 12
|
4天前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
12 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
21天前
|
消息中间件 Linux C++
c++ linux通过实现独立进程之间的通信和传递字符串 demo
的进程间通信机制,适用于父子进程之间的数据传输。希望本文能帮助您更好地理解和应用Linux管道,提升开发效率。 在实际开发中,除了管道,还可以根据具体需求选择消息队列、共享内存、套接字等其他进程间通信方
58 16
|
2月前
|
负载均衡 算法 安全
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
65 19
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
3月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
67 4
|
5月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
102 0