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

目录
  • LeetCode 1805.字符串中不同整数的数目
  • 方法一：遍历拆分
  • AC代码
    • C++

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++ 字符串不同整数数目的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C++ LeetCode1775通过最少操作次数使数组和相等

    目录 LeetCode1775.通过最少操作次数使数组的和相等 方法一:贪心 + 计数 AC代码 C++ LeetCode1775.通过最少操作次数使数组的和相等 力扣题目链接:leetcode.cn/problems/eq… 给你两个长度可能不等的整数数组 nums1 和 nums2 .两个数组中的所有值都在 1 到 6 之间(包含 1 和 6). 每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 1 到 6 之间 任意 的值(包含 1 和 6). 请你返回使 nums1 中所有数

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1812判断国际象棋棋盘格子颜色

    目录 1812.判断国际象棋棋盘中一个格子的颜色 方法一:取模 AC代码 C++ 方法二:基于方法一的小改进 AC代码 C++ 1812.判断国际象棋棋盘中一个格子的颜色 力扣题目链接:leetcode.cn/problems/de… 给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标.下图是国际象棋棋盘示意图. 如果所给格子的颜色是白色,请你返回 true,如果是黑色,请返回 false . 给定坐标一定代表国际象棋棋盘上一个存在的格子.坐标第一个字符是字

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • C++ LeetCode1780判断数字是否可以表示成三的幂的和

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

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

    目录 LeetCode 1805.字符串中不同整数的数目 方法一:遍历拆分 AC代码 C++ LeetCode 1805.字符串中不同整数的数目 力扣题目链接:leetcode.cn/problems/nu… 给你一个字符串 word ,该字符串由数字和小写英文字母组成. 请你用空格替换每个不是数字的字符.例如,"a123bc34d8ef34" 将会变成 " 123  34 8  34" .注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123&q

  • JavaScript将字符串转换为整数的方法

    本文实例讲述了JavaScript将字符串转换为整数的方法.分享给大家供大家参考.具体如下: var s='1'; var s2='2'; alert(parseInt(s) parseInt(s2)); 希望本文所述对大家的javascript程序设计有所帮助.

  • java中字符串转整数及MyAtoi方法的实现

    java中字符串转整数及MyAtoi方法的实现

    java中字符串转整数及MyAtoi方法的实现 该题虽然和我们正常使用的字符串转整数的API中函数不一致,但是通过增加了很多额外的边界或者异常处理,可以锻炼算法思维的敏锐性和处理边界异常等问题的能力. 思路:字符串题一般考查的都是边界条件.特殊情况的处理.所以遇到此题一定要问清楚各种条件下的输入输出应该是什么样的. 这里已知的特殊情况有: 能够排除首部的空格,从第一个非空字符开始计算 允许数字以正负号(+-)开头 遇到非法字符便停止转换,返回当前已经转换的值,如果开头就是非法字符则返回0 在转换

  • php中字符串和整数比较的操作方法

    今天在处理php中循环的时候,有个比比较的操作,但是结果一直不是自己预判的,于是跟踪了一下,发现了字符串和整数进行比较的时候,会把字符串转换成整数然后进行比较.这个在java,c这种强类型的语言中不会有问题,因为他们会对字符串进行转换然后比较,但是在php这种弱类型中,可以直接比较的时候,就会有问题. $a = "梦回故里"; if($a==0){ echo "等于"; }else{ echo "不等于"; } 比如下面这段代码,一开始以为会输出

  • python 字符串和整数的转换方法

    数字转成字符串 方法一: 使用格式化字符串: tt=322 tem='%d' %tt tem即为tt转换成的字符串 常用的格式化字符串: %d 整数 %f%F 浮点数 %e%E 科学计数 %g%G e 和%f/%E 和%F 的简写 %% 输出% 格式化操作符辅助指令 符号 作用 * 定义宽度或者小数点精度 - 用做左对齐 + 在正数前面显示加号( + ) <sp> 在正数前面显示空格 # 在八进制数前面显示零('0'),在十六进制前面显示'0x'或者'0X'(取决于用的是'x'还是'X') 0

  • Python字符串、整数、和浮点型数相互转换实例

    前言序锦 在编程中,经常要用到字符串的相互转换,现在在这里记录一下Python里面的字符串和整数以及浮点型数之间是如何进行相互转换的. int(str)函数将符合整数的规定的字符串转换成int型的 float(str)函数将符合浮点型的规定的字符串转换成float型的 str(num)将整数.浮点型转换成字符串型的 int(str)函数将符合整数的规定的字符串转换成int型的 num2 = "123"; num2 = int(num1); print("num2: %d&qu

  • C++实现LeetCode(8.字符串转为整数)

    [LeetCode] 8. String to Integer (atoi) 字符串转为整数 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this ch

  • 每天练一练Java函数与算法Math函数总结与字符串转换整数

    题目 请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数). 函数 myAtoi(string s) 的算法如下: 读入字符串并丢弃无用的前导空格 . 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有). 确定最终结果是负数还是正数.如果两者都不存在,则假定结果为正. 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾.字符串的其余部分将被忽略. 将前面步骤读入的这些数字转换为整数

  • 在C++中把字符串转换为整数的两种简单方法

    目录 C++中的数据类型 如何在C++中声明和初始化 int s 如何在C++中声明和初始化 string s 如何使用 stoi() 函数将字符串转换为int 如何使用stringstream 类将一个字符串转换为一个int 总结 当你用C++编码时,经常会有这样的时候,你会想把一种数据类型转换为另一种. 在这篇文章中,你将看到两种最流行的方法来学习如何在C++中把字符串转换为整数. 让我们开始吧! C++中的数据类型 C++编程语言有一些内置的数据类型. int,用于整数(整数)(例如10,

  • C++实现字符串和整数的相互转换

    目录 字符串转换整数 方法1 方法2(推荐) 整数转换字符串 字符串转换整数 方法1 #include <iostream> #include <typeinfo> using namespace std; int main() { string s = "Kinght_123"; cout << typeid(s).name() << '\n'; cout << typeid(atoi(s.c_str())).name();

随机推荐