快捷導(dǎo)航

C++ LeetCode1805字符串不同整數(shù)數(shù)目

更新時(shí)間：2022年12月16日 14:35:34 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode1805字符串不同整數(shù)數(shù)目，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

LeetCode 1805.字符串中不同整數(shù)的數(shù)目

給你一個(gè)字符串 word ，該字符串由數(shù)字和小寫英文字母組成。

請你用空格替換每個(gè)不是數(shù)字的字符。例如，"a123bc34d8ef34" 將會(huì)變成 " 123 34 8 34" 。注意，剩下的這些整數(shù)為（相鄰彼此至少有一個(gè)空格隔開）："123"、"34"、"8" 和 "34" 。

返回對(duì) word 完成替換后形成的不同整數(shù)的數(shù)目。

只有當(dāng)兩個(gè)整數(shù)的 不含前導(dǎo)零 的十進(jìn)制表示不同，才認(rèn)為這兩個(gè)整數(shù)也不同。

示例 1：

輸入：word = "a123bc34d8ef34"
輸出：3
解釋：不同的整數(shù)有 "123"、"34" 和 "8" 。注意，"34" 只計(jì)數(shù)一次。

示例 2：

輸入：word = "leet1234code234"
輸出：2

示例 3：

輸入：word = "a1b01c001"
輸出：1
解釋："1"、"01" 和 "001" 視為同一個(gè)整數(shù)的十進(jìn)制表示，因?yàn)樵诒容^十進(jìn)制值時(shí)會(huì)忽略前導(dǎo)零的存在。

提示：

1 <= word.length <= 1000
word 由數(shù)字和小寫英文字母組成

方法一：遍歷拆分

這個(gè)問題主要包括三部分：

將數(shù)字從字符串中抽取出來
將數(shù)字的前導(dǎo)零去除
數(shù)字的去重與計(jì)數(shù)

接下來逐個(gè)解決這三個(gè)問題

1. 將數(shù)字從字符串中提取出來：

我們需要一個(gè)布爾類型的變量“lastIsNum”來記錄上一個(gè)字符是否為數(shù)字。初始值為false

同時(shí)，我們還需要一個(gè)字符串，用來存儲(chǔ)整個(gè)字符串中的某個(gè)數(shù)字。string thisString

接下來遍歷字符串。若字符串遍歷結(jié)束或者遍歷到字母字符時(shí)，將lastIsNum標(biāo)記為true，否則將lastIsNum標(biāo)記為false

如果這個(gè)字符是字母，但上一個(gè)字符是數(shù)字，那么就說明我們找到了“一個(gè)數(shù)字的末尾”，此時(shí)我們就提取出了這個(gè)數(shù)字。

處理完這個(gè)數(shù)字記得將字符串清空。

如果這個(gè)字符是數(shù)字，那么直接無腦添加數(shù)字字符串thisString的末尾即可。

2. 將數(shù)字的前導(dǎo)零去除：

使用一個(gè)整數(shù)類型的變量firstLoc來記錄一個(gè)數(shù)字第一個(gè)非零的位置，初始值為-1

接著遍歷數(shù)字字符串，遇到第一個(gè)非零數(shù)字就結(jié)束遍歷，并將firstLoc修改為遍歷到的位置。

如果最后firstLoc的值仍未-1，那么就說明整個(gè)數(shù)字字符串全是0

否則，從firstLoc開始到字符串末尾所組成的子串即為去除前導(dǎo)零后的數(shù)字字符串

3. 數(shù)字的去重與統(tǒng)計(jì)：

題目問的是“有多少不同的數(shù)字”，這就需要我們對(duì)所有的數(shù)字做去重處理。

這個(gè)過程很簡單，直接使用一個(gè)哈希表即可

將所有的處理過的數(shù)字字符串放入哈希表，最后返回哈希表的大小即為去重后的結(jié)果。

時(shí)間復(fù)雜度O(len(word))
空間復(fù)雜度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字符串不同整數(shù)數(shù)目的詳細(xì)內(nèi)容，更多關(guān)于C++ 字符串不同整數(shù)數(shù)目的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: