In this Leetcode Perfect Squares problem solution, we have given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Problem solution in Python.
class Solution(object): def numSquares(self, n): from math import ceil, sqrt dp = [0, 1, 2, 3] if n<=3: return dp[n] else: for i in range(4, n + 1): dp.append(i) for x in range(1, int(ceil(sqrt(i))) + 1): temp = x*x if temp>i: break else: dp[i] = min(dp[i], 1 + dp[i - temp]) return dp[n]
Problem solution in Java.
class Solution { public int numSquares(int n) { int sqrtN = (int) Math.sqrt(n); int[] squares = new int [sqrtN]; for (int i = 1; i <= sqrtN; i++) { squares[i - 1] = i * i; } int[] dp = new int [n + 1]; for (int i = 1; i <= n; i++) { dp[i] = n + 1; for (int j = 0; j < squares.length; j++) { if (i < squares[j]) { continue; } if (squares[j] == i) { dp[i] = 1; continue; } else { dp[i] = Math.min(dp[i], 1 + dp[i - squares[j]]); } } } return dp[n]; } }
Problem solution in C++.
class Solution { public: int numSquares(int n) { if (n==0) return 0; vector<int> per; int f[n+5]={0}; f[1]=1; for(int i=2;i<=n;i++) { int minV=INT_MAX; int j=1; while (j*j<=i) { if (j*j==i) { minV=1;break; } minV=min(minV,f[i-j*j]+1); j++; } f[i]=minV; } return f[n]; } };
Problem solution in C.
void solve(int n, int * ans, int a){ if (a > *ans) return; if (n == 0) { if (a < *ans) *ans = a; return; } int z = 1; while (z++) { // Find the biggest perfect square that is less than n. if (z*z > n) { z = z-1; break; } } while (z > 0) { // Start with the biggest perfect square less than n and // continue trying every perfect square less than that. solve(n - z*z, ans, a+1); if (a+2 >= *ans) break; z = z-1; } return; } int numSquares(int n) { int ans = INT_MAX; solve(n, &ans, 0); return ans; }
0 Comments