共计 1508 个字符,预计需要花费 4 分钟才能阅读完成。
第一题 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)著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。
正文完