武功县住房和城乡建设局网站,网易企业邮箱收费版,泉州企业自助建站,行业网站渠道选择和内容运营题目链接 Leetcode.2698 求一个整数的惩罚数 rating : 1679 题目描述
给你一个正整数 n n n #xff0c;请你返回 n n n 的 惩罚数 。 n n n 的 惩罚数 定义为所有满足以下条件 i i i 的数的平方和#xff1a; 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n i ∗ i i * i i∗i 的…题目链接 Leetcode.2698 求一个整数的惩罚数 rating : 1679 题目描述
给你一个正整数 n n n 请你返回 n n n 的 惩罚数 。 n n n 的 惩罚数 定义为所有满足以下条件 i i i 的数的平方和 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n i ∗ i i * i i∗i 的十进制表示的字符串可以分割成若干连续子字符串且这些子字符串对应的整数值之和等于 i i i 。
示例 1 输入n 10 输出182 解释总共有 3 个整数 i 满足要求 1 因为 1 * 1 19 因为 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 19 因为 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 1 \leq n \leq 1000 1≤n≤1000
解法回溯
我们定义 d f s ( u , s u m , t , s ) dfs(u,sum,t,s) dfs(u,sum,t,s) 表示 s s s 能否拆分成若个子字符串能够满足这些子字符串的值加起来 t t t。
我们直接回溯枚举每一个子串的分割位置求出所有可能。
时间复杂度 O ( n 1 2 log 2 10 ) O(n^{1 2 \log_{2}^{10}}) O(n12log210) n n n 是给定的元素。对于给定的元素 n 2 n^2 n2将其转换为字符串的长度为 ⌊ m 1 2 log 10 i ⌋ \lfloor m 1 2 \log_{10}^{i} \rfloor ⌊m12log10i⌋回溯时的子状态为 2 m 2^m 2m 个所以时间复杂度为 O ( n 1 2 log 2 10 ) O(n^{1 2 \log_{2}^{10}}) O(n12log210)。
C代码
class Solution {
public:int punishmentNumber(int n) {int ans 0;functionbool(int,int,int,string) dfs [](int u,int sum,int t,string s)-bool{if(u s.size()){return sum t;}if(sum t) return false;for(int i u , d 0;i s.size();i){d d * 10 s[i] - 0;if(dfs(i 1,sum d,t,s)) return true;}return false;};for(int x 1;x n;x){string s to_string(x * x);if(dfs(0,0,x,s)) ans x * x;}return ans;}
};
