力扣hot100 完全平方数 完全背包 滚动数组 四平方和定理

这篇具有很好参考价值的文章主要介绍了力扣hot100 完全平方数 完全背包 滚动数组 四平方和定理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem: 279. 完全平方数
力扣hot100 完全平方数 完全背包 滚动数组 四平方和定理,力扣 hot100,leetcode,算法,职场和发展

思路

👨‍🏫 三叶神解

👨‍🏫 数学解法

💖 完全背包

⏰ 时间复杂度: O ( n 2 n ) O(n^2 \sqrt{n}) O(n2n )

class Solution {
    int INF = 0x3f3f3f3f;
	public int numSquares(int n)
	{
		List<Integer> list = new ArrayList<>();
		int t = 1;
		while (t * t <= n)
		{
			list.add(t * t);
			t++;
		}
		int m = list.size();
		int[][] f = new int[m + 1][n + 1];// f[i][j] 表示考虑前 i 个物品,凑出 j 所使用的最小元素个数
		Arrays.fill(f[0], INF);// 在 0 个物品中选,除了价值 0 外都是非法情况
		f[0][0] = 0;

		for (int i = 1; i <= m; i++)
		{
			int x = list.get(i - 1);// x 表示当前物品的 价值
			for (int j = 0; j <= n; j++)
			{
				f[i][j] = f[i - 1][j];// 不选当前物品
				for (int k = 1; k * x <= j; k++)// 选取 k 个当前物品
					if (f[i - 1][j - k * x] != INF)
						f[i][j] = Math.min(f[i][j], f[i - 1][j - k * x] + k);
			}
		}
		return f[m][n];
	}
}

💖 滚动数组优化

⏰ 时间复杂度: O ( n n ) O(n\sqrt{n}) O(nn )力扣hot100 完全平方数 完全背包 滚动数组 四平方和定理,力扣 hot100,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-806245.html

class Solution {
	public int numSquares(int n)
	{
		int[] f = new int[n + 1];//f[i] 表示和为 i 的最小完全平方数和 的数量
		Arrays.fill(f, 0x3f3f3f3);
		f[0] = 0;
		for (int t = 1; t * t <= n; t++)
		{
			int x = t * t;
			for (int j = x; j <= n; j++)
				f[j] = Math.min(f[j], f[j - x] + 1);
		}
		return f[n];
	}
}

💖 四平方和定理

class Solution {
    public int numSquares(int n) {
        //判断是否是 1
        if (isSquare(n)) {
            return 1;
        }
        
        //判断是否是 4
        int temp = n;
        while (temp % 4 == 0) {
            temp /= 4;
        }
        if (temp % 8 == 7) {
            return 4;
        }

        //判断是否是 2
        for (int i = 1; i * i < n; i++) {
            if (isSquare(n - i * i)) {
                return 2;
            }
        }

        return 3;
    }

    //判断是否是平方数
    private boolean isSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }
}

到了这里,关于力扣hot100 完全平方数 完全背包 滚动数组 四平方和定理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣279. 完全平方数

    思路: 假设 dp[i] 为最少组成数 i 的平方数个数; 则其上一个状态为 dp[i - j^2] + 1,1 为 j^2: 即 i 的最少完全平方数 = i - j^2 的最少完全平方数 + 1,其中 j^2  = i 为最接近 i 的平方数; 初始值:dp[0] = 0 所以,可以通过动态规划算出每一个 dp[i] ———————————————

    2024年01月24日
    浏览(42)
  • 算法题打卡day45-背包问题 | 70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

    70. 爬楼梯 - 力扣(LeetCode) 状态:查看思路后AC。 除了常规的可以爬一或二级台阶,当题目稍微修改一下,变成可以爬m级台阶,之前的DP思路就有局限(dp[i] = dp[i-1] + dp[i-2),为了通杀这类问题,可以将题目转换为完全背包问题,可以爬的楼梯级数就是背包中的物品,楼梯总

    2024年02月11日
    浏览(49)
  • 力扣hot100 -- 双指针

    目录 🎂移动零 🌙盛最多水的容器 🌼三数之和 🌼接雨水 前缀和 + 辅助数组 双指针 单调栈 283. 移动零 - 力扣(LeetCode) 关于swap 思路 i = 0, j = 0 为了保证 0 都在末尾,且顺序不变 i 指向 0 j 指向 非0 元素时 交换两者(交换后,nums[x] = i 都是非0元素; i nums[x] = j,都是 0)

    2024年02月20日
    浏览(30)
  • 题目:一个整数,它加上 100 后是一个完全平方数,再加上 168 又是一个完全平方数,请问该数是多少?

    题目:一个整数,它加上 100 后是一个完全平方数,再加上 168 又是一个完全平方数,请问该数是多少? 完全平方指用一个整数乘以自己例如1×1,2×2,3×3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。 完全平方数是非负数 (下面会说到

    2024年02月04日
    浏览(42)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(61)
  • 力扣hot100刷题记录

    二刷hot100,坚持每天打卡3道题!!! Today:2023-09-24

    2024年02月13日
    浏览(42)
  • 【题解】U405180 计算平方和

    欢迎大家在评论区抢前排! 目录 (mathbf{Part 0}) 目录 (/ mathbf{Contents}) (mathbf{Part 1}) 题目大意 (/ mathbf{Item content}) (mathbf{Part 2}) 题解 (/ mathbf{Solution}) (mathbf{Part 2.1}text{ C}) + + 神奇整数类型之 (text{__int128 }/ mathbf{C}) + + (mathbf{Magic integer type}text{ __int128})

    2024年02月19日
    浏览(45)
  • 力扣HOT100 - 160. 相交链表

    解题思路:

    2024年04月12日
    浏览(48)
  • 力扣hot100 最长有效括号 动态规划

    Problem: 32. 最长有效括号 👨‍🏫 参考题解 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月20日
    浏览(76)
  • 力扣hot100 排序链表 归并排序 递归

    Problem: 148. 排序链表 👩‍🏫 参考 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( n ) O(n) O ( n )

    2024年01月25日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包