題目資訊

題目編號: 2698
題目連結: Find the Punishment Number of an Integer
主題: Math, Backtracking

題目敘述

給定一個正整數 $n$，返回 $n$ 的_懲罰數字_。

$n$ 的懲罰數字定義為所有整數 $i$ 的平方和，其中：

$1 \leq i \leq n$
$i \times i$ 的十進制表示可以被劃分為連續的子字串，使得這些子字串的整數值之和等於 $i$。

範例 1:

輸入：n = 10
輸出：182
解釋：在範圍 [1, 10] 中，有且僅有 3 個整數 i 滿足條件：
- 1 因為 1 * 1 = 1
- 9 因為 9 * 9 = 81，並且 81 可以被劃分為 8 和 1，其和為 8 + 1 == 9。
- 10 因為 10 * 10 = 100，並且 100 可以被劃分為 10 和 0，其和為 10 + 0 == 10。
因此，10 的懲罰數字為 1 + 81 + 100 = 182

範例 2:

輸入：n = 37
輸出：1478
解釋：在範圍 [1, 37] 中，有且僅有 4 個整數 i 滿足條件：
- 1 因為 1 * 1 = 1。 
- 9 因為 9 * 9 = 81，並且 81 可以被劃分為 8 + 1。 
- 10 因為 10 * 10 = 100，並且 100 可以被劃分為 10 + 0。 
- 36 因為 36 * 36 = 1296，並且 1296 可以被劃分為 1 + 29 + 6。
因此，37 的懲罰數字為 1 + 81 + 100 + 1296 = 1478

約束條件：

$1 \leq n \leq 1000$

直覺

這個問題涉及確定在給定範圍內的特定整數，滿足當其平方被分割時的一個特定條件。具體來說，對於給定的整數 $i$，其平方 $i \times i$ 應該可以分割成連續的子字串，這樣這些子字串的和等於 $i$ 本身。目標是從 1 到 $n$ 的所有這樣的整數的平方和。這歸結為一種結合數字操作和動態規劃的方法，用於有效地探索可能的分割。

解法

此解法利用數字提取和動態規劃方法來判斷給定的整數 $i$ 是否滿足指定條件。以下是詳細的步驟：

計算數字數量：一個輔助函數計算數字中的數字數量，這有助於遍歷可能的子字串分割。
提取子字串：另一個輔助函數允許我們從任何給定的數字中使用數字索引提取子字串數字。這對於有效地分割平方數至關重要。
分割驗證：採用動態規劃方法來探索將 $i \times i$ 的十進制表示法分割成各種可能方式的所有可能性。具體過程如下：
- 初始化一個動態規劃表 dp，其中每個條目 dp[k] 包含到平方數的第 $k$ 位位置的所有可能的和。
- 通過遍歷子字串的可能結束索引，並計算從較早的分割延伸到這一索引的所有可能分割和，來填充該表。
- 檢查最終分割列表中的任何和是否等於原始數字 $i$。如果存在，則表示有一個有效的分割。
主要執行：主要函數 punishmentNumber 遍歷所有從 1 到 $n$ 的整數：
- 對於每一個整數 $i$，計算其平方。
- 使用分割驗證函數檢查這個平方是否可以分割成和等於 $i$。
- 如果滿足分割條件，將平方累加到總懲罰數中。

此方法有效地檢查每個可能的數字是否具備其平方的分割性質，確保每個有效案例將其平方貢獻到最終的和。精確的數字操作結合動態規劃使得該解法在給定的限制下既全面又高效。

程式碼

C++

class Solution {
public:
    // 函數：返回給定數字的位數
    int countDigits(int num) {
        int count = 0;
        while (num > 0) {
            num /= 10;
            count++;
        }
        return count;
    }

    // 函數：從數字 'num' 中擷取從 'beg_idx' 到 'end_idx' 的子字串數字，給定 'num' 有 'digits' 位數
    int extractSubNumber(int num, int beg_idx, int end_idx, int digits) {
        // 移除超出 end_idx 的前置位數
        num /= pow(10, digits - end_idx - 1);
        // 擷取相關的子字串部分作為數字
        return num % int(pow(10, end_idx - beg_idx + 1));
    }

