Excel Sheet Column Title

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 

Naive way: 或者从前往后提取字符，或者从后往前提取字符。

这道题咋看之下像是小学做过的10进制取每一位，但是细看之下有一个不同点。

我把它写成对应10进制便于理解。

10进制

0 -> null 

1 -> A

2 -> B

3 -> C

...

9 -> I

10-> J

11-> AA

12-> AB

...

19-> AI

20-> AJ

21-> BA

...

正常10进制是有一个0的，当9到10的时候是要进位的，而这个相当于9直接变成11。

这个不同点告诉我们不能使用正常的10进制取每一位的方法。但是除了要进位的时候，其他数值

都是与10进制数一一对应的。 于是我列了个表。

    1   10  100

1   1   x   x    A

9   9   x   x    I

10  10  x   x    J

11  1   1   x    AA

20  10  1   x    AJ

21  1   2   x    BA

30  10  2   x    BJ

40  10  3   x    CJ 

100 10  9   x    IJ

110 10  10  x    JJ

120 10  1   1    AAJ

130 10  2   1    ABJ

这样就很明了了。10到11， 20到21， 110到120，都有一个不符合一般规律的跳变，这里需要单独处理。

基本逻辑为：

如果该数除以pow(10,i)的余数不为0，比如1，2，3...9除以10的余数都不为0，就写对应的字母。

如果概述除以pow(10,i)的余数为0，比如10，20，100..除以10的余数都为0，就写pow(10,i)，这里是10。

然后每一次都减去用掉的部分直到该数变为0.

当然要把10换成26. 

public class Solution {

    int base = 26;

    public String convertToTitle(int n) {

        String s = "";

        int i = 0;

        while(n!=0){

            int num = n%(int)Math.pow(base,i+1)==0?(int)Math.pow(base,i+1):n%(int)Math.pow(base,i+1);

            num /= (int)Math.pow(base,i);

            s += (char)(num-1 + 'A');

            n -= num*(int)Math.pow(base,i);

            i++;

        }

        

        return new StringBuilder(s).reverse().toString();

    }

}

Improved Way: 这道题其实是挺难的，我第一次做就在如何对应数字和字母上耗了好久。但是通过这样列表的分析一切都明了了。

省时省力。下面是我第一次的做法，采用完全不同的方法，是从左往右进行的。

从左往右进行不能直接取商，必须得先减去之前所有幂次方的和(对应lowerPart)，然后每次的幂次方和都要对应减小。

总之很蛋疼，两种算法的复杂度都是O(logn)以26为底。

private static final int base = 26;
    public String convertToTitle(int n) {
     String s = "";
        int digits = (int)Math.floor(Math.log(n)/Math.log(base));
        int lowerPart = 0;
        for(int i = 0;i < digits;i++)
            lowerPart += (int)Math.pow(base,i);
        while(n != 0){
            int divisor = (int)Math.pow(base,digits);
            int number = (n-lowerPart)/divisor;
            if(number!= 0)
                s += (char)(number+'A'-1);
            n -= number*divisor;
            digits--;
            lowerPart -= (int)Math.pow(base,digits);
        }
        return s;
    }