C++ LeetCode1805字符串不同整数数目

   2023-02-09 学习力0
核心提示:目录LeetCode 1805.字符串中不同整数的数目方法一:遍历拆分AC代码C++LeetCode 1805.字符串中不同整数的数目力扣题目链接:leetcode.cn/problems/nu…给你一个字符串 word ,该字符串由数字和小写英文字母组成。请你用空格替换每个不是数字的字符。例如,"a12

LeetCode 1805.字符串中不同整数的数目

力扣题目链接:leetcode.cn/problems/nu…

给你一个字符串 word ,该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如,"a123bc34d8ef34" 将会变成 " 123  34 8  34" 。注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123""34""8""34"

返回对 word 完成替换后形成的 不同 整数的数目。

只有当两个整数的 不含前导零 的十进制表示不同, 才认为这两个整数也不同。

示例 1:

输入:word = "a123bc34d8ef34"
输出:3
解释:不同的整数有 "123"、"34" 和 "8" 。注意,"34" 只计数一次。

示例 2:

输入:word = "leet1234code234"
输出:2

示例 3:

输入:word = "a1b01c001"
输出:1
解释:"1"、"01" 和 "001" 视为同一个整数的十进制表示,因为在比较十进制值时会忽略前导零的存在。

提示:

  • 1 <= word.length <= 1000
  • word 由数字和小写英文字母组成

方法一:遍历拆分

这个问题主要包括三部分:

  • 将数字从字符串中抽取出来
  • 将数字的前导零去除
  • 数字的去重与计数

接下来逐个解决这三个问题

1. 将数字从字符串中提取出来:

我们需要一个布尔类型的变量“lastIsNum”来记录上一个字符是否为数字。初始值为false

同时,我们还需要一个字符串,用来存储整个字符串中的某个数字。string thisString

接下来遍历字符串。若字符串遍历结束或者遍历到字母字符时,将lastIsNum标记为true,否则将lastIsNum标记为false

如果这个字符是字母,但上一个字符是数字,那么就说明我们找到了“一个数字的末尾”,此时我们就提取出了这个数字。

处理完这个数字记得将字符串清空。

如果这个字符是数字,那么直接无脑添加数字字符串thisString的末尾即可。

2. 将数字的前导零去除:

使用一个整数类型的变量firstLoc来记录一个数字第一个非零的位置,初始值为-1

接着遍历数字字符串,遇到第一个非零数字就结束遍历,并将firstLoc修改为遍历到的位置。

如果最后firstLoc的值仍未-1,那么就说明整个数字字符串全是0

否则,从firstLoc开始到字符串末尾所组成的子串即为去除前导零后的数字字符串

3. 数字的去重与统计:

题目问的是“有多少不同的数字”,这就需要我们对所有的数字做去重处理。

这个过程很简单,直接使用一个哈希表即可

将所有的处理过的数字字符串放入哈希表,最后返回哈希表的大小即为去重后的结果。

  • 时间复杂度O(len(word))
  • 空间复杂度O(len(word))

AC代码

C++

class Solution {
private:
    unordered_set<string> se;

    void insert(string toInsert) {
        int firstLoc = -1;
        for (int i = 0; i < toInsert.size(); i++) {
            if (toInsert[i] != '0') {
                firstLoc = i;
                break;
            }
        }
        if (firstLoc == -1)
            se.insert("0");
        else
            se.insert(toInsert.substr(firstLoc));
    }
public:
    int numDifferentIntegers(string word) {
        bool lastIsNum = false;
        string thisString;
        int n = word.size();
        for (int i = 0; i <= n; i++) {
            if (i == n || isalpha(word[i])) {
                if (lastIsNum) {
                    lastIsNum = false;
                    insert(thisString);
                    thisString.clear();
                }
            }
            else {
                thisString += word[i];
                lastIsNum = true;
            }
        }
        return se.size();
    }
};

以上就是C++ LeetCode1805字符串不同整数数目的详细内容,更多关于C++ 字符串不同整数数目的资料请关注其它相关文章!

原文地址:https://juejin.cn/post/7173881123536109582
 
反对 0举报 0 评论 0
 

