【LeeCode】279. 完全平方数

【题目描述】

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

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

​​https://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); }}