溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

LeetCode中完全平方數(shù)的示例分析

發(fā)布時(shí)間：2021-12-15 14:35:14 來(lái)源：億速云 閱讀：144 作者：小新 欄目：大數(shù)據(jù)

這篇文章將為大家詳細(xì)講解有關(guān)LeetCode中完全平方數(shù)的示例分析，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

題目描述

給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。

 
示例 1:

輸入: n = 12    
輸出: 3    
解釋: 12 = 4 + 4 + 4

 
示例 2:

輸入: n = 13    
輸出: 2    
解釋: 13 = 4 + 9

 

思路解析

使用廣度優(yōu)先搜索方法，將 n 依次減去比 n 小的所有平方數(shù)，直至 n = 0 ，此時(shí)的層數(shù)即為最后的結(jié)果。

 

動(dòng)畫(huà)演示

LeetCode中完全平方數(shù)的示例分析  
動(dòng)畫(huà)演示 Made by 王琛
 

參考代碼

 1/// @五分鐘學(xué)算法
 2class Solution(object):
 3    def numSquares(self, n):
 4        Q = collections.deque([n])
 5        visited, level = set(), 0
 6        while Q:
 7            # 按層處理
 8            for i in range(len(Q)):
 9                n = Q.popleft()
10                # 若n==0，則返回當(dāng)前層數(shù)
11                if n == 0: return level
12                # 依次減去所有比n小的平方數(shù)
13                for i in range(1,int(n**0.5)+1):
14                    val = n - i**2
15                    if val in visited: continue
16                    Q.append(val)
17                    visited.add(val)
18            level = level + 1
   

代碼截圖

LeetCode中完全平方數(shù)的示例分析

關(guān)于“LeetCode中完全平方數(shù)的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手