LeetCode 279 —— 完全平方数
阅读目录
- 1. 题目
- 2. 解题思路
- 3. 代码实现
1. 题目

2. 解题思路
此图利用动态规划进行求解,首先,我们求出小于 n n n 的所有完全平方数,存放在数组 squareNums 中。
定义 dp[n] 为和为 n n n 的完全平方数的最小数量,那么有状态转移方程:
d p [ n ] = m i n ( d p [ n − s q u a r e N u m s [ i ] ] + 1 , d p [ n ] ) , 对于任意 s q u a r e N u m s [ i ] < n dp[n] = min(dp[n-squareNums[i]] + 1, dp[n]), 对于任意 \space squareNums[i] < n dp[n]=min(dp[n−squareNums[i]]+1,dp[n]),对于任意 squareNums[i]<n
d p [ n ] = 1 ,对于 s q u a r e N u m s [ i ] = = n dp[n] = 1,对于 \space squareNums[i] == n dp[n]=1,对于 squareNums[i]==n
3. 代码实现
class Solution {
public:int numSquares(int n) {vector<int> squareNums;for (int i = 1; i < n; ++i) {if (i * i > n) {break;}squareNums.push_back(i * i);}vector<int> dp(n+1, 10000);dp[1] = 1;for (int i = 2; i <= n; ++i) {for (int j = 0; j < squareNums.size(); ++j) {if (squareNums[j] > i) {break;} else if (squareNums[j] == i) {dp[i] = 1;} else {dp[i] = min(dp[i], dp[i - squareNums[j]] + 1);} }}return dp[n];}
};
时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn),第一层循环 n n n 次,第二层循环 n \sqrt{n} n 次,空间复杂度为 O ( n ) O(n) O(n),其中 squareNums 占用空间为 O ( n ) O(\sqrt{n}) O(n),也可以省略,直接在第二个循环得到 j ∗ j j*j j∗j,dp 占用空间为 O ( n ) O(n) O(n)。
相关文章:
LeetCode 279 —— 完全平方数
阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 此图利用动态规划进行求解,首先,我们求出小于 n n n 的所有完全平方数,存放在数组 squareNums 中。 定义 dp[n] 为和为 n n n 的完全平方数的最小数量,那么有状态…...
PHP发票真假API、医疗电子票据查验、发票识别接口开发示例
“营”“增”两种税是主流的流转税种,是两个独立而不能交叉的税种。也就是说交增值税的话就不交营业税,而交了营业税就不需要交增值税。而且,两者在征收的对象、征税范围、计税的依据、税目、税率以及征收管理等都有所不同,增值税…...
Python库之`lxml`的高级用法深度解析
Python库之lxml的高级用法深度解析 简介 lxml是一个功能强大的第三方库,它提供了对XML和HTML文档的高效处理能力。除了基本的解析和创建功能外,lxml还包含了一些高级用法,这些用法可以帮助开发者在处理复杂文档时更加得心应手。 高级解析技…...
参数的本质:详解 JavaScript 函数的参数
文章导读:AI 辅助学习前端,包含入门、进阶、高级部分前端系列内容,当前是 JavaScript 的部分,瑶琴会持续更新,适合零基础的朋友,已有前端工作经验的可以不看,也可以当作基础知识回顾。 上篇文章…...
悲痛都会过去,唯有当下值得珍惜
在生活的长河中,我们都会经历各种各样的悲痛与挫折,无论是来自原生家庭的困扰,婚姻中的曲折,还是小时候的创伤、男女关系中的纠葛、校园时期的霸凌。然而,当我们回首过去,曾经以为无法逾越的痛苦࿰…...
第三方软件测试机构进行代码审计需要哪些专业的知识?
代码审计 进行代码审计需要专业的知识,包括编程语言、操作系统、数据库、网络知识以及安全知识等。 1.编程语言知识是进行代码审计的基础,因为你需要理解代码的语法和结构。对于不同的应用程序,你需要了解其所使用的编程语言的特点和语法规…...
Modal.method() 不显示头部的问题
ant-design中的Modal组件有两种用法: 第一种是用标签:<a-modal></a-modal> 第二种是用Api:Modal.info、Modal.warning、Modal.confirm...... 一开始项目中这两种用法是混用的,后面UI改造,需要统一样式&…...
Java中的内部类及其用途
一、技术难点 在Java中,内部类是一个定义在另一个类内部的类。这种嵌套的结构带来了一些技术上的难点和挑战: 访问控制:内部类可以直接访问外部类的所有成员(包括私有成员),但外部类不能直接访问内部类的…...
堆(建堆算法,堆排序)
目录 一.什么是堆? 1.堆 2.堆的储存 二.堆结构的创建 1.头文件的声明: 2.向上调整 3.向下调整 4.源码: 三.建堆算法 1.向上建堆法 2.向下建堆法 四.堆排序 五.在文件中Top出最小的K个数 一.什么是堆? 1.堆 堆就…...
Linux内核重置root密码
Ubuntu 首先重新启动Ubuntu系统,然后快速按下shift键,以调出grub启动菜单在这里我们选择第二个(Ubuntu高级选项),选中后按下Enter键 选择最高的Linux内核版本所对应的recovery mode模式,按e键编辑启动项 在…...
LaTex安装及配置(Windows)
LaTex安装及配置(Windows) 安装环境安装texlive下载texlive安装 编辑器安装texstudio下载texstudio安装 环境配置 使用第一个LaTex文档新建文件编程查看results 安装 环境安装 texlive下载 镜像清华源下载地址:https://mirrors.tuna.tsing…...
这才是满分毕业答辩PPT!
这才是满分毕业答辩PPT! 2024年 毕业答辩论文指南 创新 正式 高效 正值毕业季,是不是很多同学,非常头疼如何进行论文答辩? 要想导师满意,顺利毕业,那么手里必须有份优秀的答辩PPT。这将是你的秘密武器&…...
【字典树(前缀树) 字符串】2416. 字符串的前缀分数和
本文涉及知识点 字典树(前缀树) 字符串 LeetCode 2416. 字符串的前缀分数和 给你一个长度为 n 的数组 words ,该数组由 非空 字符串组成。 定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。 例如,如果 words [“a”,…...
X-CSV-Reader:一个使用Rust实现CSV命令行读取器
🎈效果演示 ⚡️快速上手 依赖导入: cargo add csv读取实现: use std::error::Error; use std::fs::File; use std::path::Path;fn read_csv<P: AsRef<Path>>(filename: P) -> Result<(), Box<dyn Error>> {le…...
集成ECharts到若依框架:原理与使用方法详解
ECharts 是一个强大的开源数据可视化库,基于 JavaScript,能够创建丰富多彩的图表和交互数据展示。结合若依框架(RuoYi),我们可以非常方便地将 ECharts 集成到系统中,实现数据的可视化展示。本文将详细介绍 …...
【机器学习】——线性模型
💻博主现有专栏: C51单片机(STC89C516),c语言,c,离散数学,算法设计与分析,数据结构,Python,Java基础,MySQL,linux…...
最全的Redis常用命令
Redis是一个开源的内存数据结构存储系统,用作数据库、缓存和消息代理。它支持多种类型的数据结构,如字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)…...
sourcetree推送到git上面
官网:Sourcetree | Free Git GUI for Mac and Windows 下载到1次提交 下载后打开 点击跳过 下一步 名字邮箱 点击clone 把自己要上传的代码粘贴到里面去 返回点击远程->点击暂存所有 加载完毕后,输入提交内容提交 提交完成了 2次提交 把文件夹内的…...
勒索病毒的策略与建议
随着网络技术的快速发展,勒索病毒攻击成为全球范围内日益严重的网络安全威胁。勒索病毒通过加密用户文件或锁定系统来勒索赎金,给个人和企业带来了巨大的损失。因此,了解如何应对勒索病毒攻击至关重要。本文将概述一些有效的防范措施和应对策…...
doxygen 1.11.0 使用详解(十四)——输出格式
目录 HTMLLATEXMan pagesRTFXMLDocBookCompiled HTML Help (a.k.a. Windows 98 help)Qt Compressed Help (.qch)Eclipse HelpXCode DocSetsPostScriptPDF The following output formats are directly supported by doxygen: HTML Generated if GENERATE_HTML is set to YES i…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
