How to solve the problem of complete square number in leetcode
This article mainly shows you "how to solve the problem of complete squares in leetcode". The content is simple and clear. I hope it can help you solve your doubts. Let me lead you to study and learn this article "how to solve the problem of complete squares in leetcode".
Topic link
Https://leetcode-cn.com/problems/perfect-squares/
Topic description
Given a positive integer n, find several complete square numbers (such as 1, 4, 9, 16,.) so that their sum is equal to n. You need to minimize the number of complete squares of the sum.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
The idea of solving the problem
Tags: dynamic plannin
First initialize the array dp of length 1, with each position 0
If n is 0, the result is 0
The array is traversed with the subscript I, and each time the current number is updated to the maximum result, that is, dp [I] = I, for example, iTunes 4. The worst result is 4 "1" 1 "1" 1, that is, 4 digits.
The dynamic transfer equation is as follows: dp [I] = MIN (dp [I], dp [I-j] + 1), I represents the current number, and Jedj represents the square.
Time complexity: O (n*sqrt (n)), sqrt is the square root
Code
Java version
Class Solution {
Public int numSquares (int n) {
Int [] dp = new int [n + 1]; / / default initialization values are all 0
For (int I = 1; I = 0; jacks +) {
Dp [I] = Math.min (dp [I], dp [I-j * j] + 1); / / dynamic transfer equation
}
}
Return dp [n]
}
}
JavaScript version
/ * *
* @ param {number} n
* @ return {number}
, /
Var numSquares = function (n) {
Const dp = [... Array (nail1)] .map (_ = > 0); / / the array length is nim1, and the values are all 0.
For (let I = 1; I = 0; jacks +) {
Dp [I] = Math.min (dp [I], dp [I-j * j] + 1); / / dynamic transfer equation
}
}
Return dp [n]
}
Drawing and interpretation
These are all the contents of the article "how to solve the problem of complete squares in leetcode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!
