leetcode 279. Perfect Squares (python)

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

解法1：DP

递推公式为：

while j**2<=i:	  dp[i] = min(dp[i],dp[i-j**2]+1)

代码

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

c++版本

class Solution {
    
public:int numSquares(int n) {
    vector<int> dp(n+1,INT_MAX);dp[0] = 0;vector<int> square_num;for(int i=1;i<=n/2+1;i++){
    square_num.push_back(i*i);}// dp[1] = 1;for(int i=1;i<n+1;i++){
    for(int j=0;j<square_num.size();j++){
    if(i<square_num[j]) break;// cout << i << square_num[j] << endl;dp[i] = min(dp[i-square_num[j]]+1,dp[i]);}}return dp.back();}
};

时间复杂度：O(N^3/2), 循环N次， 每次尝试N的根号次
空间复杂度：O(N)
这种方法在时间上只超过了%19的用户，证明这种方法速度并不理想

解法2：BFS

算法流程

• 将所有可能合成目标数的perfect square数存在一个base中
• 将现在剩下需要合成的sum，以及已经花掉的step数以pair的方式存到栈中
• 搜索base中可以作为candidate的perfect square数,并将形成的符合条件的pair压入堆栈
• 注意为了得到的结果一定是最短的步数，需要从大到小搜索base，并且以队列方式先进先出FIFO
• 为了进一步加快速度，构建一个visited集合，储存所有已经出现过的curr_left,就是剩下需要被合成的sum
• 当curr_left存在与base中时，证明需要step最少的合成方式已经找到

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""    if n<1:return 0base = [i**2 for i in range(1,int(math.floor(math.sqrt(n))+1))]stack = collections.deque()stack.append((n,0))visited = set()visited.add(n)while stack:curr_left,curr_step = stack.popleft()if curr_left in base:return curr_step+1for j in reversed(base):if curr_left-j>0 and curr_left-j not in visited:stack.append((curr_left-j,curr_step+1))visited.add(curr_left-j)

时间复杂度：O(N)
空间复杂度：O(N)
这种方法超过了%92.5的用户

c++版本

class Solution {
    
public:int numSquares(int n) {
    vector<int> square_num;unordered_map<int,bool> memo;for(int i=n/2+1;i>=1;i--){
    square_num.push_back(i*i);memo[i*i] = true;}vector<int> visited(n+1,0);queue<pair<int,int>> q;q.push(make_pair(n,0));visited[n] = 1;while(!q.empty()){
    int curr_left = q.front().first, curr_step = q.front().second;q.pop();if(memo.count(curr_left)) return curr_step+1;for(auto& num : square_num){
    if(curr_left > num && visited[curr_left-num]==0){
    q.push(make_pair(curr_left-num,curr_step+1));visited[curr_left-num] = 1;}}}return -1;}
};

解法3：lagrange四平方和定理

四平方和定理如下：

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""while n%4 == 0:n//=4#case 1if n%8 == 7:return 4#case 2if int(n**0.5)**2 == n:return 1#case 3i = 1while i**2 < n:left = n-i**2if int(left**0.5)**2 == left:return 2i+=1#case 4return 3

时间复杂度：O(N^1/2)
空间复杂度：O(1)这种解法从时间和空间上都是最优的，超过了%99的用户
注意这边判断一个数是否能开平方的方法
参考：
https://blog.csdn.net/l_mark/article/details/89044137
https://blog.csdn.net/huhehaotechangsha/article/details/86597713