[leetcode] 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

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

tag: math

虽然此题被leetcode标为简单题,但感觉还是有难度的,需要脑筋急转弯,而不是考察数据结构。

此题关键在于,我们平常的计数法是0-25,但它是1-26.并且,后一位的Z表示的数的大小和前一位的A相同。

即:AZ = 1 * 26 + 26

A和Z都表示26,所以我们在做取余求各位的值时,如果余数为0,我们把它置为26,并向上一位借1,也即n–。在循环外面,如果n不等于0,我们需要把它也压入栈中,然后再把栈反转,得到最后的结果。

class Solution {
public:
    stack<int> s;
    string convertToTitle(int n) {
        while(n / 26 > 0){
            int leastDigit = n % 26;
            n = n / 26;
            if(leastDigit == 0){
                leastDigit = 26;
                n--;
            }
            s.push(leastDigit);
        }
        if(n != 0){
            s.push(n);
        }
        string ss;
        while(s.empty() == false){
            char c = s.top() + 'A' - 1;
            ss.push_back(c);
            s.pop();
        }
        return ss;
    }
};

Selection_007

9/7/2015 update

A cleaner solution, make use of insert function in string class.

class Solution {
public:
    string convertToTitle(int n) {
        string s;
        int remainder = 0;
        while(n > 0){
            remainder = n % 26;
            n = n / 26;
            if(remainder == 0){
                remainder = 26;
                n--;
            }
            s.insert(0, 1, remainder + 'A' - 1);
        }
        return s;
    }
};

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.