Leetcode No.171 Excel表列序号

题目描述

给定一个Excel表格中的列名称，返回其相应的列序号。

例如，

A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...

示例 1: 输入: "A" 输出: 1

示例 2: 输入: "AB" 输出: 28

示例 3: 输入: "ZY" 输出: 701

解题思路1

字符串遍历，进制转换 初始化结果 ans = 0，遍历时将每个字母与 A 做减法，因为 A 表示 1，所以减法后需要每个数加 1，计算其代表的数值 num = 字母 - ‘A’ + 1 因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位 所以每遍历一位则ans = ans * 26 + num 以 ZY 为例，Z 的值为 26，Y 的值为 25，则结果为 26 * 26 + 25=701

class Solution {
    public int titleToNumber(String s) {
        int ans = 0;
        for(int i=0;i<s.length();i++) {
            int num = s.charAt(i) - 'A' + 1;
            ans = ans * 26 + num;
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

解题思路2

字符串遍历，进制转换 初始化结果 ans = 0，遍历时将每个字母与 A 做减法，因为 A 表示 1，所以减法后需要每个数加 1，计算其代表的数值 num = 字母 - ‘A’ + 1 因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位

每位实际数值为num*26^(位数)

以 ZY 为例，Z 的值为 26*26^1，Y 的值为 25*26^0，则结果为 26*26^1 + 25*26^0=701

class Solution {
    public int titleToNumber(String columnTitle) {
        int len=columnTitle.length();
        int rs=0;
        for(int i=len-1;i>=0;i--){
            char ch=columnTitle.charAt(i);
            rs=rs+(ch-'A'+1)*fun(len-1-i);
        }
        return rs;
    }
    int fun(int n){
        int rs=1;
        while(n>0){
            rs*=26;
            n--;
        }
        return rs;
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)