type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给出一个字符串
columnTitle,表示Excel表格中的列名称。返回该列名称对应的列序号。例如:
示例 1:
示例 2:
示例 3:
提示:
1 <= columnTitle.length <= 7
columnTitle仅由大写英文组成
columnTitle在范围["A", "FXSHRXW"]内
解法一:从左到右当成 26 进制累加(推荐)
这题就是把一个“没有 0 的 26 进制字符串”转成十进制整数。
已知 “A” 是 1,“B” 是 2"AB" = 1×26¹ + 2×26⁰ = 26 + 2 = 28
类比于十进制字符串
"123" :- 一开始是 0
- 看见
1:变成 1
- 看见
2:旧结果 ×10 + 2 = 12
- 看见
3:旧结果 ×10 + 3 = 123
搬到 26 进制:
“当前结果先乘 26,把位权往前推一位,再加上这一位代表的数字。”
唯一的区别是:
- 十进制里字符
'0' ~ '9'对应 0~9;
- 这里
'A' ~ 'Z'对应 1~26,没有 0;
所以字母转数字要用
ord(c) - ord('A') + 1。整体思路:从左往右扫,每看到一个字符,就把结果“乘一位 + 本位值”。
复杂度
- 时间:O(n),n 是字符串长度,遍历一遍。
- 空间:O(1),只用到常数个变量。
解法二:从右到左,幂展开
把数学公式
∑(k_i * 26^i) 直接翻译成代码对于 FXSHRXW把每一位的字母都映射成数字:[6,24,19,8,18,24,23]result = 23×26⁰ + 24×26¹ + 18×26² + 8×26³ + 19×26⁴ + 24×26⁵ + 6×26⁶
很自然的做法就是:
- 从右边开始处理,右边第一位乘 26⁰;
- 每往左走一位,就让当前的“权重”乘一次 26:
- 一开始
multiple = 1表示 26⁰; - 每往左走一次,
multiple *= 26;
- 当前字母代表的数字
k就加到number += k * multiple里。
复杂度
- 时间:O(n),同样只扫一遍字符串。
- 空间:O(1),几个整数变量而已。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-171-excel-列名转换为数字
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 160] 相交链表
下一篇
[Leetcode 179] 最大数