Leetcode 279. Perfect Squares (python+cpp)

题目

解法1：暴力recursion（TLE）：

class Solution:def numSquares(self, n: int) -> int:def helper(curr,remain):nonlocal ansif remain<0:returnif remain==0:ans = min(ans,curr)returnfor num in square_numbers:helper(curr+1,remain-num*num)if n == 0 or n==1:return nans = float('inf')square_numbers = [i for i in range(1,n//2+1)]helper(0,n)return ans

解法2：memorization+recursion（TLE）

python解法：

class Solution:def numSquares(self, n: int) -> int:def helper(remain):if memo[remain] != float('inf'):return memo[remain]if remain==0:return 0for num in square_numbers:if num<=remain:memo[remain] = min(memo[remain],1+helper(remain-num))return memo[remain]if n == 0 or n==1:return nmemo = [float('inf')]*(n+1)square_numbers = [i*i for i in range(1,int(n**0.5)+1)]return helper(n)

C++解法：

class Solution {
    
public:int numSquares(int n) {
    if (n==0 || n==1) return n;vector<int> square_numbers;for (int i=1;i<n/2+1;i++){
    square_numbers.push_back(i);}vector<int> memo(n+1,INT_MAX);return helper(n,memo,square_numbers);}int helper(int remain,vector<int>& memo,vector<int> square_numbers){
    if (memo[remain] != INT_MAX) return memo[remain];if (remain==0) return 0;for (auto num:square_numbers){
    if (num*num<=remain){
    memo[remain] = min(memo[remain],1+helper(remain-num*num,memo,square_numbers));}}return memo[remain];}
};

recursion解法加上memorization居然还是TLE，挺惊讶的。不过对理解recursion还是有好处的

解法3：动态规划

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割 条件的位置。我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加 构成。在本题中，位置i只依赖i- k2 的位置，如i-1、i-4、i-9等等，才能满足完全平方分割 的条件。因此dp[i]可以取的最小值即为1+min(dp[i-1],dp[i-4],dp[i-9]···)。
python代码如下：

class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')]*(n+1)dp[0] = 0for i in range(1,n+1):j = 1while j*j<=i:dp[i] = min(dp[i], dp[i-j*j] + 1)j+=1return dp[n]

这种解法有可能会TLE，可以稍微改进一下就是把平方数预存一下，避免重复的平方计算，代码如下：

class Solution:def numSquares(self, n: int) -> int:# dp解法2square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]dp = [float('inf')] * (n+1)# bottom casedp[0] = 0for i in range(1, n+1):for square in square_nums:if i < square:breakdp[i] = min(dp[i], dp[i-square] + 1)return dp[-1]

C++版本dp解法代码如下：

class Solution {
    
public:int numSquares(int n) {
    vector<int> dp(n+1,INT_MAX);dp[0] = 0;for (int i=1;i<=n;i++){
    for (int j=1;j*j<=i;j++){
    dp[i] = min(dp[i], dp[i-j*j] + 1);}} return dp[n];}
};

相对来说C++的速度自然快很多，不会出现TLE的情况

解法4：greedy by recursion

这种解法的核心思想就是通过recursion把数字breakdown成很多的子部分，然后通过递归的判断子部分是否能用平方和的方式来表示，具体如下：

• 我们定义一个function，这个function接受两个参数，一个是当前要被分割的数字n，另一个是需要被分割成几部分count，函数返回值是n是否能被分割成count个部分，每个部分是一个平方数
• count从小到大开始遍历，最先成功的就是我们的答案
  python代码如下：

class Solution:def numSquares(self, n: int) -> int:# greedy + recursion 解法def can_divided_by(n,count):if count == 1:return n in square_numsfor k in square_nums:if can_divided_by(n-k,count-1):return Truereturn Falsesquare_nums = [i*i for i in range(1,int(n**0.5)+1)]for count in range(1,n+1):if can_divided_by(n,count):return count

C++版本代码如下：

class Solution {
    
public:int numSquares(int n) {
    set<int> square_nums;for (int i=1;i*i<=n;i++){
    square_nums.insert(i*i);}for (int count=1;count<=n;count++){
    if (can_divided_by(n,count,square_nums)) return count;} return 0;}bool can_divided_by(int n, int count, set<int>& square_nums){
    if (count==1) return square_nums.find(n)!=square_nums.end();for (auto k:square_nums){
    if (can_divided_by(n-k,count-1,square_nums)) return true;} return false;}
};

参考链接