LeetCode2698.求一个整数的惩罚数

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode2698.求一个整数的惩罚数【medium】。

题目描述

给你一个正整数 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

题目分析

①问题要求计算一个给定正整数n的惩罚数，其中惩罚数是由满足一定条件的数字的平方和组成的。这个条件是：将数字的平方表示为一个字符串，然后将这个字符串分割成若干连续子字符串，这些子字符串对应的整数值之和必须等于原数字。
②问题的关键在于对字符串s进行枚举分割，分割成s[0……i]s[i+1……j]，依次枚举剩下的子字符串，同时验证这种分割方案是否满足要求。依次考虑每一个字符，都有两种可能，一是逗号分割，构成新的子字符串，二是并入下一个字符串，由此得到一个树结构（以36的平方1296为例）：
树状结构图
对于解为树状结构的问题，我们很容易想到使用回溯法来解决。

回溯法：回溯算法是系统地搜索问题的解的方法。某个问题的所有可能解的称为问题的解空间，若解空间是有限的，则可将解空间映射成树结构。
任何解空间可以映射成树结构的问题，都可以使用回溯法。回溯法是能够在树结构里搜索到通往特定终点的一条或者多条特定路径。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。
值得注意，回溯法以深度优先搜索的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

③变量确立：我们使用一个DFS(int pos, int tot, int target, string s)函数来进行回溯，pos变量来代表当前的字符串索引，表示我们在字符串的哪个位置；tot是之前已经划分的子字符串之和；target代表目标值，我们要累积的数字之和必须等于 target；s是输入的数字字符串，代表一个数字的平方，例如 “81” 表示 9 * 9 的平方。
④边界条件确立：如果 pos 等于 s 的长度，这表示我们已经处理了整个字符串。在这种情况下，我们需要检查 tot 是否等于 target。
如果 tot 等于 target，说明我们已经成功地将字符串中的子字符串组合成满足条件的数，可以返回 true，否则返回 false。
⑤在每一步，我们都会尝试从当前位置 pos 开始创建一个新的子字符串，我们从 pos 开始向后遍历字符串 s。新构建的这个字符串的值用curSum来代表。
将当前字符添加到 curSum 中，将其从字符形式转换为整数，并更新 curSum。
如果 curSum + tot 大于 target，则跳出循环，因为这个子字符串无法继续累积得到满足条件的数。
否则，我们将继续递归调用 DFS 方法，将当前位置 i + 1 传递下去，同时更新 curSum + tot 作为累积值tot。
⑥如果在递归的过程中找到了一个组合，满足 tot 等于 target，则返回 true 表示成功。否则，在循环结束后返回 false 表示没有找到满足条件的组合。

题解

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public bool DFS(int pos, int tot, int target, string s)
{
    if(pos == s.Length) {
        return tot == target;
    }
    int curSum = 0;
    for(int i = pos; i < s.Length; i++) {
        curSum = curSum * 10 + s[i] - '0';
        if(curSum + tot > target) {
            return false;
        }
        if(DFS(i + 1, curSum + tot, target, s))
        {
            return true;
        }
    }
    return false;
}

public int PunishmentNumber(int n)
{
    int res = 0;
    for(int i = 1; i <= n; i++){
        string s = (i * i).ToString();
        if(DFS(0, 0, i, s)) {
            res += i * i;
        }
    }
    return res;
}