java数据结构与算法刷题-----LeetCode279. 完全平方数

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

    • 动态规划
    • 四平方和定理

在这里插入图片描述

动态规划

解题思路:时间复杂度O( n ∗ n n*\sqrt{n} nn ),空间复杂度O( n n n)
  1. DP数组及下标含义
  1. 我们要求出的是从1到n,每个数字所需的最少完全平方数。显然dp数组中存储的就是当前下标i的最少所需完全平方数。要求出谁的?显然是求出i的。那么下标就是代表求谁的,很显然,只需要一个下标,也就是一维数组。
  1. 递推公式
  1. 假设我们求出了4的最少所需完全平方数为1,也就是4本身为一个完全平方数。则dp[4]=1
  2. 此时我们要求8的最少所需完全平方数,我们可以选择的完全平方数有1和4,因为下一个完全平方数是9,9>8了,显然9往后的完全平方数都不满足条件。
  3. 显然我们不能选择1作为8需要的平方数的其中之一,因为它太小了,我们要让数量尽可能少
  4. 则我们选择4,选择一个4之后,8 - 4 = 4.也就是我们还剩下4需要找完全平方数。此时我们访问dp[4] = 1,发现4这个数字最少需要1个完全平方数。
  5. 因此8这个数,当我们第一个数选择4时,剩下的就直接访问dp[8 - 4] = dp[4] = 1即可。也就是一共需要2个完全平方数。dp[8] = 2.
  6. 综上所述,递推公式为dp[i] = min(dp[i - j 2 j^2 j2])+1, 其中j的取值范围为[1, j \sqrt{j} j ]

j 2 j^2 j2是完全平方数, i − j 2 i - j^2 ij2表示第一个数选择 j 2 j^2 j2,通过dp[ i − j 2 i - j^2 ij2]获取减去第一个数字后,剩余的数所需最少完全平方数
min(dp[i - j 2 j^2 j2])的含义就是,不断尝试不同的完全平方数作为第一个,并获取剩余数字所需最少完全平方数,找到所需数字最少的一个方案。
当剩余数字 i − j 2 i-j^2 ij2最少方案找到后,+1即可,因为我们前面减去了 j 2 j^2 j2,现在需要将 j 2 j^2 j2这个数字算上一个

  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序(单重循环,无需考虑遍历顺序,一共就一维,哪里来的谁先谁后)
  2. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

在这里插入图片描述

代码

在这里插入图片描述

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];//dp数组,代表和为i的完全平方数最少数量。下标i表示求谁的所需完全平方数最少数量
        for (int i = 1; i <= n; i++) {//1到n开始规划每个数字的完全平方数最少数量
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {//j表示完全平方数,从1开始,1,4,9,16....,但是不能>i
                //是否选择当前完全平方数。如果选择当前完全平方数,则i - 当前完全平方数,看看剩余数字的所需完全平方数数量
                //如果选择当前完全平方数所需数量更少(更优),就令minn = f[i - j*j],否则不选择当前数。minn不变
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;//当前数字所需的最少完全平方数数量。
        }
        return f[n];//返回n的最少所需完全平方数数量
    }
}

四平方和定理

  1. 四平方和定理:任意正整数x,可被最多4个正整数的平方和(完全平方数)表示。
  2. 结论一:当 n = 4 k ∗ ( 8 ∗ m + 7 ) n = 4^k * (8*m + 7) n=4k(8m+7)时,n只能被4个正整数的平方和表示。

这是一个判断条件,k和m表示随便一个数,只要n能满足即可。可以说只要 n 满足 4 k ∗ ( 8 ∗ m + 7 ) n 满足 4^k * (8*m + 7) n满足4k(8m+7)这样的条件,n就只能被4个正整数平方和表示

  1. 结论二:当前仅当 n ≠ 4 k ∗ ( 8 ∗ m + 7 ) n \not = 4^k * (8*m + 7) n=4k(8m+7)时,n才可以被3个及以下(至多3个)正整数平方和表示
解题思路:时间复杂度O( n \sqrt{n} n ),空间复杂度O( 1 1 1)
  1. n = 4 k ∗ ( 8 ∗ m + 7 ) n = 4^k * (8*m + 7) n=4k(8m+7)时,直接返回4,因为满足这个条件的正整数只能被4个完全平方数表示
  2. n ≠ 4 k ∗ ( 8 ∗ m + 7 ) n \not = 4^k * (8*m + 7) n=4k(8m+7)时,则需要额外处理,因为它表示n可能被1个或2个或3个完全平方数表示。
  1. 若当前n正好是完全平方数,则答案为1,也就是它本身表示自己
  2. 若n不是完全平方数,枚举两个完全平方数,查看是否可以组成n,也就是 n = a 2 + b 2 n = a^2 + b^2 n=a2+b2.枚举需要时间复杂度为O( n \sqrt{n} n )

