LeetCode 279. 完全平方数 (C#实现)——动态规划,四平方和定理

Stella981
• 阅读 564

问题:https://leetcode-cn.com/problems/perfect-squares/

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

GitHub实现:https://github.com/JonathanZxxxx/LeetCode/blob/master/NumSquares.cs

Blog:https://www.cnblogs.com/zxxxx/

一、动态规划实现

1、思路:对一个数字n而言,组成的它的完全平方数的最少个数可以根据它减去i*i(这里i*i<n)后对应的那个数的最少完全平方数加一,通过改变i的值最终取得最小值

从简单情况开始
1   1>=1*1 所以1对应等于0对应的最小个数加1,这里0对应的个数为0
2   2>=1*1 所以2对应等于1对应的最小个个数加1,因为之前已经记录了1对应的最小值为1,所以这里最小为2
3   3>=1*1 所以3对应等于2对应的最小个个数加1,因为之前已经记录了2对应的最小值为1,所以这里最小为3
4   4>=1*1和4>=4 所以4对应等于3或者0对应的最小个个数加1,因为之前已经记录了3对应的最小值为3,0对应的最小值为0,所以最终的最小值为1。
往后的情况依次类推

参考:LeetCode-【动态规划】-完全平方数

public int NumSquares(int n)
        {
            int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                dp[i] = n;
            }
            for (int i = 1; i <= n; i++)
            {
                int j = 1;
                while (i - j * j >= 0)
                {
                    dp[i] = Math.Min(dp[i], dp[i - j * j] + 1);
                    j++;
                }
            }
            return dp[n];
        }

二、四平方和定理实现

1、思路:任何一个正整数都可以表示成不超过四个整数的平方之和;推论:满足四数平方和定理的数n(四个整数的情况),必定满足 n=4^a(8b+7)

LeetCode 279. 完全平方数 (C#实现)——动态规划,四平方和定理

参考:C#版[击败100%的提交] - Leetcode 279. 完全平方数 - 题解

public int NumSquares2(int n)
        {
            while (n % 4 == 0)
            {
                n /= 4;
            }
            if (n % 8 == 7)
            {
                return 4;
            }
            for (int i = 0; i * i <= n; i++)
            {
                int r = (int)Math.Sqrt(n - i * i);
                if (i * i + r * r == n)
                {
                    if (i == 0 || r == 0) return 1;
                    return 2;
                }
            }
            return 3;
        }
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
8个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这