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…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
