溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關LeetCode中完全平方數的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9
使用廣度優先搜索方法，將 n 依次減去比 n 小的所有平方數，直至 n = 0 ，此時的層數即為最后的結果。
1/// @五分鐘學算法
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，則返回當前層數
11 if n == 0: return level
12 # 依次減去所有比n小的平方數
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中完全平方數的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
