LeetCode 279 —— 完全平方数

news/2024/7/14 17:54:20/文章来源:https://blog.csdn.net/seniusen/article/details/139101897

阅读目录

    • 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[nsquareNums[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 jjdp 占用空间为 O ( n ) O(n) O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052365.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

操作教程|通过DataEase开源BI工具对接金山多维表格

前言 金山多维表格是企业数据处理分析经常会用到的一款数据表格工具&#xff0c;它能够将企业数据以统一的列格式整齐地汇总至其中。DataEase开源数据可视化分析工具可以与金山多维表格对接&#xff0c;方便企业更加快捷地以金山多维表格为数据源&#xff0c;制作出可以实时更…

k8s pv 一直是release状态

如下图所示&#xff0c;pv 一直是release状态 这个时候大家可能就会想到现在我的 PVC 被删除了&#xff0c;PV 也变成了 Released 状态&#xff0c;那么我重建之前的 PVC 他们不就可以重新绑定了&#xff0c;事实并不会&#xff0c;PVC 只能和 Available 状态的 PV 进行绑定。…

ssm137基于SSM框架的微博系统+vue

微博系统网站的设计与实现 摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就…

保安维稳,四信以科技构筑高速公路安全智慧防线

近日&#xff0c;广东梅大高速发生严重塌方事故&#xff0c;造成了严重的人员伤亡和财产损失。这一事件在公众心中敲响了安全的警钟&#xff0c;再次引起了公众对于交通设施运营安全性的重点关注。 国务院安委会办公室和国家防灾减灾救灾委员会办公室等主管机构先后印发紧急通知…

make disclean V=1 分析

文章目录 make distclean步骤1&#xff1a;2090-2114行&#xff0c;执行依赖 clean步骤2&#xff1a;2120-2124行&#xff0c;执行依赖 $(mrproper-dirs)步骤3&#xff1a;2118-2129行&#xff0c;执行依赖 mrproper步骤4&#xff1a;2135-2142行&#xff0c;实现 distclean 编…

flutter 的webview中touchstart和touchend 执行异常问题解决

效果 背景 使用flutter 调用webview内网页&#xff0c;网页内容是监听touchstart和 touchend&#xff0c;触发不同是事件&#xff0c;但是发现每次长按都 手指抬起后 才会执行 touchstart和touchend&#xff0c;满足不了我的需求&#xff0c;我的需求是当手指按下 立即执行touc…

大模型时代的具身智能系列专题(三)

清华高阳团队 高阳为清华叉院助理教授&#xff0c;本科毕业于清华大学计算机系&#xff0c;博士毕业于UC Berkeley。博士导师是Vision领域的大牛Trevor Darrell&#xff0c;读博期间和Sergey Levine合作开始强化学习方面的探索&#xff0c;博后跟随Pieter Abbeel做强化学习&am…

Windows下mingw32编译ffmpeg5.1.4实现rtsp拉流

由于客户要求&#xff0c;要在Windows下使用mingw32编译&#xff0c;去ffmpeg.org下载需要编译的版本&#xff0c;使用msys2方法进行编译&#xff0c;使用QT5.10的编译器&#xff0c;基本上把网上的方法试了个遍&#xff0c;编译全部库总是报错出问题 查看了ffbuild文件夹中con…

【全开源】JAVA情侣扭蛋机情侣游戏系统源码支持微信小程序+微信公众号+H5

一、引言&#xff1a;增添恋爱甜蜜&#xff0c;扭出惊喜时刻 在恋爱生活中&#xff0c;总是需要一些小小的惊喜和乐趣来增添甜蜜。为此&#xff0c;我们精心打造了“情侣扭蛋机情侣游戏系统小程序源码”&#xff0c;为情侣们提供一个充满趣味和创意的互动平台。 二、独特扭蛋…

C++的第一道门坎:类与对象(一)

1.面向过程与面向对象 1.1面向过程 我们之前学习的C语言就是一种面向过程的语言&#xff0c;面向过程的语言强调的是具体实现的过程&#xff0c;一般用函数来具体实现。我们用面向过程的思想&#xff0c;就可以把炒菜分为以下几个步骤: 1.2面向对象 而对于面向对象的语言而言…

【ARMv8/v9 异常模型入门及渐进 10 -- WFI 与 WFE 使用详细介绍 1】

请阅读【ARMv8/v9 ARM64 System Exception】 文章目录 WFI 与 WFE等待事件&#xff08;WFE&#xff09;发送事件&#xff08;SEV&#xff09;本地发送事件&#xff08;SEVL&#xff09;WFE 唤醒事件 WFE 使用场景举例与代码实现wfe睡眠函数sev 事件唤醒函数全局监视器和自旋锁 …

如何异地组网添加摄像机?

本文将介绍如何使用天联技术实现异地组网添加摄像机&#xff0c;并保障数据的安全性。 安防摄像机的应用愈发广泛&#xff0c;无论是家庭安防还是企业监控&#xff0c;摄像机都扮演着重要角色。在一些特殊场合或者特殊需求下&#xff0c;我们需要将摄像机添加到异地网络中进行监…

uniapp android使用uni.chooseLocation,app云打包后,定位地址列表一直在加载中

复现BUG 1、自己生成一个证书 参考生成证书流程 2、使用刚生成证书的SHA1 &#xff0c;重新创建一个高德key 高德开放平台地址 3、打包&#xff08;打包的包名要与高德申请key所填的包名一致&#xff09;

Java面试八股之Synchronized锁升级的原理

Synchronized锁升级的原理 Synchronized锁升级是Java为了提高并发性能而引入的一项优化措施&#xff0c;这一机制主要发生在JDK 1.6及之后的版本中。Synchronized锁升级旨在减少锁带来的性能开销&#xff0c;通过从低开销的锁逐步升级到高开销的锁&#xff0c;以适应不同的竞争…

从零入门激光SLAM(二十一)——FAST-LIO2论文解析

FAST-LIO2: Fast Direct LiDAR-Inertial Odometry 论文地址&#xff1a;https://ieeexplore.ieee.org/stamp/stamp.jsp?tp&arnumber9697912 代码&#xff1a;https://github.com/hku-mars/FAST_LIO 一、文章概述 1.问题导向 基于视觉传感器的高分辨率和高精度的实时密…

Docker笔记-搭建达梦Python环境(dmPython + SQLAlchemy)

背景 达梦提供的C接口&#xff0c;dpi和java的jar包已经很好用了&#xff0c;想不到&#xff0c;来了一个用python的同事&#xff0c;这里就只能适应下他了&#xff0c;在不影响其他环境下搭建一个python的达梦环境。最后发现&#xff0c;python对进行达梦增删改查&#xff0c…

【设计模式】JAVA Design Patterns——Bytecode(字节码模式)

&#x1f50d;目的 允许编码行为作为虚拟机的指令 &#x1f50d;解释 真实世界例子 一个团队正在开发一款新的巫师对战游戏。巫师的行为需要经过精心的调整和上百次的游玩测试。每次当游戏设计师想改变巫师行为时都让程序员去修改代码这是不妥的&#xff0c;所以巫师行为以数据…

1 计算机硬件-CPU-校验码-存储系统-输入输出设备-总线结构

计算机硬件 考情分析&#xff1a;趋势很小&#xff0c;22年考过&#xff0c;根据趋势以后考的可能较小 基本组成&#xff1a;运算器&#xff0c;控制器&#xff0c;储存器&#xff0c;输入设备&#xff0c;输出设备运算器和控制器也统称为中央处理单元&#xff08;CPU&#xf…

视频截图软件,这几款截图神器收好!

在数字化时代&#xff0c;视频内容已经成为我们获取信息、娱乐休闲的主要方式之一。而在观看视频的过程中&#xff0c;我们总会遇到一些想要定格下来的精彩瞬间。此时&#xff0c;一款高效的视频截图软件就显得尤为重要。今天&#xff0c;就为大家推荐几款功能强大、操作简便的…

2024年5月软考,别再傻傻啃书了!

备考2024年软考&#xff0c;不听课也不刷题&#xff0c;只是看教材的话&#xff0c;想要考试通过&#xff0c;几乎是不可能的&#xff0c;特别是基础比较薄弱的考生。 为什么只看教材通不过&#xff1f; 如果只是把教材从头到尾看一遍&#xff0c;毫无目的地看书&#xff0c;…