This is the 29th day of my participation in the genwen Challenge

Topic describes

Given an integer columnNumber, return its corresponding column name in the Excel table.

Such as:

A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28
Copy the code

Example 1:

Input: columnNumber = 1 Output: "A"Copy the code

Example 2:

Input: columnNumber = 28 Output: "AB"Copy the code

Example 3:

Input: columnNumber = 701Copy the code

Example 4:

Input: columnNumber = 2147483647 Output: "FXSHRXW"Copy the code

Tip:

  • 1 < =columnNumber< = 231-1

Their thinking

This can be viewed as a 26 – base conversion problem. A base 26 number can be expressed as:


a 1 x 2 6 0 + a 2 x 2 6 1 + a 3 x 2 6 2 + a 4 x 2 6 3 + . . . = n A_1 \times 26^0 + a_2 \times 26^1 + a_3 \times 26^2 + a_4 × 26^3 +… = n

If we do the same thing as 26 for both sides, we get a1a_1a1. Then divide both sides by 26, so that cancels out the a1a_1A1 term, and this becomes:


0 + a 2 x 2 6 0 + a 3 x 2 6 1 + a 4 x 2 6 2 + . . . = n / 26 0 + a_2 \times 26^0 + a_3 \times 26^1 + a_4 \times 26^2 + … = n / 26

Therefore, we can continue to carry out the operation of same module and same division to the above formula, obtaining and eliminating the lowest term each time, until NNN becomes 0.

Another thing to notice in this case is that the column names in this problem don’t have zeros. When you get to 26, you’re supposed to round up and fill in 0, but in this case 26 is Z. So a1a_1a1, a2a_2a2, a3a_3a3… The range of values of is 1-26 (corresponding to a-z), while the range of modulo of 26 is 0-25. This results in 26 modulo 26 to 0, and when you divide both sides by 26, you cannot eliminate the lowest term (26/26 = 1). To solve this problem, we can subtract 1 from n in the same module and same division operations. In this way, the correctness of the process of obtaining and eliminating the lowest terms is guaranteed.

code

C++

class Solution {
public:
    string convertToTitle(int columnNumber) {
        int n = columnNumber;
        string ans;
        while (n > 0) {
            ans += (n - 1) % 26 + 'A';
            n = (n - 1) / 26;
        }
        reverse(ans.begin(), ans.end());
        returnans; }};Copy the code

Another way to write it

class Solution {
public:
  string convertToTitle(int columnNumber) {
    string res;
    while (columnNumber > 26) {
      res = (char) ('A' + (columnNumber - 1) % 26) + res;
      columnNumber = (columnNumber - 1) / 26;
    }
    return (char) ('A' + columnNumber - 1) + res; }};Copy the code