今日题目

https://leetcode.com/problems/find-the-punishment-number-of-an-integer/description/

解题思路

注意对于小于 $1000^2$ 的数，其所有分割方案数最多为 $2^5 = 32$。这意味着如果用 DFS 来决定是否在某个位置切分，每个数最多只需枚举 32 种情况。

由于 $N \leq 1000$，可以直接用暴力方法解决。

解题方法

使用 DFS 判断一个数是否能成为惩罚数。

复杂度分析

  • 时间复杂度：$O(N\times 2^{log(N)})$，其中 N 的含义与题目描述一致。

  • 空间复杂度：$O(1)$。

代码

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def check(x, now, s, nows, cnt):
            if now == 0:
                return (s + nows) == x
            if s > x:
                return False
            flag = check(x, now // 10, s, nows + now % 10 * (10 ** cnt), cnt + 1)
            if flag:
                return True
            flag |= check(x, now // 10, s + nows, now % 10, 1) 

            return flag

        ans = 0
        for i in range(n + 1):
            if check(i, i*i, 0, 0, 0):
                ans += i * i

        return ans

class Solution:
    def punishmentNumber(self, n: int) -> int:
        punishmentNumbers = [0, 1, 9, 10, 36, 45, 55, 82, 91, 99, 100, 235, 297, 369, 370, 379, 414, 657, 675, 703, 756, 792, 909, 918, 945, 964, 990, 991, 999, 1000]

        ans = 0
        for x in punishmentNumbers:
            if x > n:
                return ans
            ans += x * x
        
        return ans

普通解法结果：

image.png

最快解法结果：

image.png