如何用Python实现LeetCode 279题的完全平方数查找算法？

本文共计492个文字，预计阅读时间需要2分钟。

【题目描述】给你一个整数n，返回和为n的最小平方数个数。

【题目解析】完全平方数是一个整数可以表示为某个整数的平方。例如，1, 4, 9, 16等都是完全平方数。题目要求找出所有和为n的最小平方数个数。

【代码实现】pythondef min_squares(n): dp=[0] * (n + 1) for i in range(1, n + 1): dp[i]=float('inf') for j in range(1, int(i ** 0.5) + 1): dp[i]=min(dp[i], dp[i - j * j] + 1) return dp[n]

示例n=12result=min_squares(n)print(result) # 输出结果

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

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

​​leetcode.cn/problems/perfect-squares/?favorite=2cktkvj​​

回溯

​​windliang​​

回溯： 暴力po解, 会超时

import java.util.*;// 2022-12-17class Solution { public int numSquares(int n) { System.out.println(dfs(n)); return dfs(n); } private int dfs(int n) { if (n == 0 ) return 0; int count = Integer.MAX_VALUE; for (int i = 1; i * i <= n; i++){ count = Math.min(count, dfs(n - i * i) + 1); } return count; }}public class Main{ public static void main(String[] args) { int num = 12; // 输出： 3 int num1 = 13; // 输出: 2 new Solution().numSquares(num); new Solution().numSquares(num1); }}

优化

优化：利用map保存中间值迭代的结果

import java.util.*;// 2022-12-17class Solution { public int numSquares(int n) { int res = dfs(n, new HashMap<Integer, Integer>()); System.out.println(res); return res; } private int dfs(int n, HashMap<Integer, Integer> map) { // 记录每个数字的count次数 直接返回 if (map.containsKey(n)){ return map.get(n); } if ( n == 0 ) return 0; int count = Integer.MAX_VALUE; for (int i = 1; i * i <= n; i++){ count = Math.min(count, dfs(n - i * i, map) + 1); } map.put(n, count); return count; }}public class Main{ public static void main(String[] args) { int num = 12; // 输出： 3 int num1 = 13; // 输出: 2 new Solution().numSquares(num); new Solution().numSquares(num1); }}