2698.求一个整数的惩罚数

链接：2698.求一个整数的惩罚数
难度：Medium
标签：数学、回溯
简介：给你一个正整数 n ，请你返回 n 的 惩罚数 。

题解 1 - cpp

• 编辑时间：2023-10-25
• 执行用时：316ms
• 内存消耗：5.92MB
• 编程语言：cpp
• 解法介绍：dfs计算当前值是否可行。

class Solution {
public:
    bool check(int num) {
        string s = to_string(num * num);
        function<bool(int, int)> dfs = [&](int idx, int target) -> bool {
            if (idx == s.size()) return target == 0;
            for (int cnt = 1; cnt <= s.size() - idx; cnt++) {
                if (dfs(idx + cnt, target - stoi(s.substr(idx, cnt)))) return true;
            }
            return false;
        };
        return dfs(0, num);
    }
    int punishmentNumber(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) res += check(i) ? i * i : 0;
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-10-25
• 执行用时：1416ms
• 内存消耗：15.71MB
• 编程语言：python
• 解法介绍：同上。

def check(num: int) -> bool:
        s = str(num * num)
        def dfs(idx: int, target: int) -> bool:
            if idx == len(s): return target == 0
            for cnt in range(1, len(s) - idx + 1):
                if dfs(idx + cnt, target - int(s[idx: idx + cnt])): return True
            return False
        return dfs(0, num)
    class Solution:
        def punishmentNumber(self, n: int) -> int:
            return sum(i * i if check(i) else 0 for i in range(1, n + 1))

题解 3 - rust

• 编辑时间：2023-10-25
• 执行用时：124ms
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

fn check(num: i32) -> bool {
    let s = num.pow(2).to_string().chars().collect::<Vec<_>>();
    fn dfs(s: &Vec<char>, idx: usize, target: i32) -> bool {
        if idx == s.len() {
            target == 0
        } else {
            for cnt in 1..=(s.len() - idx) {
                if dfs(
                    s,
                    idx + cnt,
                    target - &s[idx..idx + cnt].iter().collect::<String>().parse::<i32>().unwrap(),
                ) {
                    return true;
                }
            }
            false
        }
    }
    dfs(&s, 0, num)
}
impl Solution {
    pub fn punishment_number(n: i32) -> i32 {
        (1..=n).map(|i| if check(i) { i * i } else { 0 }).sum()
    }
}