mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
34 lines
494 B
Go
34 lines
494 B
Go
package leetcode
|
|
|
|
import "math"
|
|
|
|
func numSquares(n int) int {
|
|
if isPerfectSquare(n) {
|
|
return 1
|
|
}
|
|
if checkAnswer4(n) {
|
|
return 4
|
|
}
|
|
for i := 1; i*i <= n; i++ {
|
|
j := n - i*i
|
|
if isPerfectSquare(j) {
|
|
return 2
|
|
}
|
|
}
|
|
return 3
|
|
}
|
|
|
|
// 判断是否为完全平方数
|
|
func isPerfectSquare(n int) bool {
|
|
sq := int(math.Floor(math.Sqrt(float64(n))))
|
|
return sq*sq == n
|
|
}
|
|
|
|
// 判断是否能表示为 4^k*(8m+7)
|
|
func checkAnswer4(x int) bool {
|
|
for x%4 == 0 {
|
|
x /= 4
|
|
}
|
|
return x%8 == 7
|
|
}
|