這篇文章將為大家詳細講解有關(guān)LeetCode中完全平方數(shù)的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
成都創(chuàng)新互聯(lián)公司堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的襄州網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9
使用廣度優(yōu)先搜索方法，將 n 依次減去比 n 小的所有平方數(shù)，直至 n = 0 ，此時的層數(shù)即為最后的結(jié)果。
重慶分公司
重慶分公司
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，則返回當前層數(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
關(guān)于“LeetCode中完全平方數(shù)的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
