求一个整数的惩罚数【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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
