1. 题目
1.1 英文题目
Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.
1.2 中文题目
给你一个字符串 columnTitle ,表示 Excel 表格中的列名称。返回该列名称对应的列序号。
1.3输入输出
输入 | 输出 |
---|---|
columnTitle = "A" | 1 |
columnTitle = "AB" | 28 |
columnTitle = "ZY" | 701 |
columnTitle = "FXSHRXW" | 2147483647 |
1.4 约束条件
- 1 <= columnTitle.length <= 7
- columnTitle consists only of uppercase English letters.
- columnTitle is in the range ["A", "FXSHRXW"].
2. 分析
2.1 一般算法
这道题类似于26进制转化为十进制的问题,因此可以类比进制转换的“加权求和法”,具体代码如下:
class Solution {
public:
int titleToNumber(string columnTitle) {
int num = 0;
for (int i = columnTitle.size() - 1; i >= 0; i--) {
num += (columnTitle[i] - 'A' + 1) * pow(26, columnTitle.size() - 1 - i);
}
return num;
}
};
2.2 优化求和算法
考虑到pow函数时间复杂度较高,可利用递推进行求解。代码如下:
class Solution {
public:
int titleToNumber(string columnTitle) {
int num = 0;
for (int i = 0; i < columnTitle.size(); i++) {
num = columnTitle[i] - 'A' + 1 + num * 26;
}
return num;
}
};
2.2 c++11优化算法
对于循环部分,可以用c++11进行优化。代码如下:
class Solution {
public:
int titleToNumber(string columnTitle) {
int num = 0;
for (auto element:columnTitle) {
num = element - 'A' + 1 + num * 26;
}
return num;
}
};