关于golang:golangleetcode中级Excel表列序号Powerxn

第一题 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次方

代码如下