ExcelSheetColumnTitle [source code]

public class ExcelSheetColumnTitle {
static
/******************************************************************************/
public class Solution {
    public String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int digit = n % 26;
            int next = n / 26;
            if (digit == 0 && next > 0) {
                sb.append('Z');
                n = next - 1;
            } else {
                sb.append((char) ('A' + digit - 1));
                n = next;
            }
        }
        return sb.reverse().toString();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ExcelSheetColumnTitle.Solution tester = new ExcelSheetColumnTitle.Solution();
        String[] inputs = {
            "26", "Z",
            "27", "AA",
            "28", "AB",
            "52", "AZ",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = Integer.parseInt(inputs[2 * i]);
            String expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(n);
            Printer.closeColor();
            String output = tester.convertToTitle(n);
            System.out.print(" -> " + output);
            Printer.openColor(output.equals(expected) ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

看起来很简单的一个题目, 最后却花了很多的时间!
刚开始发现问题之后(Z不好处理), 我就想着凭什么呢? 就想着怎么发现这背后的数学原理, 从数学上用一个简单的方法来解决掉, 但是想了很久都没有想到(包括base改到27, 同样没有用(因为base10的时候的最大的digit是9, 所以既然我们这里最大想要一个Z, 那么我们就要base是26 + 1: 可惜这个想法最后是错的)).

最后干脆还是笨办法, 分别处理了一下直接写了算了, 最后的速度是0ms (10%), 最优解;

这个是submission最优解上用recursion写的版本:

public class Solution {  
    public String convertToTitle(int n) {  
        return n == 0 ? "" : convertToTitle(--n / 26) + (char)('A' + (n % 26));  
    }  
}

有人指出这种代码其实最后的速度还是O(N^2), 因为每一个iteration都有concatenation.

This is a very neat solution, but I am afraid that the time complexity of this solution (at least in python, as far as I can tell) is O((n/26)^2) because of the string concatenation in python. The time complexity of string concatenation is O(k) since it is immutable, k is the total length of the string. In your case, the function recurs roughly n/26 times, and in each recursion, there is a O(n/26) operation. So the total complexity of this method is roughly O(n^2) instead of O(n).

An improve could be that only use list which has a O(1) complexity appending, and only concatenate once at the end. The time complexity will be O(n), but the code need more lines.

这个是discussion上面在我的解法的基础上优化的一种写法:

public class Solution {  
    public String convertToTitle(int n) {  
        StringBuilder result = new StringBuilder();  

        while(n>0){  
            n--;  
            result.insert(0, (char)('A' + n % 26));  
            n /= 26;  
        }  

        return result.toString();  
    }  
}

他这个解法就算是解决了我一直以来的问题, 用一个统一的数学上的解释来统一处理了所有的情况;
首先这个问题是一个base26的, 那么我们最后的alphabet其实是0..25, 我们要让0和A对应, 25和Z对应就行了;
所以他这里上来先一个--;

他这里用insert来避免最后的reverse, 但是:

Inserting to the beginning of StringBuilder actually takes O(n). see http://stackoverflow.com/questions/5931261/java-use-stringbuilder-to-insert-at-the-beginning

所以不如还是干脆最后reverse;

这个是另外一个人给出的解释:

Instead of 1 -> A, 26 -> Z, we can assume that 0 -> A, 25 -> Z, and then here comes the base 26 representation, it's similar when you convert a number from base 10 to base 2.

以及另外一个:
consider the letter 'A' to have a value of 1, 'B'->2 ..... 'Z'->26
note that in the above notation, values are 1-based

here our Radix (R) == 26

the final value of a number X Y Z = X R^2 + Y R + Z

this looks similar to base-10 decimal number but the biggest difference is that the numbers on every digit starts with 1, instead of 0., and the max on each digit goes up to R (Radix) instead of R-1

for example
Z== Radix
then next number is AA = R + 1 = Z+1
ZZ = R R + R
next number is AAA = 1R^2 + 1 * R + 1 = ZZ +1

so from the AAA notation to their sequence number (decimal) it's easy, but the other way is a bit tricky due to the way % and / operates.

Problem Description

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   

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:104.1K
Total Submissions:404.5K
Contributor: LeetCode
Companies
microsoft facebook zenefits
Related Topics
math
Similar Questions
Excel Sheet Column Number