完全平方数(LeetCode-279)

简介: 完全平方数(LeetCode-279)

6. 完全平方数(LeetCode-279)


题目

给你一个整数 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 <= 104


思路

看到示例一的 4 + 4 + 4 4+4+44+4+4 知道是完全背包问题,本题求和为 n 的完全平方数的最少数量


五部曲


dp[j] 含义


和为 j的完全平方数的最少数量

递推公式


想一下,如果访问的当前物品是完全平方数,那么就分别求装它和不装它的数量,二者取小值。如果不是完全平方数,那么还是取不装它的数量

d p [ j ] = m i n ( d p [ j ] , d p [ j − i ] + 1 )

数组初始化


和为 0的完全平方数的最少数量肯定为零,而其他要初始化为最大值

遍历顺序


这里求最少数量,是组合数还是排列数都无所谓,所以顺序随意


代码展示

class Solution
{
public:
    int numSquares(int n)
    {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            bool flag = false;
            if (i == 1)
            {
                flag = true;
            }
            for (int k = 0; k < i; k++)
            {
                if (k * k == i)
                {
                    flag = true;
                    break;
                }
            }
            for (int j = i; j <= n; j++)
            {
                if (flag && dp[j - i] != INT_MAX)
                {
                    dp[j] = min(dp[j], dp[j - i] + 1);
                }
            }
        }
        return dp[n];
    }
};


分析一下,很快写出来了。但时间复杂度过于之高。那肯定是求完全平方数没有处理好。看了下题解,是我的物品选错了,我是遍历数然后判断它是不是完全平方数,但这样做就烦了。数值 n什么时候完全平方数?说白了 n是整数。那我的物品就取 n

class Solution
{
public:
    int numSquares(int n)
    {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
};
目录
相关文章
|
1月前
|
缓存 自然语言处理 JavaScript
Github 3k+ star,中后台管理系统框架,支持多款 UI 组件库,兼容PC、移动端!比商业系统还专业!!
Fantastic-admin/basic 是基于 Vue3 与 TypeScript 的中后台管理系统框架,支持多款 UI 组件库,如 Element Plus、Arco Design、Naive-UI 等。它提供完整的项目结构、权限控制、国际化、多级缓存标签页等功能,兼容 PC、平板及移动端,适合快速搭建企业级后台应用。框架具备高度可定制性,拥有 3k+ GitHub Star,生态完善,适合中小团队和个人开发者提升效率。
104 2
|
2月前
|
Kubernetes Linux 网络安全
Rocky Linux 8.9配置Kubernetes集群详解,适用于CentOS环境
初始化成功后,记录下显示的 `kubeadm join`命令。
161 0
|
算法 测试技术 vr&ar
☆打卡算法☆LeetCode 152. 乘积最大子数组 算法解析
☆打卡算法☆LeetCode 152. 乘积最大子数组 算法解析
|
4月前
|
自然语言处理 IDE 开发工具
5分钟完成手势识别项目!CodeBuddy的Craft模式让传统编程方法沦为古董?
本文介绍了使用CodeBuddy快速开发手势识别程序的方法。首先安装Python 3.9.13并配置VS Code环境,接着通过pip安装依赖库`mediapipe`和`opencv-python`。利用CodeBuddy的Craft模式,仅需输入自然语言描述即可生成基础代码,经过简单调整后即可运行。代码实现了四种手势识别(OK、竖大拇指、握拳、张开手掌),并通过摄像头实时展示结果。尽管电脑摄像头像素较低,但识别效果良好。本文旨在帮助读者了解CodeBuddy的强大功能,并激发更多创意应用。
344 20
|
监控 安全 JavaScript
浅谈移动端设备标识码:DeviceID、IMEI、IDFA、UDID和UUID
场景 : 客户提出一个问题就是把用户的登录记录和设备绑定到一起,就是每个人都是固定的设备(可能是安全因素吧)。一开始想的是回去设备的IMEI号和用户账号绑定起来,结果发现IMEI不对外开发,只能另寻他法,最后通过获取设备序列号作为唯一标识。
浅谈移动端设备标识码:DeviceID、IMEI、IDFA、UDID和UUID
|
JavaScript 前端开发 开发工具
使用vue3+element-ui plus 快速构建后台管理模板
本文介绍了如何使用Vue 3和Element UI Plus快速构建后台管理模板的步骤,包括安装Vue 3脚手架、Element UI Plus以及如何全局配置Element UI Plus。然后详细讲解了如何使用Element UI Plus构建布局,包括Header组件、Aside组件和HomeView视图的创建和样式调整,以及App.vue和main.css的修改,最后提供了项目的文件结构图和效果展示。
使用vue3+element-ui plus 快速构建后台管理模板
|
消息中间件 存储 资源调度
订单超时怎么处理?我们用这种方案
在电商业务下,许多订单超时场景都在24小时以上,对于超时精度没有那么敏感,并且有海量订单需要批处理,推荐使用基于定时任务的跑批解决方案。
2210 122
订单超时怎么处理?我们用这种方案
|
弹性计算 大数据 测试技术
阿里服务器租用多少钱一年?阿里云服务器租用价格表(最新CPU/内存/带宽/磁盘收费标准)
阿里服务器租用多少钱一年?阿里云服务器租用价格表(最新CPU/内存/带宽/磁盘收费标准)。阿里云服务器的租用费用因实例类型、地域、配置等因素而有所不同,价格范围可以从几百元到几千元不等。2024年阿里云服务器租用费用价格表更新,云服务器ECS经济型e实例2核2G、3M固定带宽99元一年、ECS u1实例2核4G、5M固定带宽、80G ESSD Entry盘优惠价格199元一年,轻量应用服务器2核2G3M带宽轻量服务器一年61元、2核4G4M带宽轻量服务器一年165元12个月、2核4G服务器30元3个月,幻兽帕鲁4核16G和8核32G服务器配置,云服务器ECS可以选择经济型e实例、通用算力u1实
|
人工智能 架构师 Cloud Native
架构愿景: 构建良好软件的关键
架构愿景: 构建良好软件的关键
284 0
|
机器学习/深度学习 资源调度 算法
推荐系统[四]:精排-详解排序算法LTR (Learning to Rank)_ poitwise, pairwise, listwise相关评价指标,超详细知识指南。
推荐系统[四]:精排-详解排序算法LTR (Learning to Rank)_ poitwise, pairwise, listwise相关评价指标,超详细知识指南。
推荐系统[四]:精排-详解排序算法LTR (Learning to Rank)_ poitwise, pairwise, listwise相关评价指标,超详细知识指南。