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

力扣題目鏈接：leetcode.cn/problems/nu…

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

輸入：word = "a1b01c001"
輸出：1
解釋："1"、"01" 和 "001" 視為同一個整數(shù)的十進制表示，因為在比較十進制值時會忽略前導(dǎo)零的存在。

提示：

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

方法一：遍歷拆分

這個問題主要包括三部分：

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

接下來逐個解決這三個問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 時間復(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)文章！

最新評論