엔지니어 게시판
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))
        
        
        
        
전체 307 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 38 명
  • 오늘 방문자 741 명
  • 어제 방문자 2,154 명
  • 최대 방문자 2,154 명
  • 전체 회원수 451 명
알림 0