279 Perfect Squares
Given a positive integern, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum ton.For example, givenn=
12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.Approach 1: DFS
The Idea: Find the smallest path from root to leaf. Let squares be all the perfect squares that are less than n. Begin with the root node as n, and define all children of n to be
n-squares[i]. Continue this process until a remainder of 0 is reached. Lagrange's four-square theorem tells us that this number will always be less than or equal to 4 (
every natural number can be represented as the sum of four integer squares). Return the minimum path length. This is bad approach because it prioritizes the depth of the tree when it is a smarter to equally weight the branches closest to the root.class Node:
def __init__(self, num, remainder, count):
self.num = num
self.remainder = remainder
self.count = count
class Solution(object):
def __gatherPerfectSquares(self, n):
"""
:param n: up to <= n
:return: List[int] of perfect squares
"""
return [i*i for i in range(1,n+1) if i*i <= n]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
squares = self.__gatherPerfectSquares(n)
top = Node(n, n, 0)
stack = [top]
the_min = 9999
while len(stack) > 0:
top = stack.pop()
# Lagrange's four-square theorem
if top.count >= 4:
continue
options = [num for num in squares if num <= top.remainder]
for opt in options:
remainder = top.remainder - opt
if remainder == 0:
the_min = min(the_min, top.count + 1)
stack.append(Node(opt, remainder, top.count + 1))
return the_min
Approach 2: BFS
import queue
class Node:
def __init__(self, num, remainder, count):
self.num = num
self.remainder = remainder
self.count = count
class Solution(object):
def __gatherPerfectSquares(self, n):
"""
:param n: up to <= n
:return: List[int] of perfect squares
"""
return [i*i for i in range(1,n+1) if i*i <= n]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
squares = self.__gatherPerfectSquares(n)
q = queue.Queue()
q.put(Node(n, n, 0))
while not q.empty():
front = q.get()
# Lagrange's four-square theorem
if front.count >= 4:
continue
options = [num for num in squares if num <= front.remainder]
for opt in options:
remainder = front.remainder - opt
if remainder == 0:
return front.count + 1
q.put(Node(opt, remainder, front.count + 1))
Last modified 4yr ago