快速幂
func myPow(x float64, n int) float64 {
flag := true
var res float64
res = 1.0
if (n < 0){
flag = false
n = -n
} else if (n == 0){
res = 1.0
}
for n > 0{
if (n%2 == 1){res = res * x}
n = n /2
x = x * x
}
if (flag == false){
return 1/res
} else{
return res
}
}
稍微好看点:
func myPow(x float64, n int) float64 {
if (n < 0){
return 1.0/quickPow(x, 0 - n)
}
return quickPow(x, n)
}
func quickPow(x float64, n int) float64{ //这里可以命名_quickPow 表明内部函数
res := 1.0
for n > 0{
if (n&1 == 1){res = res * x}
n = n /2
x = x * x
}
return res
}
在快速幂算法中,`exp % 2 == 1` 这个条件用于检查当前的指数 `exp` 是否是奇数。当 `exp` 是奇数时,我们需要将当前的 `base` 乘到结果 `result` 上。具体解释如下:
1. **奇数指数处理**:
当 `exp` 是奇数时,我们可以将其表示为 `exp = 2k + 1`(其中 \( k \) 是一个整数)。在这种情况下,`base^{exp}` 可以写成 `base^{2k+1} = base^{2k} * base`。因此,我们需要将当前的 `base` 乘到结果 `result` 上。
2. **偶数指数处理**:
当 `exp` 是偶数时,我们可以将其表示为 `exp = 2k`。在这种情况下,`base^{exp}` 可以写成 `(base^2)^k`。因此,我们只需将 `base` 平方,并将 `exp` 减半。
在代码中,这个条件用于判断当前的 `exp` 是否是奇数,并在是奇数时更新 `result`。具体代码如下:
```go
func quickPow(base, exp, mod int) int {
result := 1
base = base % mod
for exp > 0 {
if exp % 2 == 1 {
result = (result * base) % mod
}
base = (base * base) % mod
exp = exp / 2
}
return result
}
解释:
- if exp % 2 == 1 { result = (result * base) % mod }
:如果 exp
是奇数,将当前的 base
乘到 result
上,并取模。
- base = (base * base) % mod
:将 base
平方,并取模。
- exp = exp / 2
:将 exp
减半。
通过这种方式,快速幂算法能够在对数时间复杂度内计算大整数幂,显著提高计算效率。
### TLE 超时-暴力解法
func myPow(x float64, n int) float64 {
flag := true
var res float64
res = 1.0
if (n < 0){
flag = false
n = -n
} else if (n == 0){
res = 1.0
}
for ;n > 0;n–{
res = res * x
}
if (flag == false){
return 1/res
} else{
return res
}
}
```