LeetCode 솔루션 분류

[11/22] 279. Perfect Squares

컨텐츠 정보

본문

Medium
8635373Add to ListShare

Given an integer n, return the least number of perfect square numbers that sum to n.

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, 149, 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))
        
        
        
        
LeetCode 솔루션 357 / 5 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0