首页 > 其他分享 >LeetCode 279 完全平方数

LeetCode 279 完全平方数

时间:2024-07-31 15:11:09浏览次数:16  
标签:拆成 平方 int 完全 整数 279 LeetCode dp

题目描述

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

思路

使用动态规划,对于一个数n,要将其拆成几个完全平方数的和,并且要求完全平方数的个数尽可能少,假设n可以拆成一个完全平方数x(n-x)的和,那么只需要继续求(n-x)最少可以拆成多少个完全平方数就能得出当选择x作为一个完全平方数时的最少完全平方数个数。然后选择不同的x,求最小的那一个答案即可。

具体步骤

1 确定dp数组的意义

dp[i]表示整数i最少可以拆成dp[i]个完全平方数的和。

2 确定状态转移方程

dp[i] = min{dp[i - x]} + 1 (x < i且 x为完全平方数)

3 初始状态

因为要求的是最小值,所以初始状态dp[i]设置为正无穷。并且dp[0]= 0,dp[1]=1。0其实在这里没什么意义,但是在递推过程中需要通过dp[0]来计算dp[i * i],比如dp[4] = dp[2 * 2] = dp[4 - 2 * 2] + 1 = 1

代码

class Solution {
    public int numSquares(int n) {
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

标签:拆成,平方,int,完全,整数,279,LeetCode,dp
From: https://www.cnblogs.com/zawaludo/p/18334644

相关文章

  • Leetcode每日一题 20240729 682.棒球比赛
    题目描述你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表ops,其中ops[i]是你需要记录的第i项操作,ops遵循下述规则:整数x:表示本回合新获......
  • Leetcode每日一题 202040726 2740.找出分区值
    题目描述给你一个正整数数组nums。将nums分成两个数组:nums1和nums2,并满足下述条件:数组nums中的每个元素都属于数组nums1或数组nums2。两个数组都非空。分区值最小。分区值的计算方法是|max(nums1)-min(nums2)|。其中,max(nums1)表示数组nums1......
  • Leetcode每日一题 20240727 3106.满足约束且字典序最小的字符串
    题目描述给你一个字符串s和一个整数k。定义函数distance(s1,s2),用于衡量两个长度为n的字符串s1和s2之间的距离,即:字符‘a’到‘z’按循环顺序排列,对于区间[0,n-1]中的i,计算所有「s1[i]和s2[i]之间最小距离」的和。例如,distance(“ab”,......
  • Leetcode每日一题 20240730 2961.双模幂运算
    题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)%mi==target返回一个由好下标组成的数组,顺序不限。2961.双模幂......
  • 代码随想录算法训练营Day0| LeetCode704: 二分查找
    LeetCode704二分查找先看了一下数组理论基础:数组基础题目链接:704.二分查找啥也没看,凭感觉直接上手:classSolution(object): defsearch(self,nums,target): fornuminnums: ifnum==target: returnnums.index(num) break return-1通过倒是......
  • (nice!!!)LeetCode 2952. 需要添加的硬币的最小数量(贪心、数组)
    题目:2952.需要添加的硬币的最小数量思路:假设区间[1,s-1]的数都可组合得到,当遍历到x=coins[i]时,1、当x<=s时,可以组合的数就是区间[1,s-1]和区间[x,s-1+x]的交集,即区间[1,s-1+x]2、当x>s时,区间[1,s-1]和区间[x,s-1+x]没有交集,那我就只能通过添加一个数来实现了。在这里......
  • leetcode题目总结
    前言本文为leetcode上的题目简单分析总结,仅作记录,欢迎提出建议,共同学习交流。 390.消除游戏列表 arr 由在范围 [1,n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。重复上面的步......
  • LeetCode15 三数之和
    前言题目:15.三数之和文档:代码随想录——三数之和编程语言:C++解题状态:没思路…思路不可包含重复三元组的条件是本题最大的难点,本题的一大思路在与排序后进行去重。代码双指针法classSolution{public:vector<vector<int>>threeSum(vector<int>&nums......
  • LeetCode-day30-2961. 双模幂运算
    LeetCode-day30-2961.双模幂运算题目描述示例示例1:示例2:思路代码题目描述给你一个下标从0开始的二维数组variables,其中variables[i]=[ai,bi,ci,mi],以及一个整数target。如果满足以下公式,则下标i是好下标:0<=i<variables.length((aibi%10)ci)......
  • LeetCode 756. Pyramid Transition Matrix
    原题链接在这里:https://leetcode.com/problems/pyramid-transition-matrix/description/题目:Youarestackingblockstoformapyramid.Eachblockhasacolor,whichisrepresentedbyasingleletter.Eachrowofblockscontains onelessblock thantherowbenea......