因为需要枚举一个完全平方数a,a属于[1, n \sqrt{n} n ], 并判断 n − a 2 n - a^2 na2是否是完全平方数

  1. 以上两个条件都不满足,则需要3个完全平方数表示,返回3即可
代码

在这里插入图片描述

class Solution {
    // 判断是否为完全平方数,如果是完全平方数,则只需1个完全平方数(它本身)即可表示
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }
    // 判断是否能表示为 4^k*(8m+7)
    public boolean checkAnswer4(int x) {
        while (x % 4 == 0) x /= 4;//不断除以4,相当于不断进行4^(k-1)操作,直到k归0
        //此时剩余(8m+7),我们取余8,则剩下的数字为不可以被8取余的数
        //如果剩下的数字正好是7,这返回true,否则返回false
        return x % 8 == 7;
    }
    public int numSquares(int n) {
        if (isPerfectSquare(n)) return 1;//如果n是完全平方数,返回1
        if (checkAnswer4(n)) return 4;//满足n = 4^k * (8*m + 7),则只能由4个完全平方数表示
        //不满足n = 4^k * (8*m + 7),并且n本身不是完全平方数,则只能由2个或者3个完全平方数表示
        //先试图用2个完全平方数表示n,如果成功,返回2
        for (int i = 1; i * i <= n; i++) {
            //选择i*i作为当前完全平方数的其中之一,
            int j = n - i * i;//则减去这个完全平方数,剩下的数字为n - i * i
            if (isPerfectSquare(j)) return 2;//如果剩下的数字也是完全平方数,则可以由2个数字表示
        }
        //无法用2个完全平方数表示,返回3
        return 3;
    }

    

    
}

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

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

相关文章

图像处理_积分图

目录 1. 积分图算法介绍 2. 基本原理 2.1 构建积分图 2.2 使用积分图 3. 举个例子 1. 积分图算法介绍 积分图算法是图像处理中的经典算法之一&#xff0c;由Crow在1984年首次提出&#xff0c;它是为了在多尺度透视投影中提高渲染速度。 积分图算法是一种快速计算图像区域和…

LeetCode-56. 合并区间【数组 排序】

LeetCode-56. 合并区间【数组 排序】 题目描述&#xff1a;解题思路一&#xff1a;排序&#xff1f;怎么排&#xff1f;当然是排各个区间的左边界&#xff0c;然后判断下一个边界的左边界与结果数组里面的右边界是否重叠。解题思路二&#xff1a;优化解题思路三&#xff1a;0 题…

Linux: 进程优先级

Linux: 进程优先级 一、进程优先级概念二、如何查看进程优先级三、如何修改进程的优先级&#xff08;PRL vs NI&#xff09;四、为何优先级PRL必须限定范围五、进程其他特性 一、进程优先级概念 优先级的本质就是排队&#xff0c;而排队则是资源不足所引起的。在计算机中&#…

《Lost in the Middle: How Language Models Use Long Contexts》AI 解读

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…

【JavaScript 漫游】【049】ES6 规范中对象的扩展

文章简介 本篇文章为【JavaScript 漫游】专栏的第 049 篇文章&#xff0c;对 ES6 规范中对象的扩展知识点进行了记录。具体包括&#xff1a; 属性的简洁表示法属性名表达式方法的 name 属性属性的可枚举性和遍历super 关键字对象的扩展运算符链判断运算符Null 判断运算符新增…

MIT最新研究成果 机器人能够从错误中纠偏 无需编程介入和重复演示

目前科学家们正在努力让机器人变得更加智能&#xff0c;教会他们完成诸如擦拭桌面&#xff0c;端盘子等复杂技能。以往机器人要在非结构化环境执行这样的任务&#xff0c;需要依靠固定编程进行&#xff0c;缺乏场景通用性&#xff0c;而现在机器人的学习过程主要在于模仿&#…

ctf题目

目录 1.文件包含的一道题目&#xff0c;没什么难度&#xff0c; 2.一道sql注入的题目&#xff0c;伪静态 3.限制只能本地访问。 1.文件包含的一道题目&#xff0c;没什么难度&#xff0c; 但是一个点就是它这里去包含的那个文件名就是flag&#xff0c;而不是flag.php也不是f…

Linux之miniconda的安装和使用

一、miniconda简介 Miniconda和Anaconda都是由Continuum Analytics开发的Python发行版。二者的主要区别在于它们所自带的软件包集合的大小。Miniconda是一个免费的conda最低安装程序。它是Anaconda的一个小型引导程序版本&#xff0c;只包括conda、Python、它们都依赖的包&…

C++语言·入门

现在我们讲完了数据结构初阶部分的内容&#xff0c;数据结构剩下的内容会在C语言讲解的差不多的时候加入。 1. 什么是C C语言是结构化模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度抽象和建模时&#xff0c…

