一个软件app_自己注册公司_seo网站推广与优化方案_百度指数数据分析平台官网

279. 完全平方数

• 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

• 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

1. 动态规划

• 思路:

  1. 初始化：dp[0] = 0，因为和为 0 不需要任何完全平方数

  2. 对于每个i (1~n)，遍历所有小于等于 i 的完全平方数 j * j，并更新 dp[i] 为 dp[i - j * j] + 1 的最小值

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""# 初始化dp数组, dp[i]表示和为i的完全平方数的最少数量dp = [float('inf')] * (n + 1)dp[0] = 0  # 和为0不需要任何完全平方数for i in range(1, n + 1):# 遍历所有小于等于i的完全平方数for j in range(1, int(math.sqrt(i)) + 1):dp[i] = min(dp[i], dp[i - j*j] + 1)return dp[n]

• 时间复杂度：O(n * sqrt(n))，因为需要遍历1到 n，并且对于每个 i，最多需要遍历 sqrt(i) 次

• 空间复杂度：O(n)，使用了一个大小为 n+1 的数组 dp

2. 广度优先搜索

• 思路:

  1. 将 n 作为起始节点

  2. 每次从当前节点减去一个完全平方数，得到新的节点

  3. 使用 BFS 来找到从 n 到 0 的最短路径

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""# 生成所有小于等于n的完全平方数squares = [i * i for i in range(1, int(n**0.5) + 1)]# BFS 队列，存储 (当前值, 步数)queue = deque([(n, 0)])visited = set()  # 记录已经访问过的节点while queue:current, steps = queue.popleft()# 遍历所有完全平方数for square in squares:next_val = current - squareif next_val == 0:  # 找到目标return steps + 1if next_val > 0 and next_val not in visited:visited.add(next_val)queue.append((next_val, steps + 1))return -1  # 如果没有找到，返回 -1（理论上不会发生）

• 时间复杂度：O(n * sqrt(n))，BFS 最多会遍历 n 个节点，每个节点最多有 sqrt(n) 条边

• 空间复杂度：O(n)，用于存储队列和访问记录