Leetcode.2698 求一个整数的惩罚数
题目链接
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 = 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 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(n1+2log210) , n n n 是给定的元素。对于给定的元素 n 2 n^2 n2,将其转换为字符串的长度为 ⌊ m = 1 + 2 log 10 i ⌋ \lfloor m = 1 + 2 \log_{10}^{i} \rfloor ⌊m=1+2log10i⌋,回溯时的子状态为 2 m 2^m 2m 个,所以时间复杂度为 O ( n 1 + 2 log 2 10 ) O(n^{1 + 2 \log_{2}^{10}}) O(n1+2log210)。
C++代码:
class Solution {
public:int punishmentNumber(int n) {int ans = 0;function<bool(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;}
};
相关文章:
Leetcode.2698 求一个整数的惩罚数
题目链接 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 的…...
大数据Flink(一百零二):SQL 聚合函数(Aggregate Function)
文章目录 SQL 聚合函数(Aggregate Function) SQL 聚合函数(Aggregate Function) Python UDAF,即 Python AggregateFunction。Python UDAF 用来针对一组数据进行聚合运算,比如同一个 window 下的多条数据、或者同一个 key 下的多条数据等。针对同一组输入数据,Python A…...
因mapjoin加载内存溢出而导致return code 3
因mapjoin加载内存溢出而导致return code 3 问题描述:日志定位: 问题描述: 例行Hive作业报错 日志定位: Starting to launch local task to process map join; maximum memory 5172101120 [2023-10-16 07:56:51,530] - INFO:…...
pip 指定源
pip定源 # 指定豆瓣 python -m pip install transformers -i http://pypi.douban.com/simple/ --trusted-host pypi.douban.com参考 出现错误:Looking in indexes:https://pypi.tuna.tsinghua.edu.cn/simple...
嵌入式中的MCU、ARM、DSP、FPGA
目录 “角色扮演” MCU ARM 特点 DSP 特点 FPGA 特点 应用 “角色扮演” MCU(Microcontroller Unit)、ARM(Advanced RISC Machine)、DSP(Digital Signal Processor)和FPGA(Field-Progr…...
二、PHP基础学习[变量]
部分内容引用自:https://blog.csdn.net/lady_killer9/article/details/108978062 一、PHP基础学习 1.语法与注释 示例: <?php // PHP 代码/* 这是 PHP 多行 注释 */ ?>2.输出 示例:echo 123; 3.变量 规矩: 变量以 …...
k8s kubeadm配置
master 192.168.41.30 docker、kubeadm、kubelet、kubectl、flannel node01 192.168.41.31 docker、kubeadm、kubelet、kubectl、flannel node02 192.168.41.32 do…...
B-3:Web安全之综合渗透测试
B-3:Web安全之综合渗透测试 任务环境说明: 服务器场景:Server2104(关闭链接) 服务器场景用户名、密码:未知 1.通过URL访问http://靶机IP/1,对该页面进行渗透测试,将完成后返回的结果内容作为FLAG值提交; 通过访问IP/1,查看源代码发现flagishere,访问后发现什么也没…...
设计模式—设计模式总览
设计模式—设计模式总览 在 1994 年,由 Erich Gamma、Richard Helm、Ralph Johnson 和 John Vlissides 四人合著出版了一本名为 《Design Patterns - Elements of Reusable Object-Oriented Software》(中文译名:《设计模式 - 可复用的面向对…...
C++ 流程控制(分支、循环、跳转)
#include<iostream>using namespace std;int main() {// 单分支和双分支cout << "please enter your age:" << endl;int age;cin >> age;if(age > 18){cout << "welcome! adult." << endl;}else{cout << &qu…...
【网络协议】聊聊TCP的三挥四握
上一篇我们说了网络其实是不稳定的,TCP和UDP其实是两个不同的对立者,所以TCP为了保证数据在网络中传输的可靠性,从丢包、乱序、重传、拥塞等场景有自己的一套打法。 TCP格式 源端口和目标端口是不可缺少的,用以区分到达发送给拿…...
Docker镜像仓库
Docker镜像仓库 一、Docker镜像的创建1.1、基于已有镜像创建1.2、基于本地模板创建1.3、基于Dockerfile创建(使用最广泛)1.3.1、联合文件系统(UnionFS)1.3.2、镜像加载原理1.3.3、Dockerfile1.3.4、Docker 镜像结构的分层 二、如何…...
跨界技术:SOCKS5代理在电商、爬虫与游戏领域的应用
随着技术的日益发展,各种工具和技术手段被广泛应用于不同的领域。其中,SOCKS5代理、跨界电商、爬虫技术、出海策略以及游戏产业都成为了当下最热门的话题。本文将探讨这些关键技术如何相互融合,为企业和个人带来更多的机会和挑战。 1. SOCKS…...
LeetCode--快速排序
文章目录 1 排序原理2 代码实现 1 排序原理 quickSort(int[] arr, int left, int right) 参数描述 arr: 待排序的数组left: 排序的左边位置right: 排序的右边位置 排序步骤: 先选取左边节点的数据作为 pivot从右边开始, 向左遍历节点数据, 在满足right > left 条件前提下…...
2023年CSP-S赛后总结(2023CSP-S题解)
目录 T1 题目描述 输入格式 输出格式 代码 T2 题目描述 输入格式 输出格式 题目描述 输入格式 输出格式 题意翻译 代码 T3 题目背景 题目描述 输入格式 输出格式 代码 T4 题目描述 输入格式 输出格式 总结 T1 题目描述 小 Y 有一把五个拨圈的密码锁。…...
Django viewsets 视图集与 router 路由实现评论接口开发
正常来说遵循restful风格编写接口,定义一个类包含了 get post delete put 四种请求方式,这四种请求方式是不能重复的 例如:获取单条记录和多条记录使用的方式都是get,如果两个都要实现的话那么得定义两个类,因为在同一个类中不能有…...
RCE 远程代码执行漏洞分析
RCE 漏洞 1.漏洞描述 Remote Command/Code Execute 远程命令执行/远程代码执行漏洞 这种漏洞通常出现在应用程序或操作系统中,攻击者可以通过利用漏洞注入恶意代码,并在受攻击的系统上执行任意命令。 2.漏洞场景 PHP 代码执行PHP 代码注入OS 命令执…...
JDK8新特性:Stream流
目录 1.获取Stream流 2.Stream流常见的中间方法 3.Stream流常见的终结方法 1、 Stream 是什么?有什么作用?结合了什么技术? ●也叫 Stream 流,是Jdk8开始新增的一套 API ( java . util . stream .*),可以用于操作集…...
【.net core】yisha框架单页面双列表联动效果示例
gridTable1列表数据为gridTable别表数据的子数据,点击gridTable时gridTable1列表数据更新, {Layout "~/Views/Shared/_Index.cshtml";} <div class"container-div"><div class"row"><div id"search…...
01. 板载硬件资源和开发环境
一、板载硬件资源 STM32F4VGT6-DISCOVERY硬件资源如下: (1). STM32F407VGT6微控制器有1M的FLASH存储器,192K的RAM,LQFP100封装 (2). 板上的ST-LINK_V2可以使用选择的方式把套件切换成一个独立的ST-LINK/V2来 使用(可以使用SWD…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
