【每日一题Day358】LC2698求一个整数的惩罚数 | 递归

简介: 【每日一题Day358】LC2698求一个整数的惩罚数 | 递归

求一个整数的惩罚数【LC2698】

给你一个正整数 n ,请你返回 n惩罚数

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

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

生日快乐~水一天

  • 思路
  • 枚举1 <= i <= n,判断i*i是否满足条件,如果满足则计数
  • check:通过递归实现,枚举每个分割点,判断是否能成功分割。计算过程中有重复计算,因此可以打表记录
  • 实现
class Solution {
    public int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (check(i * i, i)) ans += i * i;
        }
        return ans;
    }
    boolean check(int t, int x) {
        if (t == x) return true;
        int d = 10;
        while (t >= d && t % d <= x) {
            if (check(t / d, x - (t % d))) return true;
            d *= 10;
        }
        return false;
    }
}

实现打表

class Solution {
    static int[] f = new int[1010];
    static {
        for (int i = 1; i <= 1000; i++) {
            f[i] = f[i - 1];
            if (check(i * i, i)) f[i] += i * i;
        }
    }
    static boolean check(int t, int x) {
        if (t == x) return true;
        int d = 10;
        while (t >= d && t % d <= x) {
            if (check(t / d, x - (t % d))) return true;
            d *= 10;
        }
        return false;
    }
    public int punishmentNumber(int n) {
        return f[n];
    }
}
作者:宫水三叶
链接:https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/solutions/2497448/gong-shui-san-xie-jian-dan-di-gui-yun-yo-qdxl/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


相关文章
【每日一题Day99】LC1663具有给定数值的最小字符串 | 贪心
如果k−(n−i)∗26<=1,那么表示尾部全部插入z,没有分数剩余甚至还有同于,那么第i个字符可以插入的最小字符'a',贡献的分数为1
77 0
【每日一题Day108】LC1798你能构造出连续值的最大数目 | 贪心
局部最优:每次从数组中找到未选择数字中的最小值来更新区间,如果当前连续值x小于选择的数值coin,那么无法获得更大的区间,退出循环
62 0
【每日一题Day87】LC1819序列中不同最大公约数的数 | 数学
由于数组中的最大公约数不可能超过子序列的最大值,因此可以枚举所有可能的最大公约数来判断当前的公约数是否有子序列构成。
129 0
【每日一题Day78】LC1803统计异或值在范围内的数对有多少 | 字典树+容斥原理
不过如果在工程中,不考虑前缀匹配的话,基本上使用 hash 就能满足。如果考虑前缀匹配的话,工程也不会使用 Trie 。一方面是字符集大小不好确定,另外,对于个别的超长字符 Trie 会进一步变深。
100 0
【每日一题Day78】LC1803统计异或值在范围内的数对有多少 | 字典树+容斥原理
【每日一题Day36】LC795区间子数组的个数 | 单调栈 模拟
给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。生成的测试用例保证结果符合 32-bit 整数范围。
110 0
|
9月前
|
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
61 0
|
9月前
【每日一题Day368】LC421数组中两个数的最大异或值 | 字典树
【每日一题Day368】LC421数组中两个数的最大异或值 | 字典树
39 0
|
9月前
【每日一题Day201】LC2436有效时间的数目 | 乘法原理 枚举
【每日一题Day201】LC2436有效时间的数目 | 乘法原理 枚举
69 2
|
9月前
【每日一题Day299】LC2235两整数相加
【每日一题Day299】LC2235两整数相加
39 0
|
9月前
【每日一题Day184】LC2413最小偶倍数 | 数学
【每日一题Day184】LC2413最小偶倍数 | 数学
39 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等