題目資訊

題目編號: 2999
題目連結: Count the Number of Powerful Integers
主題: Math, String, Dynamic Programming

題目敘述

你有三個整數 start、finish 和 limit。你也有一個0-索引的字串 s，它表示一個正整數。

如果一個正整數 x 以 s 結尾（換句話說，s 是 x 的後綴）且 x 中的每個數字都不超過 limit，則稱 x 為強大的整數。

返回在範圍 [start..finish] 內強大的整數的總數。

當且僅當字串 x 是字串 y 的某個索引（包括 0）開始的字串，並延伸到索引 y.length - 1 時，x 是 y 的後綴。例如，25 是 5125 的後綴，而 512 不是。

範例 1:

輸入: start = 1, finish = 6000, limit = 4, s = "124"
輸出: 5
解釋: 在範圍 [1..6000] 內的強大整數有 124、1124、2124、3124 和 4124。所有這些整數的每位數字都 <= 4，且以 "124" 為後綴。注意，5124 不是一個強大整數，因為它的第一位數是 5，大於 4。
可以證明在這個範圍內只有 5 個強大整數。

範例 2:

輸入: start = 15, finish = 215, limit = 6, s = "10"
輸出: 2
解釋: 在範圍 [15..215] 內的強大整數有 110 和 210。所有這些整數的每位數字都 <= 6，且以 "10" 為後綴。
可以證明在這個範圍內只有 2 個強大整數。

範例 3:

輸入: start = 1000, finish = 2000, limit = 4, s = "3000"
輸出: 0
解釋: 在範圍 [1000..2000] 內的所有整數都小於 3000，因此 "3000" 不能是這個範圍內任何整數的後綴。

約束條件:

$1 \leq \text{start} \leq \text{finish} \leq 10^{15}$
$1 \leq \text{limit} \leq 9$
$1 \leq \text{s.length} \leq \lfloor \log_{10}(\text{finish}) \rfloor + 1$
s 僅包含數字，且這些數字最多為 limit。
s 不含前導零。

直覺

此問題要求我們計數在給定範圍 [start..finish] 內滿足兩個條件的整數：每個數字最多為 limit，且整數必須以尾碼 s 結尾。這暗示需要兩個步驟的過程：根據 limit 生成潛在的整數，然後匹配它們的尾碼 s。挑戰在於考慮到範圍可能很大，需要高效地執行此操作。

解法

解決此問題的方法包括將任務分解為可管理的步驟：

字串轉換和範圍調整：
- 將邊界 start 和 finish 轉換為字串格式，以便於操作個別數字。
- 將 start 減去 1，以使用半開區間的邏輯 (start..finish]。
計算函數：
- 定義一個輔助函數 calculate，用於確定對於給定邊界字串 x，有多少 “强力整數” 存在。
- 計算 finish 和 start - 1 的強力整數，並通過這兩個值的差來確定結果。
尾碼和長度檢查：
- 如果字串 x 的長度小於尾碼 s，立即返回 0，因為 x 不可能以 s 結尾。
- 如果 x 和 s 的長度相等，只需要直接比較它們，以確定 x 是否為強力整數。
逐位數字檢查：
- 當 x 長於 s 時，迭代檢查 x 的每個數字，直到 s 範圍開始（形成前綴）。
- 對於每個前綴數字，檢查它是否超出了 limit。如果超過，則計算基於此位置的數字排列受 limit 約束的所有可能數字，並返回計數。
前綴建構和計數：
- 根據先前未違反 limit 的數字選擇，構造可能的數字，使用 $(limit + 1)$ 的冪次來計算所有可能的組合。
- 當 x 的尾碼大於或等於 s 時，將其包含在計數中，因為這表示至少存在一個有效的數字在給定的條件下以 s 結尾。

此方法通過個別考慮數字，並對 limit 下的可能性進行指數計數，確保全面覆蓋所有適用的數字，達到適用於大輸入的效率。

程式碼

C++

class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        // 將起始和結束數字轉換為字串
        string startStr = to_string(start - 1);
        string finishStr = to_string(finish);
        
        // 計算範圍 (start..finish] 中強大的整數數量
        return calculate(finishStr, s, limit) - calculate(startStr, s, limit);
    }

    long long calculate(string x, string s, int limit) {
        // 如果 x 的長度小於 s，則 x 不可能有 s 作為後綴
        if (x.length() < s.length()) {
            return 0;
        }
        
        // 如果 x 和 s 長度相同，則直接比較
        if (x.length() == s.length()) {
            return x >= s ? 1 : 0;
        }

        // 提取與 s 長度相同的 x 的後綴
        string suffix = x.substr(x.length() - s.length(), s.length());
        long long count = 0;
        int preLen = x.length() - s.length();

        // 遍歷 x 的前綴部分
        for (int i = 0; i < preLen; i++) {
            // 如果任何一位數字超出限制，計算可能形成的數字並退出
            if (limit < (x[i] - '0')) {
                count += static_cast<long>(pow(limit + 1, preLen - i));
                return count;
            }
            
            // 計算可以形成的數字直到當前數字
            count += static_cast<long>(x[i] - '0') * static_cast<long>(pow(limit + 1, preLen - 1 - i));
        }

        // 如果 x 的後綴大於或等於 s，則加 1
        if (suffix >= s) {
            count++;
        }

        return count;
    }
};

Python

class Solution:
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        # 將 start 和 finish 數字轉換為字串
        startStr = str(start - 1)
        finishStr = str(finish)
        
        # 計算範圍 (start..finish] 中強力整數的數量
        return self.calculate(finishStr, s, limit) - self.calculate(startStr, s, limit)

    def calculate(self, x: str, s: str, limit: int) -> int:
        # 如果 x 的長度小於 s，則 x 無法有 s 作為後綴
        if len(x) < len(s):
            return 0
        
        # 如果 x 和 s 的長度相同，直接比較它們
        if len(x) == len(s):
            return 1 if x >= s else 0

        # 提取與 s 長度相同的 x 的後綴
        suffix = x[-len(s):]
        count = 0
        preLen = len(x) - len(s)

        # 遍歷 x 的前綴部分
        for i in range(preLen):
            # 如果任何位數超過限制，計算可能的數字並退出
            if limit < int(x[i]):
                count += (limit + 1) ** (preLen - i)
                return count
            
            # 計算到目前位數可以形成的數量
            count += int(x[i]) * (limit + 1) ** (preLen - 1 - i)

        # 如果 x 的後綴大於等於 s，則加 1
        if suffix >= s:
            count += 1

        return count

複雜度分析

時間複雜度: $O(n)$
空間複雜度: $O(1)$

CS Note
En

Leetcode 2999. Count the Number of Powerful Integers

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析