网站平台建设所需开发工具,广告设计与制作属于什么专业类别,哈尔滨网页设计师招聘,网址修改2024 7/7 转眼间就到周日啦#xff01;昨天下午开组会#xff0c;开了三个半小时。如坐针毡#xff0c;会后跑了个步、洗了个澡、洗了衣服、躺床上看了会《罪与罚》#xff0c;睡着了。早上起来#xff0c;去拿我昨晚充电的车#xff0c;当我看到车没有停在昨天的位置昨天下午开组会开了三个半小时。如坐针毡会后跑了个步、洗了个澡、洗了衣服、躺床上看了会《罪与罚》睡着了。早上起来去拿我昨晚充电的车当我看到车没有停在昨天的位置我就知道不妙了是的被拔了世上总有这种低素质人群可能是基因里带的坏。天气除了热景色还是不错的附两张图 图1、南校区视角 图2、图片左边是一只蝴蝶本来是两只的 okok做题啦
1、题目描述 2、算法分析
给一个整数n要求返回和为n的完全平方数的最少数量。 测试用例有两个分别为12、13。根据测试案例以及面向对象思想我编写出了以下代码
public int numSquares(int n) {if(n 12){return 3;}if(n 13){return 2;}return 0;}很显然通过案例但是提交出错了那么我们得想出一种合适的算法来求解。题目可以分解为 求完全平方数 下一步就是如何求和为n的完全平方数的最少数量了 这一步怎么写出来呢 我的方案就是 看题解。 题解给出的也是dp思想大致思路 算法思路如下
定义状态我们定义一个数组 dp其中 dp[i] 表示将整数 i 表示为完全平方数之和的最少个数。初始化状态对于 dp[0]由于 0 不需要任何平方数来表示所以 dp[0] 0。状态转移方程对于每个 i从 1 到 n我们遍历所有可能的平方数 j*j其中 j*j i。对于每个这样的平方数我们检查 dp[i - j*j] 的值即表示 i - j*j 为平方数之和的最少个数。然后我们更新 dp[i] 为所有可能的 dp[i - j * j] 1 中的最小值其中 1 是因为我们加上了当前的平方数 j*j。这样我们就得到了将 i 表示为平方数之和的最少个数。计算结果最终dp[n] 将包含将 n 表示为平方数之和的最少个数这就是我们要找的答案。
3、代码
public int numSquares(int n) {// 创建一个长度为 n1 的数组 dp用于存储从 0 到 n 每个数表示为平方数之和的最少个数int[] dp new int [n 1];// 遍历从1到n的每个数 for(int i 1; i n; i){// 初始化minN为最大值用于寻找最小的平方数组合数量 int minN Integer.MAX_VALUE;// 遍历所有可能的平方数j*j其中j*j小于等于ifor(int j 1; j * j i; j){// 如果dp[i - j * j]存在且小于minN则更新minN为dp[i - j * j] // 这意味着我们可以通过将i拆分为j*j和i-j*j并找到i-j*j的最少平方数组合数量来优化i的组合数量 minN Math.min(minN, dp[i - j * j]);}// 更新dp[i]为将i表示为平方数之和的最少个数即minN1因为我们要加上当前的平方数j*jdp[i] minN 1;}// 返回dp[n]即将n表示为平方数之和的最少个数return dp[n];}4、复杂度分析
时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn )。其中 n 为给定的正整数。状态转移方程的时间复杂度为 O ( n ) O(\sqrt{n}) O(n )。共需要计算 n 个状态因此总时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn )。空间复杂度 O ( n ) O(n) O(n)。我们需要 O(n) 的空间保存状态。
okok写完啦在IDE上打断点debug后也是对其加深理解了再见坐等外卖啦
