Computer Science/Coding Test
LeetCode: 279. Perfect Squares
focalpoint
2021. 12. 27. 15:11
O(N**2) Time Complexity, O(N) Memory
Not an effective solution at all especially in terms of time complexity.
class Solution:
def numSquares(self, n: int) -> int:
INT_MAX = int(1e5)
dp = [INT_MAX] * (n+1)
x = 1
while x * x <= n:
dp[x*x] = 1
x += 1
for i in range(1, n+1):
if dp[i] != INT_MAX:
continue
for j in range(i//2, i):
dp[i] = min(dp[i], dp[j]+dp[i-j])
return dp[n]
A nice approach would be BFS.
Time Complexity is O(N) as the worst scenario here is adding up 1s. (Deepest route is 1+1+1+...+1)
Memory Complexity is O(N*sqrt(N)) as we have sqrt(N) perfect square numbers and the height of the tree will be N at worst.
class Solution:
def numSquares(self, n: int) -> int:
psns = []
x = 1
while x * x <= n:
psns.append(x*x)
x += 1
nums, cnt = {n}, 0
while nums:
next_nums = set()
cnt += 1
for num in nums:
for psn in psns:
if psn == num:
return cnt
if num < psn:
break
next_nums.add(num-psn)
nums = next_nums
DP Solution
Time Complexity is O(N*sqrt(N))
Memory Complexity is O(N)
class Solution:
def numSquares(self, n: int) -> int:
INT_MAX = int(1e5)
dp = [INT_MAX] * (n+1)
dp[0] = 0
for i in range(1, n+1):
for j in range(1, int(i**0.5)+1):
dp[i] = min(dp[i], dp[i-j*j]+1)
return dp[n]