免责声明:本文仅代表作者个人观点,与乐学笔记(本网)无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
    本网站有部分内容均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责,若因作品内容、知识产权、版权和其他问题,请及时提供相关证明等材料并与我们留言联系,本网站将在规定时间内给予删除等相关处理.

  • Aurelius vs mORMot vs EntityDAC Delphi 的
    Aurelius vs mORMot vs EntityDAC   Delphi 的 ORM框架:http://www.tmssoftware.com/site/aurelius.asp#product-buy-onlinehttps://synopse.info/fossil/wiki/Synopse+OpenSourcehttps://www.devart.com/entitydac/download.htmlkbmMW  http://www.compo
    02-09
  • 【Ruby】Mac gem的一些坑
    前言自上一次升级MacOS系统后出现jekyll无法构建的问题,当时处理半天。谁知道最近又升级了MacOS,荒废博客多时,今天吝啬写了一篇准备发布,构建报错,问题重新。还是记录下,以防下次升级出问题。问题描述安装jekyll静态博客需要在Ruby环境下运行,于是参照
    02-09
  • iOS oc 调用 swift
    如股票oc要调用swift里面的代码 需要包含固定这个头文件项目名称 LiqunSwiftDemo-Swift.h         #ProjectName#-Swift.h固定的写法swift 目的 是取代oc 但是 不会完全取代 只是前端的替换LiqunSwiftDemo-Swift 点进去 可以看到 所有的swift代码 都产生
    02-09
  • objective-c NSTimer 定时器
    -(void)initTimer{//时间间隔NSTimeInterval timeInterval =3.0 ;//定时器repeats 表示是否需要重复,NO为只重复一次NSTimer *timer = [NSTimer scheduledTimerWithTimeInterval:timeInterval target:self selector:@selector(mobileAnimation) userInfo:nil
    02-09
  • Objective-C  日记③ 字符串
    Objective-C 日记③ 字符串
    一、创建字符串、类方法   公式创建NSString  +(id) stringWithFormat:(NSString *) format,……;eg:  NSString *height;  height=[NSString stringWithFormat:@"高度是: %d 长度: %d",10,20];得到的字符串:“高度是: 10 长度: 20” 注意:  省
    02-09
  • Objective-C KVC机制
    Objective-C KVC机制http://blog.csdn.net/omegayy/article/details/7381301全部推翻重写一个版本,这是我在公司内做技术分享的文档总结,对结构、条理做了更清晰的调整。 1.    基本概念MODEL主要是英文文档里面经常出现的一些概念,讲解一下,方便英文
    02-09
  • objective-c 加号 减号 - +
    “加号代表static”是错误的说法,可能跟你那样表达的人其实意思是:“前置加号的方法相当于Java 里面的静态方法”。在Oc中,方法分为类方法和实例方法。前置加号(+)的方法为类方法,这类方法是可以直接用类名来调用的,它的作用主要是创建一个实例。有人把
    02-09
  • Objective-C  日记①
    Objective-C 日记①
    1、Xcode的.m扩展名表示文件含有Object-C代码,C以.c文件,C++以.cpp文件2、头文件声明:C使用:#include,O-C使用#import(当然你也可以使用#include) 3、输出方式:  C:printf("",参数);  O-C:NSLog(@"",参数); 4、布尔类型  C:bool 具有true
    02-09
  • ASP.NET MVC 操作AD 获取域服务器当前用户姓
    #region 根据当前登录域账号 获取AD用户姓名和所在OU目录/// summary/// 根据当前登录域账号 获取AD用户姓名和所在OU目录/// /summary/// param name="searchUser"要搜索的当前用户名/param/// param name="paths"out返回该用户所在OU目录/param/// param nam
    02-09
  • swift和OC - 拆分数组 和 拆分字符串
    1. 拆分数组 /// 根据 数组 截取 指定个数返回 多个数组的集合func splitArray( array: [Date], withSubSize subSize: Int) - [[Date]] {//数组将被拆分成指定长度数组的个数let count = array.count% subSize == 0 ? (array.count/ subSize) : (array.count
    02-08
点击排行