2698. 求一个整数的惩罚数(看官方题解, 已解)

2698. 求一个整数的惩罚数

难度: 中等

来源: 每日一题 2023.10.25

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

示例 1：

输入：n = 10
输出：182
解释：总共有 3 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182

示例 2：

输入：n = 37
输出：1478
解释：总共有 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 <= n <= 1000

class Solution {
    public int punishmentNumber(int n) {

    }
}

分析与题解

打表法, 大聪明写法

打表法实际上就是完全利用空间换时间, 我们把在允许范围内(1 <= n <= 1000)的所有可能性都列举取出, 然后根据题意, 对于某一个数直接取值就好了.

打表法具有快速，易行（可以写暴力枚举程序）的特点，缺点是代码可能太大，或者情况覆盖不完

当数量级较低时, 我们可使用打表法, 但是当数据集很大时, 不建议使用打表法.

接下来, 我们就看一下打表法直接取值的过程.
```
class Solution {
    public int punishmentNumber(int n) {
        int[] array = new int[]{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};
        int result = 0;
        for(int item : array) {
            if (item <= n) {
                result += item * item;
            } else {
                break;
            }
        }
        return result;
    }
}
```
复杂度分析:
- 时间复杂度: O(n), 与 n 大小相关的线性时间复杂度.
- 空间复杂度: O(1), 虽然是创建了一个数组, 但是数组的长度是不会发生改变的. 所以是常量级别的空间复杂度.
结果如下所示.

回溯法

其实很早就听说回溯法, 一直没有实践机会, 今天做这个题目, 看到官方的题解是回溯法, 就是查了查相关的内容. 总算对回溯法有了一个大体的了解.

回溯法别名也叫试探法, 这一叫法突然让我想到在迷宫中找寻出路的问题. 脑子立马出现了如下的图片.

按选优条件向前搜索, 以达到目标. 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

对于这个题目使用回溯法就很直观了. 假设有一个数字为 1234, 目标数字为 33, 也就是将 1234 拆分成很多的连续子串, 然后相加尽量等于 22.

利用回溯法的思想, 我们首先拿出 1 , 那么剩下的 234 的子串组成的数字之和要是 33 - 1 = 32

紧接着 234字符串拿出 2, 那么剩下 34 的子串组成的数字之和要是 33 - 1 - 2 = 30.

剩下的34字符串拿出 3, 剩下4, 不再满足组合提交, 也不能使33 - 1 - 2 - 3 == 4 成立. 所以 4 就是回溯点, 返回上一级.

来到上一级, 既然34字符串拿出 3 不行, 那我们就拿 34, 但是依然不能使 33 - 1 - 2 == 34 成立. 所以 34 就是回溯点, 返回上一级.

来到上一级, 既然234字符串单拿出 2 没有符合条件的组合, 那就拿 23, 剩下 4, 还是不能使 33 - 1 - 23 == 4 成立, 对于拿出 23 再也没有别的组合, 那就继续回溯. 返回上一级.

再次来到上一级, 既然234字符串单拿出 2 单拿出 23 没有符合条件的组合, 那就拿 234, 还是不能使 33 - 1 == 234 成立, 对于拿出 234 再也没有别的组合, 那就继续回溯. 返回上一级.

接下来, 我们就看一下当第一位选择了 1 的回溯过程示意图

然后既然单选 1 不行, 那我们就继续依次分割选择 12子串.

那么继续尽心回溯过程.

剩下的34字符串拿出 3, 剩下4, 不再满足组合提交, 也不能使33 - 12 - 3 == 4 成立. 所以 4 就是回溯点, 返回上一级.

来到上一级, 既然34字符串拿出 3 不行, 那我们就拿 34, 但是依然不能使 33 - 12 == 34 成立. 所以 34 就是回溯点, 返回上一级.

这样看来 12 的整体回溯过程也找不到合适的组合.

继续回溯, 再次选择 123 子串.

剩下4, 不再满足组合提交, 也不能使33 - 123 == 4 成立. 所以 4 就是回溯点, 返回上一级.

继续回溯, 再次选择 1234 子串.

由于 33 != 1234 . 所以到此, 我们得到了最终结论, 1234 不能按照题意分割成满足和是33的子串组合.

回到这个题目, 对于某个数, 我们知道如何通过回溯法判断它是否满足题意. 而 n 则是一个范围, 我们只需要从 1 遍历到 n 即可.
```
int result = 0;
for(int i = 0; i <= n; i++) {
    String s = Integer.toString(i * i);
    if (dfs(s, 0, 0, i)) {
        result += i * i;
    }
}
```
然后, 对于每一个数字, 我们都通过深度遍历的形式进行回溯操作. 那么递归返回条件是啥呢? 主要有以下几个条件.
- 当遍历到最后, 我们需要判断当前的总和与目标总和是否一致.
- 在遍历过程中, 如果当前的总和比目标总和还要大, 后面就不用遍历了(再遍历也是加法, 总和会更大), 直接返回False就行. 表示这个链路失败.
```
public boolean dfs(String s, int pos, int tot, int target) {
    if (pos == s.length()) {
        return tot == target;
    }
    int sum = 0;
    for (int i = pos; i < s.length(); i++) {
        sum = sum * 10 + s.charAt(i) - '0';
        if (sum + tot > target) {
            break;
        }
        if (dfs(s, i + 1, sum + tot, target)) {
            return true;
        }
    }
    return false;
}
```
接下来, 我们就一起看一下整体的解题过程.
```
class Solution {
    public int punishmentNumber(int n) {
        int result = 0;
        for(int i = 0; i <= n; i++) {
            String s = Integer.toString(i * i);
            if (dfs(s, 0, 0, i)) {
                result += i * i;
            }
        }
        return result;
    }
    public boolean dfs(String s, int pos, int tot, int target) {
        if (pos == s.length()) {
            return tot == target;
        }
        int sum = 0;
        for (int i = pos; i < s.length(); i++) {
            sum = sum * 10 + s.charAt(i) - '0';
            if (sum + tot > target) {
                break;
            }
            if (dfs(s, i + 1, sum + tot, target)) {
                return true;
            }
        }
        return false;
    }
}
```
复杂度分析:
- 时间复杂度: O(n²), 最少是 n² 的时间复杂度.
- 空间复杂度: O(logn), 其中 n 表示给定的元素。每次递归需要占用空间，递归的最大深度为数字转换为字符串的长度，因此递归的最大深度为 nlogn，因此空间复杂度为 O(logn)。
结果如下所示.