【Hot100】LeetCode—279. 完全平方数

目录

  • 题目
  • 1- 思路
  • 2- 实现
    • ⭐完全平方数——题解思路
  • 3- ACM 实现


题目

  • 原题连接:279. 完全平方数

1- 思路

思路

  • 动规五部曲

2- 实现

⭐完全平方数——题解思路

在这里插入图片描述

class Solution {public int numSquares(int n) {// 1. 定义 dpint[] dp = new int[n+1];//2. 递推公式// dp[j] = Math.min(dp[j],dp[j-i*i]+1);//3. 初始化int max = Integer.MAX_VALUE;for(int i = 0 ; i < dp.length;i++){dp[i] = max;}dp[0] = 0;for(int i = 1 ; i*i <= n;i++){for(int j = i*i ; j<=n ; j++){dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n];}
}

3- ACM 实现

public class squareNum {public static int numSquares(int n){int[] dp = new int[n+1];// 2. 递推公式// dp[j] = Math.min(j-i*i+1,dp[j]);// 3.初始化int MAX = Integer.MAX_VALUE;for (int i = 0 ; i <= n;i++){dp[i] = MAX;}dp[0] = 0;//4. 先遍历 物品 后遍历背包for(int i = 1; i*i <= n;i++){for(int j = i*i ; j <= n;j++){dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入要求的完全平方数和");int n = sc.nextInt();System.out.println("结果是"+numSquares(n));}
}

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

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

相关文章

pytest-fixture

资料来源&#xff1a;虫师2020的个人空间-虫师2020个人主页-哔哩哔哩视频 支持类似unittest风格的fixture&#xff0c;即setup和teardown class类中的方法分类 类方法可以直接调用&#xff0c;需要添加装饰器&#xff0c;修改类中的变量 实例方法&#xff0c;需要先实例化&…

达梦数据库系列—29. DTS迁移ORACLE到DM

目录 1.ORACLE源端信息 2.DM目的端信息 3.DTS 迁移评估 4.数据库迁移 4.1 Oracle 源端数据库准备 4.2 目的端达梦数据库准备 初始化参数设置 兼容性参数设置 表空间规划 用户规划 创建迁移用户和表空间 4.3迁移步骤 创建迁移 配置数据源 配置迁移对象及策略 开…

TCP客户端connect断线重连

文章目录 TCP客户端connect断线重连1、为什么要断线重连2、实现代码 TCP客户端connect断线重连 1、为什么要断线重连 客户端会面临服务器崩溃的情况&#xff0c;我们可以试着写一个客户端重连的代码&#xff0c;模拟并理解一些客户端行为&#xff0c;比如游戏客户端等. 考虑到…

【Git】merge合并分支

两个分支未修改同一个文件的同一处位置: Git自动合并 两个分支修改了同一个文件的同一处位置:产生冲突 例&#xff1a; 在master分支修改了main同时&#xff0c;feat分支也修改了相同的文件 合并的时候就会产生冲突 解决方法: Step1- 手工修改冲突文件&#xff0c;合并冲突内容…

go语言day15 goroutine

Golang-100-Days/Day16-20(Go语言基础进阶)/day17_Go语言并发Goroutine.md at master rubyhan1314/Golang-100-Days GitHub 第2讲-调度器的由来和分析_哔哩哔哩_bilibili 一个进程最多可以创建多少个线程&#xff1f;-CSDN博客 引入协程 go语言中内置了协程goroutine&#…

星环科技携手东华软件推出一表通报送联合解决方案

随着国家金融监督管理总局“一表通”试点工作的持续推进&#xff0c;星环科技携手东华软件推出了基于星环科技分布式分析型数据库ArgoDB和大数据基础平台TDH的一表通报送联合解决方案&#xff0c;并已在多地实施落地中得到充分验证。 星环科技与东华软件作为战略合作伙伴&…

论文阅读【检测】:Facebook ECCV2020 | DETR

文章目录 论文地址AbstractMotivation模型框架详细结构小结 论文地址 DETR Abstract 提出了一种将目标检测视为直接集预测问题的新方法。简化了检测pipeline&#xff0c;有效地消除了许多手工设计的组件的需求&#xff0c;例如非最大抑制过程或锚生成&#xff0c;这些组件明…

802.11无线网络权威指南(二):无线帧结构

802.11无线网络权威指南&#xff08;二&#xff09;&#xff1a;无线帧结构 无线协议桢的三种类型无线网络帧结构完整帧格式control frameDuration/IDAddressSequence ControlQoS ControlHT Control 字段Frame Body 帧体FCS 校验域 帧细节管理帧控制帧RTS 帧CTS 帧ACK 帧格式PS…

ceph log内容解析

log内容构造 如osd的一条log 分别表示 时间戳 线程id 日志等级 子模块 内容实体 剖析源码实现 每条log都是由一个Entry构成 定义在src/log/entry.h中 Entry(short pr, short sub) :m_stamp(clock().now()), // 打印日志时的时间戳m_thread(pthread_self()), // 打印日志的线…

redis的持久化方式

目录 1. 什么是持久化&#xff1f; 2. redis实现持久化的方式 2.1 什么是RDB&#xff1f; 2.2 什么时候会触发RDB模式&#xff1f; 2.2.1 手动触发 2.2.2 自动触发 2.3 什么是Aof&#xff1f; 2.3.1 开启Aof 2.4 RBD和AOF的区别 1. 什么是持久化&#xff1f; 把内存中…

el-table列的显示与隐藏

需求&#xff1a;实现 表字段的显示与隐藏。效果图 代码实现 写在前面 首先 我部分字段有自定义的排序逻辑&#xff0c;和默认值或者 数据的计算 所以是不能简单的使用 v-for 循环column 。然后 我需要默认展示一部分字段&#xff0c;并且 当表无数据时 提示不能 显示隐藏 …

AIGC Kolors可图IP-Adapter-Plus风格参考模型使用案例

参考: https://huggingface.co/Kwai-Kolors/Kolors-IP-Adapter-Plus 代码环境安装: git clone https://github.com/Kwai-Kolors/Kolors cd Kolors conda create --name kolors python=3.8 conda activate kolors pip install -r requirements.txt python3 setup.py install…

mybatis一对多 多对多

一对一 方式一: ,在result的property属性用user.XXX 方式二:把user对象的属性用resultMap标签包含在association标签里,user的id做id标签,特点是返回值是对象的标识,而集合是collection 一对多 在user类加了个订单的集合,表示一个用户有多个订单 这接口当然是user的 分为re…

PWM信号转模拟信号转换器GP8101/GP8101M

前言&#xff1a; 各位大佬&#xff0c;听说过PAC吗&#xff1f;PAC (PWM to Analog Converter)。 今天介绍一个小众的转换芯片&#xff0c;PWM转模拟信号的&#xff0c;有一定的应用场景,单价一元多。这种芯片隔离PWM还是很容易的。 0%-100% PWM to 0-5V/0-10V SOP8封装的GP…

HarmonyOS三方库的使用

系统组件难以提供比较优秀的界面&#xff0c;需要第三方库来实现一些比较好看的界面效果 三方库的获取&#xff1a; 开源社区支持OpenHarmony-TPC 和 Openharmony三方库中心仓 先目前已经拥有各种各样的三方库&#xff0c;包括UI 图片 动画 网络 数据存储 工具类 多媒体 安全等…

redis数据类型介绍

Redis 支持多种数据类型&#xff0c;包括&#xff1a; 1.字符串&#xff08;String&#xff09;&#xff1a;最简单的数据类型&#xff0c;可以存储字符串、数字等。 2.哈希&#xff08;Hash&#xff09;&#xff1a;类似于 Map&#xff0c;可以存储键值对&#xff0c;其中键值…

Go语言编程 学习笔记整理 第2章 顺序编程 后半部分

1.流程控制 1.1 条件语句 if a < 5 { return 0 } else { return 1 } 注意&#xff1a;在有返回值的函数中&#xff0c;不允许将“最终的”return语句包含在if...else...结构中&#xff0c; 否则会编译失败&#xff01;&#xff01;&#xff01; func example(x int) i…

leetcode 2236.判断根节点是否等于字节点

1.题目要求: 给你一个 二叉树 的根结点 root&#xff0c;该二叉树由恰好 3 个结点组成&#xff1a;根结点、左子结点和右子结点。如果根结点值等于两个子结点值之和&#xff0c;返回 true &#xff0c;否则返回 false 。2.思路: 直接数组前序遍历&#xff0c;然后判断后面两个…

【C++】:红黑树深度剖析 --- 手撕红黑树!

目录 前言一&#xff0c;红黑树的概念二&#xff0c;红黑树的性质三&#xff0c;红黑树节点的定义四&#xff0c;红黑树的插入操作4.1 第一步4.2 第二步4.3 插入操作的完整代码 五&#xff0c;红黑树的验证六&#xff0c;实现红黑树的完整代码五&#xff0c;红黑树与AVL树的比较…

【接口自动化_08课_Pytest+Yaml+Allure框架】

上节课一些内容 的补充 1、openxl这个方法&#xff0c;第一个元素是从1开始的&#xff0c;不是从0开始 回写的列在程序里写的是11&#xff0c;是因为是固定值 一、1. Yaml入门及应用 1、什么是yaml YAML&#xff08;/ˈjməl/&#xff0c;尾音类似camel骆驼&#xff09;是一…