Fork me on GitHub

leetcode之171. Excel表列序号

发表于 | 分类于
字数统计 448 字 | 阅读时长 2 分钟

题目描述：

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

例如，

1
2
3
4
5
6
7
8
9
>     A -> 1
>     B -> 2
>     C -> 3
>     ...
>     Z -> 26
>     AA -> 27
>     AB -> 28 
>     ...
>

示例 1:

1
2
3
> 输入: "A"
> 输出: 1
>

示例 2:

1
2
3
> 输入: "AB"
> 输出: 28
>

示例 3:

1
2
3
> 输入: "ZY"
> 输出: 701
>

解题思路一：

时间复杂度：$O(n)$,空间复杂度:$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int titleToNumber(string s) {
        map<char, int> mp;
        int count = 0, m = 0;
        int n = 0;
        
        if(s.length() <= 0) return -1;
        
        for(int i = 0; i < 26; i++)
        {
            if(!mp.count('A' + i))
            {
                n++;
                mp['A' + i] = n;
            }
            
        }

         for(int j = s.length() - 1; j >= 0; j--)
        {
            //最后一位只需加上自身就行
            if( j == s.length() - 1)
                count += mp[s[j]];
            
            else
            {
                m++; 
                count += mp[s[j]] * (pow(26,m)); 
            }
        }

         return count;
        
    }
};

解题思路二：

时间复杂度：$O(n)$,空间复杂度:$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int titleToNumber(string s) {
        map<char, int> mp;
        int count = 0, m = 0;
        int n = 0;
        
        if(s.length() <= 0) return -1;
        
        for(int i = 0; i < 26; i++)
        {
            if(!mp.count('A' + i))
            {
                n++;
                mp['A' + i] = n;
            }

            
        }

         for(int j = s.length() - 1; j >= 0; j--)
        {
            count += mp[s[j]] * pow(26,m);
            m++;
        }
        
        return count;
        
    }
};

解题思路三：

时间复杂度：$O(n)$,空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//改进版本2
class Solution {
public:
    int titleToNumber(string s) {
        int count = 0, m = 0;
       
        if(s.length() <= 0) return -1;
        
        for(int j = s.length() - 1; j >= 0; j--)
        {
            count += (s[j] - 'A' + 1) * pow(26,m);
            m++;
        }
        
        return count;
        
    }
};

解题思路四：

时间复杂度：$O(n)$,空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//改进版本3
class Solution {
public:
    int titleToNumber(string s) {
        int count = 0;
       
        if(s.length() <= 0) return -1;
        
        for(int j = s.length() - 1; j >= 0; j--)
        {
            count += (s[j] - 'A' + 1) * pow(26,s.length() - j - 1);
            
        }
        
        return count;
        
    }
};