LeetCode279. 完全平方数(2024冬季每日一题 27)
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
提示:
1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104
思路:动态规划
- f[i] 表示最少需要多少个数的平方来表示整数 i
- 对于当前 i,计算对应的 f[i] 的状态转移方程
- 可以看组成 i 的完全平方数的最后一个数,假设为 j
- 显然,f[i] = f[i - j * j] + 1,1 代表最后一个数为 j
- 可以枚举所有可能的 j ,求出数量最少的 f[i],即组成 i 所用最少的完全平方数
- 取最小的一个,即有 f[i] = min(f[i], f[i - j * j] + 1);
- 注意,初始时需要将 f 全部位置初始化为最大值,f[0] = 0
class Solution {
public:int f[10010];int numSquares(int n) {memset(f, 0x3f, sizeof f);f[0] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j * j <= i; j++){f[i] = min(f[i], f[i-j*j] + 1);}}return f[n];}
};
相关文章:
LeetCode279. 完全平方数(2024冬季每日一题 27)
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。 …...
Scala 隐式转换
object test {//复习隐式转换://隐式转换:编译器 偷偷地,自动地帮我们把一种数据转换为另一种类型//例如:int --> double//它有失败的时候(double --> int),有成功的时候//当它转换失败的…...
K8S命令部署后端(流水线全自动化部署)
前言 本文为链接: 云效流水线k8s半自动部署java(保姆级)的补充,本文起初的目的是为了补充完善k8s流水线的全自动化部署,但是也适用于k8s的一键重启,因为使用k8s的web页面容易出现漏点的情况,因此也可以把代码保存为shell脚本,同样可以实现一键重启。关于…...
Ubuntu中配置交叉编译工具的三条命令的详细研究
关于该把下面的三条交叉编译配置语句加到哪里,详情见 https://blog.csdn.net/wenhao_ir/article/details/144326545 的第2点。 现在试解释下面三条交叉编译配置语句: export ARCHarm export CROSS_COMPILEarm-buildroot-linux-gnueabihf- export PATH$…...
【PyQt5教程 二】Qt Designer 信号与槽的使用方法及PyQt5基本小部件说明
目录 一、信号与槽机制: 二、信号与槽使用方法: (1)使用Qt Designer 的信号与槽编辑器: (2)使用固定语法直接建立信号槽连接: 三、PyQt小部件及其触发信号: &#x…...
编程语言中接口(Interface)介绍
编程语言中接口(Interface)介绍 在编程语言中,“接口”(Interface)是一种抽象类型,定义了一组方法(和属性),但不包含其具体实现。接口通常用于规定类必须实现的行为&…...
算法学习之贪心算法
前言 记录一下,免得又又忘了 贪心算法 在刚接触的时候,我一直觉得贪心和动态规划有相似之处,但做过的题目看,贪心似乎不用迭代...
【jvm】垃圾回收的优点和原理
目录 1. 说明2. 优点3. 原理3.1 发现无用对象3.2 回收无用对象所占用的内存 4. 回收算法4.1 标记-清除算法4.2 复制算法4.3 标记-整理算法4.4 分代收集算法 1. 说明 1.JVM(Java虚拟机)垃圾回收是Java语言的一大特性,它自动管理内存ÿ…...
YOLO系列发展历程:从YOLOv1到YOLO11,目标检测技术的革新与突破
文章目录 前言一、YOLOv1:单阶段目标检测的开端二、YOLOv2:更精准的实时检测三、YOLOv3:阶梯特征融合四、YOLOv4:性能和速度的新平衡五、YOLOv5:易用性和扩展性的加强六、YOLOv6:工业部署的利器七、YOLOv7&…...
深入浅出:序列化与反序列化的全面解析
文章目录 1. 引言2. 什么是序列化?2.1 为什么需要序列化? 3. 什么是反序列化?3.1 反序列化的重要性 4. 序列化与反序列化的实现4.1 JSON (JavaScript Object Notation)4.2 XML (eXtensible Markup Language)4.3 Protocol Buffers (Protobuf)4…...
word实践:正文/标题/表图等的共用模板样式设置
说在前面 最近使用word新建文件很多,发现要给大毛病,每次新建一个word文件,标题/正文的字体、大小和间距都要重新设置一遍,而且每次设置这些样式都忘记了参数,今天记录一下,以便后续方便查看使用。现在就以…...
Blender中使用BlenderGIS插件快速生成城市建筑模型
导入下载 BlenderGIS 插件 去github上下载其压缩包,地址如下: https://github.com/domlysz/BlenderGIS 在BlenderGIS中导入这个插件压缩包: 点击上方菜单栏的编辑,点击偏好设置 在插件>从磁盘安装中导入刚刚下载的压缩包 可…...
【单元测试】单元测试的重要性
1一些错误的认识 在实际的单元测试过程中总会有一些错误的认识左右着我们,使之成为单元测试最大的障碍,在此将其一一分析如下: 它太浪费时间了,现在要赶进度,时间上根本不允许,或者随便做做应付领导。 …...
Codeforces Round 992 (Div. 2)
这场cf只在b卡了一下,因为b真是犯蠢了,我以为会向下取整,结果是完全就不取整,或者说是向上取整,卡了我半个小时,要不是紧急看了题一下,昨天那场就毁了 话不多说,直接开讲 A. Game …...
el-table一键选择全部行,切换分页后无法勾选
el-table一键全选,分页的完美支持 问题背景尝试解决存在问题问题分析 解决方案改进思路如下具体代码实现如下 问题背景 现在有个需求,一个表格有若干条数据(假设数量大于20,每页10条,保证有2个以上分页即可)。 现在需要在表格上方…...
负载均衡最佳实践及自定义负载均衡器
文章目录 负载均衡最佳实践及自定义负载均衡器一、负载均衡概述二、轮询负载均衡器(一)理论介绍(二)Java 实现示例(三)关键步骤(四)流程图 三、随机负载均衡器(一&#x…...
大模型 LMDeploy 量化部署
1 模型部署 定义: 在软件工程中,部署通常指的是将开发完毕的软件投入使用的过程。在人工智能领域,模型部署是实现深度学习算法落地应用的关键步骤。简单来说,模型部署就是将训练好的深度学习模型在特定环境中运行的过程。 场景…...
算法设计5_分支限界法
分支限界法 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。 步骤: ① 定义解空间(对解编码); ② 确定解空间的树结构; ③ 按BFS等方式搜索: a.每个活…...
2025年人工智能专业可以考哪些证书呢?
人工智能是目前全球热门的专业领域之一,随着人工智能应用范围的不断扩大,越来越多的人开始关注人工智能相关证书的获取。那么,人工智能专业可以考什么证书呢?本文将为大家介绍人工智能相关证书的种类。 人工智能机器视觉应用工程师…...
仿真技术助力高尔夫球打破传统设计局限,实现球杆强大的功能
Altair近日宣布与业内领先的高尔夫装备制造商 Cleveland Golf 开展合作,以设计新款 HiBore XL 球杆。借助 Altair 先进的仿真与设计技术,Cleveland Golf 不断刷新高尔夫装备的行业标准,并在球杆产品设计方面实现突破。 Cleveland Golf 借助 A…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
