第一题 Excel表列序号
题目
思路
列名称对应序列号
分别从‘A’到‘Z’对应1到26
接着
在前面加A，继续从完成从‘A’到‘Z’
显然，这种进位制的计数法实质上是26进制
只不过，由于第一个元素A代表1，这是个没有零的26进制
代码
func titleToNumber(columnTitle string) (number int) {
for i, multiple := len(columnTitle)-1, 1; i >= 0; i-- {
//从字符串最后一个字符开始计算，每个字符乘以26为底它循环次数为幂的倍数得到它代表的实际数值
k := columnTitle[i] - 'A' + 1
number += int(k) * multiple
multiple *= 26
}
return
}也可以由前往后计算
func titleToNumber(columnTitle string) (number int) {
ans := 0
for i := 0; i < len(columnTitle); i++{
ans = ans*26+int(columnTitle[i]-'A'+1)
}
return ans
}效果
复杂度分析
时间复杂度：O(n)，其中 n 是列名称 columnTitle 的长度。需要遍历列名称一次。
空间复杂度：O(1)。
第二题 Power（x，n）
题目
解题
题目很简单
只是求n次x相乘的结果即可
如果n为负数则求1/x相乘的结果
但是
如果按照这种思维写出来的代码
func myPow(x float64, n int) float64 {
if n==0{return 1}
if n<0 {
x=1/x
n=-n
}
res:=x
for i:=1;i<n;i++{
res*=x
}
return res
}结果自然是超时的
因为在n的值很大的时候
效率实在过于低下
我们需要在此基础上再进行优化
通过分治
可以把复杂度从O（n）优化到O（logn）
代码
func myPow(x float64, n int) float64 {
var quickMul func( float64, int)float64
quickMul=func (x float64, n int) float64 {
if n == 0 {
return 1
}
y := quickMul(x, n/2)
if n%2 == 0 {
return y * y
}
return y * y * x
}
if n >= 0 {
return quickMul(x, n)
}
return 1 / quickMul(x, -n)
}效果
学习官方解析
由于n可以转化为二进制，即用2的幂次组成的数共同表示
因此我们只需计算出x的1，2，4，8，16...次方 就能用他们组成x的n次方
代码如下
func myPow(x float64, n int) float64 {
if n >= 0 {
return quickMul(x, n)
}
return 1.0 / quickMul(x, -n)
}
func quickMul(x float64, N int) float64 {
ans := 1.0
// 贡献的初始值为 x
x_contribute := x
// 在对 N 进行二进制拆分的同时计算答案
for N > 0 {
if N % 2 == 1 {
// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute
}
// 将贡献不断地平方
x_contribute *= x_contribute
// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N /= 2
}
return ans
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。