求一个整数的惩罚数

6441. 求一个整数的惩罚数

给你一个正整数 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) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-10-25 07:31:39

fn dfs(p: usize, sum: i32, i: i32, s: &Vec<u8>) -> bool {
    if p == s.len() { // 递归终点
        return sum == i; // i 符合要求
    }
    let mut x = 0;
    for j in p..s.len() { // 枚举分割出从 s[p] 到 s[j] 的子串
        x = x * 10 + (s[j] & 0xf) as i32; // 子串对应的整数值
        if dfs(j + 1, sum + x, i, s) {
            return true;
        }
    }
    false
}

static mut initialized: bool = false;
static mut pre_sum: [i32; 1001] = [0; 1001];

fn init_once() {
    unsafe {
        if initialized { // 之前初始化过了
            return;
        }
        initialized = true;
        for i in 1..1001 {
            let s = (i * i).to_string().bytes().collect();
            pre_sum[i as usize] = pre_sum[i as usize - 1] + if dfs(0, 0, i, &s) { i * i } else { 0 };
        }
    }
}

impl Solution {
    pub fn punishment_number(n: i32) -> i32 {
        init_once();
        unsafe { pre_sum[n as usize] }
    }
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 41.5 MB, 提交时间: 2023-10-25 07:31:22

/**
 * @param {number} n
 * @return {number}
 */
function dfs(p, sum, s, i) {
    const n = s.length;
    if (p === n) { // 递归终点
        return sum === i; // i 符合要求
    }
    let x = 0;
    for (let j = p; j < n; j++) { // 枚举分割出从 s[p] 到 s[j] 的子串
        x = x * 10 + parseInt(s[j]); // 子串对应的整数值
        if (dfs(j + 1, sum + x, s, i)) {
            return true;
        }
    }
    return false;
}

const PRE_SUM = new Array(1001).fill(0);
for (let i = 1; i <= 1000; i++) {
    const s = (i * i).toString();
    PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(0, 0, s, i) ? i * i : 0);
}

var punishmentNumber = function (n) {
    return PRE_SUM[n];
};

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-25 07:31:03

int PRE_SUM[1001];

int init = []() {
    for (int i = 1; i <= 1000; i++) {
        string s = to_string(i * i);
        int n = s.length();
        function<bool(int, int)> dfs = [&](int p, int sum) -> bool {
            if (p == n) { // 递归终点
                return sum == i; // i 符合要求
            }
            int x = 0;
            for (int j = p; j < n; j++) { // 枚举分割出从 s[p] 到 s[j] 的子串
                x = x * 10 + s[j] - '0'; // 子串对应的整数值
                if (dfs(j + 1, sum + x)) {
                    return true;
                }
            }
            return false;
        };
        PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(0, 0) ? i * i : 0);
    }
    return 0;
}();

class Solution {
public:
    int punishmentNumber(int n) {
        return PRE_SUM[n];
    }
};

python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-23 09:51:28

A = [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, 1296]
class Solution:
    def punishmentNumber(self, n: int) -> int:
        return sum(x * x for x in A if x <= n)

golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-23 09:51:01

var preSum [1001]int

func init() { // 预处理
	for i := 1; i <= 1000; i++ {
		s := strconv.Itoa(i * i)
		n := len(s)
		var dfs func(int, int) bool
		dfs = func(p, sum int) bool {
			if p == n { // 递归终点
				return sum == i // i 符合要求
			}
			x := 0
			for j := p; j < n; j++ { // 从 s[p] 到 s[j] 组成的子串
				x = x*10 + int(s[j]-'0') // 对应的整数值
				if dfs(j+1, sum+x) {
					return true
				}
			}
			return false
		}
		preSum[i] = preSum[i-1]
		if dfs(0, 0) { // i 符合要求
			preSum[i] += i * i // 计算前缀和
		}
	}
}

func punishmentNumber(n int) int {
	return preSum[n]
}

java 解法, 执行用时: 1 ms, 内存消耗: 38.4 MB, 提交时间: 2023-05-23 09:50:33

class Solution {
    private static final int[] PRE_SUM = new int[1001];

    static {
        for (int i = 1; i <= 1000; i++) {
            var s = Integer.toString(i * i).toCharArray();
            PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(s, i, 0, 0) ? i * i : 0);
        }
    }

    private static boolean dfs(char[] s, int i, int p, int sum) {
        if (p == s.length)  // 递归终点
            return sum == i; // i 符合要求
        int x = 0;
        for (int j = p; j < s.length; j++) { // 从 s[p] 到 s[j] 组成的子串
            x = x * 10 + s[j] - '0'; // 对应的整数值
            if (dfs(s, i, j + 1, sum + x))
                return true;
        }
        return false;
    }

    public int punishmentNumber(int n) {
        return PRE_SUM[n];
    }
}

python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-23 09:50:20

'''
判断 [1,1000] 的每个数字 i 是否符合要求，
并预处理 [1,i] 内的符合要求的数字和 preSum。
对于每个数字 i，把它转成字符串 s 后，写一个回溯，
枚举第一个子串、第二个子串、……，累加所有子串对应的整数值之和 sum。
如果存在 sum=i，则说明 i 符合要求。
'''

PRE_SUM = [0] * 1001  # 预处理
for i in range(1, 1001):
    s = str(i * i)
    n = len(s)
    def dfs(p: int, sum: int) -> bool:
        if p == n:  # 递归终点
            return sum == i  # i 符合要求
        x = 0
        for j in range(p, n):  # 从 s[p] 到 s[j] 组成的子串
            x = x * 10 + int(s[j])  # 对应的整数值
            if dfs(j + 1, sum + x):
                return True
        return False
    PRE_SUM[i] = PRE_SUM[i - 1] + (i * i if dfs(0, 0) else 0)

class Solution:
    def punishmentNumber(self, n: int) -> int:
        return PRE_SUM[n]

上一题

下一题

详情