Last active
April 21, 2019 10:26
-
-
Save jack5241027/cb58eab8e8c98ee99544a04de79eef27 to your computer and use it in GitHub Desktop.
279. Perfect Squares.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @param {number} n | |
| * @return {number} | |
| */ | |
| var numSquares = function(n) { | |
| const squares = []; | |
| for (let i = 1; i * i <= n; i++) { | |
| squares.push(i*i); | |
| } | |
| const que = []; | |
| que.push([n]); | |
| let count = 1; | |
| while (que.length) { | |
| const curLevel = que.shift(); | |
| const level = [] | |
| for (let j = 0; j < curLevel.length; j++) { | |
| const remain = curLevel[j]; | |
| for (let i = 0; i < squares.length; i++) { | |
| const diff = remain - squares[i]; | |
| if (diff > 0) { | |
| level.push(remain - squares[i]); | |
| } | |
| if (diff === 0) { | |
| return count; | |
| } | |
| if (diff < 0) { | |
| break; | |
| } | |
| } | |
| } | |
| que.push(level); | |
| count += 1; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment