今日问题

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

直觉分析

注意，小于 $1000^2$ 的所有数字组合数量均为 $2^5 = 32$。这意味着使用深度优先搜索来决定是否从某个区间中断，每个数字的最大成本仅为 32。

由于 $N \leq 1000$，我们可以采用暴力方法解决该问题。

解决方法

使用深度优先搜索来判断该数是否为惩罚数。

复杂度分析

  • 时间复杂度：$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