LeetCode 2698. 求一个整数的惩罚数【字符串,回溯,预处理,打表】1678

2023-10-29 17:52

本文主要是介绍LeetCode 2698. 求一个整数的惩罚数【字符串,回溯,预处理,打表】1678,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个正整数 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

解法 数学+字符串+回溯

i 2 i^2 i2 转成字符串 s s s ,然后写一个递归,枚举 s s s 分割出的第一个子串、第二个子串、……,把每个子串对应的整数值 x x x 加到 sum \textit{sum} sum 中。递归到终点时,如果 sum = i \textit{sum}=i sum=i ,则说明 i i i 符合要求。

int PRE_SUM[1001];
int init = []() {for (int i = 1; i <= 1000; i++) {string s = to_string(i * i);int n = s.length();function<bool(int, int)> dfs = [&](int p, int sum) -> bool {if (p == n) return sum == i; // 递归终点,i符合要求int x = 0;for (int j = p; j < n; ++j) { // 枚举分割出从 s[p] 到 s[j] 的子串x = x * 10 + s[j] - '0'; // 子串对应的整数值if (dfs(j + 1, sum + x)) return true;}return false;};PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(0, 0) ? i * i : 0);}return 0;
}();
class Solution {
public:int punishmentNumber(int n) {return PRE_SUM[n];}
};

复杂度分析:

  • 时间复杂度:预处理 O ( U 1 + 2 log ⁡ 10 2 ) ≈ O ( U 1.602 ) \mathcal{O}(U^{1 + 2\log_{10} 2})\approx\mathcal{O}(U^{1.602}) O(U1+2log102)O(U1.602) ,其中 U = 1000 U=1000 U=1000 。对于数字 i 2 i^2 i2 ,它的十进制字符串的长度为 m = ⌊ 1 + 2 log ⁡ 10 i ⌋ m=\lfloor1+2\log_{10} i\rfloor m=1+2log10i
    划分型题目的本质就是枚举子集,所以递归需要 O ( 2 m ) = O ( i 2 log ⁡ 10 2 ) \mathcal{O}(2^m)=\mathcal{O}(i^{2\log_{10} 2}) O(2m)=O(i2log102) 的时间,对其积分可知,整个预处理需要 O ( U 1 + 2 log ⁡ 10 2 ) \mathcal{O}(U^{1 + 2\log_{10} 2}) O(U1+2log102) 的时间。
  • 空间复杂度:预处理 O ( U ) \mathcal{O}(U) O(U)

还可直接打表:

int val[] = {1,9,10,36,45,55,82,91,99,100,235,297,369,370,379,414,657,675,703,756,792,909,918,945,964,990,991,999,1000};
class Solution {
public:int punishmentNumber(int n) {int sum = 0;for (int i = 0; i < 29 && val[i] <= n; ++i)sum += val[i] * val[i];return sum;}
}; 

这篇关于LeetCode 2698. 求一个整数的惩罚数【字符串,回溯,预处理,打表】1678的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/302345

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

uva 10916 Factstone Benchmark(打表)

题意是求 k ! <= 2 ^ n ,的最小k。 由于n比较大,大到 2 ^ 20 次方,所以 2 ^ 2 ^ 20比较难算,所以做一些基础的数学变换。 对不等式两边同时取log2,得: log2(k ! ) <=  log2(2 ^ n)= n,即:log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ,其中 n 为 2 ^

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return