【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); }}

人的一生要疯狂一次，无论是为一个人，一段情，一段旅途，或一个梦想。