2021-05-04:给定一个非负整数c,你要判断是否存在两个整数a和b,使得a*a+b*b=c。【举例】c=5时,返回true。c=4时,返回true。c=3时,返回false。
福大大 答案2021-05-04:
四平方和定理。时间复杂度:O(sqrt(N))。空间复杂度:O(1)。
1.n一直除以4,直到不能整除为止。
2.n%8,如果余7,直接返回4。
3.从1到sqrt(n)开始循环,a*a+b*b=c成立时,a和b都不为0,返回2;a和b有一个为0,返回1。
4.返回3。
5.在本题中,返回值是1和2的是true。返回值是3和4的是false。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math"
)
func main() {
for i := 1000; i <= 1100; i++ {
ret := isSquares(i)
fmt.Println(i, ret)
}
}
//4+1+1+1
func isSquares(n int) bool {
return numSquares(n) <= 2
}
func numSquares(n int) int {
for n&3 == 0 { //n%4==0
n >>= 2 //n/=4
}
if n&7 == 7 { //n%8==7
return 4
}
a := 0
for a*a <= n {
b := int(math.Sqrt(float64(n - a*a)))
if a > b {
break
}
if a*a+b*b == n {
ret := 0
if a != 0 {
ret++
}
if b != 0 {
ret++
}
return ret
}
a += 1
}
return 3
}
执行结果如下:
This design is steller! You definitely know how to keep a reader amused.
Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great
job. I really loved what you had to say, and more than that, how you presented it.
Too cool!
When some one searches for his necessary thing, therefore he/she wants to be
available that in detail, so that thing is maintained over here.