本文主要是介绍【每日一题】2698. 求一个整数的惩罚数-2023-10.25,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
2698. 求一个整数的惩罚数
给你一个正整数 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) {int res=0;for(int i=1;i<=n;i++){String s=Integer.toString(i*i);if(dfs(s,0,0,i)){res+=i*i;}}return res;}public boolean dfs(String s,int pos,int tot,int target){if(pos == s.length()){return tot==target;}int sum=0;for(int i=pos;i<s.length();i++){sum=sum*10+s.charAt(i)-'0';if(sum+tot>target){break;}if(dfs(s,i+1,sum+tot,target)){return true;}}return false;}
}
结果:
这篇关于【每日一题】2698. 求一个整数的惩罚数-2023-10.25的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!