题目:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...
) which sum to n.
For example, given n = 12
, return 3
because 12 = 4 + 4 + 4
; given n = 13
, return 2
because 13 = 4 + 9
.
链接: http://leetcode.com/problems/perfect-squares/
题解:
又是数学题,每次一看jianchao.li.fighter添加的题目,就知道跟数字有关系。数学不好的我,做起来真的很头大....这道题看了discuss以后发现有好多种方法,有dp, BFS,还有纯数学解法。下面是最简单的dp,核心的递推公式是对于j= 1 , j * j <= i来说, tmp = Math.min(tmp, tmp[i - j * j] + 1);
Time Complexity - O(nlogn), Space Complexity - O(n)
public class Solution { public int numSquares(int n) { if(n < 1) { return 0; } int[] min = new int[n + 1]; for(int i = 1; i <= n; i++) { int tmp = Integer.MAX_VALUE; for(int j = 1; j * j <= i; j++) { tmp = Math.min(tmp, min[i - j * j] + 1); } min[i] = tmp; } return min[n]; } }
题外话:
最近似乎丧失了独立思考的能力,每次做题想了5分钟就不耐烦去看Discuss的答案了。这样可不行,需要锻炼的不是记题背题,而是自己的思维。真是懒惰到家了。
二刷:
依然是使用和一刷一样的方法。
我们主要就是建立一个dp数组。在i从1到n的过程中,我们计算 dp[i - j * j] + 1最小的值。也就是减去一个平方数后我们比较这个剩余值的最小值,再加上1,就是我们的dp[i]
Java:
Time Complexity - O(n * sqrt(n)), Space Complexity - O(n)
public class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { int min = n; for (int j = 1; j * j <= i; j++) { min = Math.min(min, dp[i - j * j] + 1); } dp[i] = min; } return dp[n]; } }
三刷:
又卡了这道题,不过现在找到了原因 - 直觉上总觉得除了DP以外会有更好的解法,事实上也确实有很好的数学解法。有机会再好好理解,现在要做到的是,碰到题目,至少要能够想出一个可行的解法,再考虑优化。
数学解法就是拉格朗日了,意思是说每个自然数都可以被表示为4个自然数的平方。先mark下来,以后再看。 https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
Java:
DP:
public class Solution { public int numSquares(int n) { if (n < 1) return n; int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { int min = Integer.MAX_VALUE; for (int j = 1; j * j <= i; j++) { min = Math.min(min, dp[i - j * j] + 1); } dp[i] = min; } return dp[n]; } }
题外话:
一道题目做了好几遍还会卡,说明并不理解。需要真正好好静下心来思考才行。
Reference:
https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics
https://leetcode.com/discuss/56982/o-sqrt-n-in-ruby-c-c
https://leetcode.com/discuss/62526/an-easy-understanding-dp-solution-in-java
https://leetcode.com/discuss/56983/simple-java-dp-solution
https://leetcode.com/discuss/72205/java-dp-solution-with-explanation
https://leetcode.com/discuss/57066/4ms-c-code-solve-it-mathematically
https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
https://www.alpertron.com.ar/4SQUARES.HTM
https://leetcode.com/discuss/57185/o-sqrt-n-about-0-034-ms-and-0-018-ms
https://leetcode.com/discuss/93109/straightforward-java-bfs-beats-93-69%25
https://leetcode.com/discuss/57850/explanation-of-the-dp-solution
https://leetcode.com/discuss/68295/beautiful-9-lines-java-solution
https://leetcode.com/discuss/57020/java-solution-o-n-1-2-time-and-o-1-space
https://leetcode.com/discuss/57477/sqrt-applying-fermats-theorm-brahmagupta-fibonacci-identity
https://leetcode.com/discuss/63750/concise-java-dp-solution
https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares