LeetCode 솔루션 분류
[11/22] 279. Perfect Squares
본문
Medium
8635373Add to ListShareGiven 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.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
Constraints:
1 <= n <= 104
Accepted
618,636
Submissions
1,176,512
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
import math
from collections import deque
class Solution:
def numSquares(self, n: int) -> int:
queue = deque([(n,0)])
while queue:
num, steps = queue.popleft()
for sqside in range(int(math.sqrt(num)), 0, -1):
newnum = num - sqside**2
if newnum == 0: return steps+1
queue.append((newnum, steps+1))