    // 函數：檢查一個數字的平方是否可以滿足條件
    bool isValidPartition(int num, int target) {
        int digits = countDigits(num);
        
        // 動態規劃表：儲存每個索引的可能和組合
        vector<vector<int>> dp(digits);
        
        // 初始化第一位數
        dp[0].push_back(extractSubNumber(num, 0, 0, digits));
        
        // 填入所有子字串結束索引的可能和到DP表中
        for (int i = 1; i < digits; i++) {
            dp[i].push_back(extractSubNumber(num, 0, i, digits));
            for (int j = 1; j <= i; j++) {
                int currentNum = extractSubNumber(num, j, i, digits);
                if (!dp[j - 1].empty()) {
                    for (int partialSum : dp[j - 1]) {
                        dp[i].push_back(partialSum + currentNum);
                    }
                }
            }
        }

        // 檢查是否有任何和匹配目標值
        for (int partitionSum : dp[digits - 1]) {
            if (partitionSum == target) {
                return true;
            }
        }
        
        return false;
    }

    // 主函數：計算 'n' 的懲罰數字
    int punishmentNumber(int n) {
        int totalPunishment = 0;
        
        // 遍歷從1到n的所有整數
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            // 檢查當前數字的平方是否可以分區加總為該數字
            if (isValidPartition(square, i)) {
                totalPunishment += square;
            }
        }
        
        return totalPunishment;
    }
};

Python

class Solution:
    # 函數用來返回給定數字中的位數
    def countDigits(self, num):
        count = 0
        while num > 0:
            num //= 10
            count += 1
        return count

    # 函數用來從 'num' 中提取從 'beg_idx' 到 'end_idx' 的子字串數字，給定 'num' 有 'digits' 位數
    def extractSubNumber(self, num, beg_idx, end_idx, digits):
        # 移除超出 end_idx 的前導位數
        num //= 10**(digits - end_idx - 1)
        # 提取相關的子字串部分作為數字
        return num % 10**(end_idx - beg_idx + 1)

    # 函數用來檢查一個數字的平方能否滿足條件
    def isValidPartition(self, num, target):
        digits = self.countDigits(num)
        
        # 動態規劃表格用來存儲每個索引可能的和組合
        dp = [[] for _ in range(digits)]
        
        # 初始化第一位數
        dp[0].append(self.extractSubNumber(num, 0, 0, digits))
        
        # 用每個子字串結束索引的所有可能的和填滿 DP 表
        for i in range(1, digits):
            dp[i].append(self.extractSubNumber(num, 0, i, digits))
            for j in range(1, i + 1):
                currentNum = self.extractSubNumber(num, j, i, digits)
                if dp[j - 1]:
                    for partialSum in dp[j - 1]:
                        dp[i].append(partialSum + currentNum)

        # 檢查是否有任何和匹配目標值
        for partitionSum in dp[digits - 1]:
            if partitionSum == target:
                return True
        
        return False

    # 計算 'n' 的懲罰數的主函數
    def punishmentNumber(self, n):
        totalPunishment = 0
        
        # 遍歷從 1 到 n 的所有整數
        for i in range(1, n + 1):
            square = i * i
            # 檢查當前數字的平方是否能被分割並加總到數字
            if self.isValidPartition(square, i):
                totalPunishment += square
        
        return totalPunishment

複雜度分析

時間複雜度: $O(n \cdot d^3)$，其中 $n$ 是輸入的整數，$d$ 是最大數字平方 ($n \times n$) 的數字位數。推導如下：
- 外部循環迭代 $n$ 次，每次對於從 $1$ 到 $n$ 的每一個整數。
- 在此循環內，會調用 isValidPartition 方法，其中：
  - 確定 $i \times i$ 的數字位數，其複雜度為 $O(\log(i^2)) = O(\log(i))$（對應於 $\log(n^2) \approx 2 \log(n)$，且限制在 $d$）。
  - 初始化一個動態規劃表，具有 $d$ 行，每行可能需要評估所有可能的子切割方案，即從 $0$ 到 $d-1$。考慮到嵌套循環和潛在的 DP 傳播，這使得循環複雜度大約為 $O(d^3)$。
- 因此，$n$ 次外部迭代和 $O(d^3)$ 的內部複雜度的組合，得出 $O(n \cdot d^3)$。
空間複雜度: $O(d^2)$，其中 $d$ 是可能的最大平方數 ($n \times n$) 的數字位數。這是由於 isValidPartition 中所使用的動態規劃表，該表可以儲存到每個數字位位置的所有可能和，從而在每個數字從 $0$ 到 $d-1$ 的情況下，可能導致 $O(d)$ 個不同條目。

CS Note
En

Leetcode 2698. Find the Punishment Number of an Integer

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析