求一个整数的惩罚数

难度:

标签:

题目描述

Given a positive integer n, return the punishment number of n.

The punishment number of n is defined as the sum of the squares of all integers i such that:

1 <= i <= n
The decimal representation of i * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

Example 1:

Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2:

Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1. 
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. 
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. 
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

Constraints:

1 <= n <= 1000

代码结果

运行时间: 46 ms, 内存: 16.0 MB

/*
 * 思路：
 * 1. 使用IntStream从1到n进行遍历。
 * 2. 对于每个i，计算i*i，并检查其是否满足条件。
 * 3. 将满足条件的i*i累加。
 * 4. 返回累加的惩罚数之和。
 */
import java.util.stream.IntStream;

public class Solution {
    public int punishmentNumber(int n) {
        return IntStream.rangeClosed(1, n)
                        .map(i -> i * i)
                        .filter(square -> canBeSplit(String.valueOf(square), (int) Math.sqrt(square)))
                        .sum();
    }

    private boolean canBeSplit(String s, int target) {
        return canBeSplitHelper(s, target, 0, 0);
    }

    private boolean canBeSplitHelper(String s, int target, int currentSum, int start) {
        if (start == s.length()) {
            return currentSum == target;
        }
        for (int i = start; i < s.length(); i++) {
            int num = Integer.parseInt(s.substring(start, i + 1));
            if (canBeSplitHelper(s, target, currentSum + num, i + 1)) {
                return true;
            }
        }
        return false;
    }
}

解释

方法:

首先，这个题解通过预计算的方法解决问题，即预先计算了所有可能的 n (从 1 到 1000) 的惩罚数，并将结果存储在数组 ans 中。对于每个 n，计算 n 的平方并转换为字符串 sq。然后，使用一个递归函数 dfs 来尝试所有可能的连续子字符串分割方式，查看这些子字符串的整数和是否等于 n。如果存在这样的分割方式，那么该 n 的惩罚数就是 n 的平方；否则为 0。最后，累加数组 ans 中的值，以便直接通过索引快速回答任何小于等于 1000 的 n 的询问。

时间复杂度:

O(n * 2^k)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么选择预计算所有可能的 n 的惩罚数而不是在每次查询时动态计算？

▷

预计算所有可能的 n 的惩罚数而不是在每次查询时动态计算的主要原因是效率和响应速度。通过预先计算和存储结果，我们可以将查询的时间复杂度降至 O(1)，即直接通过索引访问预计算的结果，这对于需要频繁查询的情况非常有效。相反，如果每次查询时都动态计算，可能需要较复杂的递归或其他计算，特别是当 n 较大时，这将消耗更多计算资源和时间。因此，预计算为我们提供了一个时间换空间的优化策略，特别适合解答多次查询，保证查询效率。

🦆

在递归函数 dfs 中，递归的终止条件是 `start == len(sq)`，这意味着什么？如何确保所有子字符串都被考虑？

▷

在递归函数 `dfs` 中的终止条件 `start == len(sq)` 意味着递归函数已经遍历完了整个平方数字符串 `sq` 的所有字符，没有更多的字符可以用来继续分割。这个条件是检查是否到达字符串的末尾，如果是，则检查当前累积的子字符串的整数和是否等于原始的整数 n。确保所有子字符串被考虑的方法在于，递归函数从当前 `start` 位置向后探索所有可能的分割点，即每次调用 `dfs(i, s + int(sq[start:i]))` 都会尝试从 `start` 到 `i` 的一个新的子字符串，并将其转化为整数加到当前的和 `s` 中。这种方法通过遍历所有可能的分割点来确保覆盖所有可能的子字符串组合。

🦆

您提到的分割点可能性为 `2^9`，这是如何计算得出的？请解释分割点选择的逻辑。

▷

提到分割点可能性为 `2^9` 是基于字符串的最大长度和可能的分割方法计算得出的。例如，如果一个数字 n 的平方产生了一个长度为 10 的字符串（如 n=32，n^2=1024，长度为 4），那么在这个长度为 10 的字符串中，每个字符位置都可以是一个潜在的分割点。从第一个字符到第九个字符，每个位置都可以选择是否作为分割点，因此每个位置都有分割或不分割两种选择。因此，分割的可能性是 `2^9`。分割点选择的逻辑是考虑字符串中每个可能的字符位置，根据这个位置是否作为分割点，递归地探索所有不同的分割组合。

求一个整数的惩罚数

题目描述

代码结果

解释

代码细节讲解

相关问题