[Leetcode 171] Excel 列名转换为数字

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),几个整数变量而已。
上一篇
[Leetcode 160] 相交链表
下一篇
[Leetcode 179] 最大数