CTF of Z2BNS
0%

解码字母到整数映射

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：

字符（'a' - 'i'）分别用（'1' - '9'）表示。
字符（'j' - 'z'）分别用（'10#' - '26#'）表示。
返回映射之后形成的新字符串。

题目数据保证映射始终唯一。

示例1：

1
2
3
输入：s = "10#11#12"
输出："jkab"
解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

示例2：

1
2
输入：s = "1326#"
输出："acz"

示例3：

1
2
输入：s = "25#"
输出："y"

示例4：

1
2
输入：s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
输出："abcdefghijklmnopqrstuvwxyz"

提示：

  • 1 <= s.length <= 1000
  • s[i] 只包含数字（'0'-'9'）和 '#' 字符。
  • s 是映射始终存在的有效字符串。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

使用map容器存储键值对映射，遍历字符串，判断每个字符后面的第2个字符是否是’#’，如果是则长度为3的子串作为键，否则就是当前字符作为键去map中找值。

c++代码：(执行用时0ms，击败100.00%，内存消耗6.7M，击败18.21%）

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
class Solution {
public:
    string freqAlphabets(string s) {
        string result="";
        map<string,string> m;
        int i;
        int n=s.length();
        string arr1[26]={"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#"};
        string arr2[26]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
        //初始化映射规则
        for(i=0;i<26;++i){
            m[arr1[i]]=arr2[i];
        }
        //遍历字符串s
        for(i=0;i<n;++i){
            //该字符后面第二个字符是#，表示对应字符j-z
            if(i<n-2 && s[i+2]=='#'){
                //截取长度为3的子串
                result+=m[s.substr(i,3)];
                i+=2;
            }else{
                result+=m[s.substr(i,1)];
            }
        }
        return result;

    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：遍历

我们对字符串 s 进行顺序遍历。

当遍历到位置 i 时，我们首先向后看两个字符（即 s[i + 2]），如果 s[i + 2] 存在且为 '#'，那么位置 i，i + 1 和 i + 2 表示一个 'j' 到 'z' 之间的字符，否则位置 i 表示一个 'a' 到 'i' 的字符。

根据对 s[i + 2] 的判断，我们可以使用字符串转整数的方法得到对应的字符的 ASCII 码，从而得到字符本身。在这之后，我们将位置 i 后移，继续进行遍历直到结束。

c++代码：(执行用时0ms，击败100.00%，内存消耗6.4M，击败31.87%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string freqAlphabets(string s) {
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            if (i + 2 < s.size() && s[i + 2] == '#') {
                ans += char((s[i] - '0') * 10 + (s[i + 1] - '1') + 'a');
                i += 2;
            }
            else {
                ans += char(s[i] - '1' + 'a');
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是字符串 s 的长度。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

思路是一样的，利用字符和ASCII之间的转换也挺好，代码比较简洁明了。我用了map容器反而增加了空间复杂度，代码看着比较长😯

------------- THE END! THANKS! -------------