LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对于十进制整数转字符串过程为

31542
=> % 10 = 2，/10 = 3154
=> % 10 = 4，/10 = 315
=> % 10 = 5，/10 = 31
=> % 10 = 1，/10 = 3
=> % 10 = 3，/10 = 0
          |
      31542 ← 依次添加到首字符

• 需要注意的是，这道题从 1 开始计数，每个位置可以表示的值不能为 0

A  // 1
Z  // 26
AA // 27 = 1 * 26 + 1
AZ // 52 = 1 * 26 + 26 = 2 * 26，不能写为 B0
BA // 53 = 2 * 26 + 1
BZ // 78 = 2 * 26 + 26 = 3 * 26，不能写为 C0
ZZ // 702 = 26 * 26 + 26 = 27 * 26

702
=> % 26 = 0，/26 = 27
=> % 26 = 1，/26 = 1
=> % 26 = 1, /26 = 0
          |
        AA0，错误，不能有 0

• 因此如果得到余数为 0，则用 Z 填充，再将原有的数减掉 26 即可

702 = 27 * 26
=> % 26 = 0，(702 - 26) / 26 = 702 / 26 - 1 = 26
=> % 26 = 0，(26 - 26) /26 = 26 / 26 - 1 = 0
          |
         ZZ = 26 * 26 + 26

701 = 26 * 26 + 25
=> % 26 = 25，/26 = 26
=> % 26 = 0 ，26 / 26 - 1 = 0
          |
         ZY = 26 * 26 + 25

• 解法如下

class Solution {
 public:
  string convertToTitle(int columnNumber) {
    string res;
    while (columnNumber) {
      int t = columnNumber % 26;
      if (!t) {
        res.insert(begin(res), 'Z');
        columnNumber = columnNumber / 26 - 1;
      } else {
        res.insert(begin(res), 'A' + t - 1);
        columnNumber /= 26;
      }
    }
    return res;
  }
};

• 也可以在求余数前先将原有的数减一，这样如果余数为 0 则用 A 填充，余数为 25 则用 Z 填充

class Solution {
 public:
  string convertToTitle(int columnNumber) {
    string res;
    while (columnNumber) {
      --columnNumber;
      int t = columnNumber % 26;
      res.insert(begin(res), 'A' + t);
      columnNumber /= 26;
    }
    return res;
  }
};