Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 –> AB 

python给出的函数和参数是

class Solution:
    # @return a string
    def convertToTitle(self, num):

显然这里就是逆向,将ASCII转换成字符即可

>>> chr(65)
'A'
>>> chr(66)
'B'

再分析下过程,假如num为28,倒着推是这么算的:

A * 26 + B = 1 * 26 + 2 = 28

也就是说传进去一个参数,%26为低位,/26商为高位

但是假如有多个字符,比如ABC,换成数字就是:

A * 26 ^ 2 + B * 26 + C = num

如此看来低位C还是num%26,B是(num/26)%26,A是(num/26^2)%26,因此可以不停%26,然后倒序

第一次提交

class Solution:
    # @return a string
    def convertToTitle(self, num):
        str = ''
        while num > 0:
            a = num % 26
            num /= 26
            str = chr(a + 64) + str
        return str

结果错误

Submission Result: Wrong Answer
Input:	26
Output:	"A@"
Expected:	"Z"

显然当num为26的时候,a为0,chr(64)变成了A,而不是Z,显然错误,再仔细分析一下:

如果num为26,26 * 1,直接chr(26 + 64),为Z

如果num为27,26 * 1 + 1,直接chr(26 + 64) + chr(1 + 64),为AA

如果num为26 * 2,26直接chr(26 + 64) + chr(26 + 64),为ZZ

如果num为26 * 2 + 1,直接chr(26 + 64) + chr(26 + 64) + chr(1 + 64),为ZZA

如此看来,十分简单,自己前面想多了~!只需要根据商和余数判断即可

第二次提交

class Solution:
    # @return a string
    def convertToTitle(self, num):
        str = ''
        tmp1 = num / 26
        tmp2 = num % 26
        if tmp1:
            str = chr(26 + 64) * tmp1
        if tmp2:
            str += chr(tmp2 + 64)
        return str

看看结果,红色错误

Submission Result: Memory Limit Exceeded

看到这结果我也是醉了~!

不过仔细想想,这个错误,难道是死循环还是说输出问题,只有可能是tmp1那里拼凑N次导致的

>>> a = 'hello'
>>> a * 100
'hellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohellohello'

当重复10000+次后,并不是一次性输出来,而是好像一定缓冲区,逐步输出来的,可能就是输出的问题,那就换一种方式试试,因此加一个

第三次提交

class Solution:
    # @return a string
    def convertToTitle(self, num):
        str = ''
        tmp1 = num / 26
        tmp2 = num % 26
        while tmp1:
            str += chr(26 + 64)
            tmp1 -= 1
        if tmp2:
            str += chr(tmp2 + 64)
        return str

结果还是不行,这样性能就不行了

Submission Result: Time Limit Exceeded

Last executed input:	1000000001

仔细思考下,在python里,字符串是不可变类型,因此不停+会产生新的字符串,用到了新的内存,换成join第四次提交

class Solution:
    # @return a string
    def convertToTitle(self, num):
        str = ''
        tmp1 = num / 26
        tmp2 = num % 26
        while tmp1:
            str = ''.join([str, chr(26 + 64)])
            tmp1 -= 1
        if tmp2:
            str += chr(tmp2 + 64)
        return str

错误信息跟上面一样,也是醉了~!

发表评论