STM32学习笔记(10_1)- I2C通信协议

无人问津也好&#xff0c;技不如人也罢&#xff0c;都应静下心来&#xff0c;去做该做的事。 最近在学STM32&#xff0c;所以也开贴记录一下主要内容&#xff0c;省的过目即忘。视频教程为江科大&#xff08;改名江协科技&#xff09;&#xff0c;网站jiangxiekeji.com 本期开…

Linux基础命令篇之——压缩与解压(tar、gzip、bzip2、zip和unzip)

linux基础命令——解压与压缩 以下是关于Linux命令tar、gzip、bzip2、zip和unzip的详细介绍&#xff1a; 1. tar 这个是Linux用的最多的解压缩命令 tar是Linux系统中用于创建和处理归档文件的命令。归档文件是一个包含多个文件和/或目录的单一文件。常与压缩命令gzip或bzip2结…

【CANN训练营笔记】Atlas 200I DK A2体验手写数字识别模型训练推理

环境介绍 开发板&#xff1a;Huawei Atals 200I DK A2 内存&#xff1a;4G NPU&#xff1a;Ascend 310B4 CANN&#xff1a;7.0 准备环境 下载编译好的torch_npu wget https://obs-9be7.obs.cn-east-2.myhuaweicloud.com/wanzutao/torch_npu-2.1.0rc1-cp39-cp39-linux_aarch…

.NET CORE 分布式事务(四) CAP实现最终一致性

目录 引言&#xff1a; 1.0 最终一致性介绍 2.0 CAP 2.0 架构预览 3.0 .NET CORE 结合CAP实现最终一致性分布式事务 3.1 准备工作(数据库&#xff0c;本文使用的是MySql) 3.1.1 数据模型 3.1.2 DbContext 3.1.3 数据库最终生成 3.2 Nuget引入 3.3 appsettings.json …

【OS探秘】【虚拟化】【软件开发】VirtualBox 虚拟化软件卸载和重装

往期OS系列博文&#xff1a; 【OS探秘】【虚拟化】【软件开发】在Windows 11上安装mac OS虚拟机 【OS探秘】【虚拟化】【软件开发】在Windows 11上安装Kali Linux虚拟机 一、事出有因 近日&#xff0c;笔者的Oracle VM VirtualBox突然抽风了&#xff0c;虚拟机无法启动&…

深入理解MapReduce:从Map到Reduce的工作原理解析

当谈到分布式计算和大数据处理时&#xff0c;MapReduce是一个经典的范例。它是一种编程模型和处理框架&#xff0c;用于在大规模数据集上并行运行计算任务。MapReduce包含三个主要阶段&#xff1a;Map、Shuffle 和 Reduce。 ** Map 阶段 ** Map 阶段是 MapReduce 的第一步&am…

Linux appimage如何正确打开

在之前的文章中&#xff0c;提到使用appimage软件非常方便。 但是首次使用会遇到这样的问题&#xff1a; 1. 双击打不开 2. 在终端打开提示&#xff1a; /home/roy/software/appimage/Obsidian-1.5.11.AppImage dlopen(): error loading libfuse.so.2 AppImages require …

关系型数据库mysql(9)主从复制和读写分离

目录 1. 主从复制和读写分离 2. mysql 支持的复制类型 3.架构图 一.主从复制 1.主从复制的定义 2.主从复制的过程 中继日志&#xff08;Relay Log&#xff09;&#xff1a; 优点&#xff1a; 3.为什么要复制 4.谁复制谁 5.数据放在什么地方 6.主从复制出现的问题 …

基于Uni-app的体育场馆预约系统的设计与实现

文章目录 基于Uni-app的体育场馆预约系统的设计与实现1、前言介绍2、开发技术简介3、系统功能图3、功能实现4、库表设计5、关键代码6、源码获取7、 &#x1f389;写在最后 基于Uni-app的体育场馆预约系统的设计与实现 1、前言介绍 伴随着信息技术与互联网技术的不断发展&#…

服务器固定IP(固定出口IP)去访问外部服务

背景 服务器上有多个IP&#xff0c;那么在服务器请求外部服务的时候&#xff0c;到底是使用哪个IP呢&#xff1f;如果要使用特定的IP去请求外部服务&#xff0c;该如何设置呢&#xff1f; 分析 遇到一个实际的场景&#xff1a; 我们产品和其他产品联调&#xff0c;我们的服务…

软考历史题目

2023.3 1. 磁盘索引块1KB,每个地址项4字节&#xff0c;每个磁盘索引块可以存放256个物理块地址 2.5个地址项为直接索引地址&#xff0c;所以0-5逻辑块是直接索引 3.一级间接地址索引&#xff0c;每个指向的物理块存255个地址 4.二级间接地址&#xff1a;256个间接索引表地址…