题目描述与示例

题目描述

给定一段”密文”字符串s,其中字符都是经过”密码本”映射的,现需要将”密文”解密并且输出。

映射的规则 :"a-i"分别用"1-9"表示,"j-z" 分别用"10*-26*"表示

约束:映射始终唯一

输入描述

“密文”字符串

输出描述

明文字符串

补充说明

翻译后的文本的长度在100以内

示例一

输入

20*19*20*

输出

tst

示例二

输入

12320*12319*20*

输出

abctabcst

解题思路

元素映射

涉及元素一一映射的关系,构建从数字到字母的映射这件事,很容易想到应该使用哈希表来解决

为了构建数字和字母之间的映射,可以使用ASCII码值来完成。使用ord("a")可以计算得到字符"a"的ASCII码值,选定数字i的范围为[1, 26],则ord("a")+i-1可以得到所有小写字母的ASCII码值,再使用chr()内置函数将ASCII码值转换回小写字母,即chr(ord("a")+i-1)。故构建映射关系哈希表的代码为

dic = {str(i): chr(ord("a") + i - 1) for i in range(1, 27)}

两位数的处理

另外,本题所给密码字符串中,两位数(10-26)的后面都会带一个*,而一位数(1-9)的后面不带*,我们必须把这两种情况区分开来。

如果我们从头到尾地遍历原字符串s,每次遇到一个*号,则说明此时*号前面的两个字符需要合并在一起,视为一个两位数来处理。

很显然,只有在遇到*号的时候,才需要去查看刚刚最新遇到的两个数字字符,这是一种后进先出的思路,很显然可以使用栈来处理这个过程。其过程如下

stack = list()

for ch in s:
    if ch == "*":
        digit_1 = stack.pop()
        digit_10 = stack.pop()
        stack.append(digit_10 + digit_1)
    else:
        stack.append(ch)

退出循环后,栈中储存了若干个数字字符串(有一位数也有两位数),再将这些数字字符串传入哈希表中进行从数字到字母的映射,再合并为一个字符串输出即为答案。代码如下

print("".join(dic[num_str] for num_str in stack))

代码

Python

# 题目:【哈希表】2023C-密码解密
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:栈,哈希表
# 代码看不懂的地方,请直接在群上提问


# 构建数字和字母之间的映射关系
dic = {str(i): chr(ord("a") + i - 1) for i in range(1, 27)}

# 输入字符串
s = input()

# 构建一个栈
stack = list()

# 遍历s中所有字符
for ch in s:
    # 如果是*号,说明*前面的两个数字要合并为一个两位数一起考虑
    if ch == "*":
        # 弹出栈顶两个元素,分别是个位和十位的字符串
        # 先弹出个位,再弹出10位
        digit_1 = stack.pop()
        digit_10 = stack.pop()
        # 将合并后的两位数重新压回栈顶
        stack.append(digit_10 + digit_1)
    # 如果不是*号,而是数字,则直接入栈
    else:
        stack.append(ch)

# 最后栈中的所有元素即为数字字符串,使用dic进行从数字到字母的映射之后再合并即可
print("".join(dic[num_str] for num_str in stack))

Java

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // 构建数字和字母之间的映射关系
        HashMap<String, Character> dic = new HashMap<>();
        for (int i = 1; i <= 26; i++) {
            dic.put(Integer.toString(i), (char) ('a' + i - 1));
        }

        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();

        // 构建一个栈
        Stack<String> stack = new Stack<>();

        // 遍历s中所有字符
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 如果是*号,说明*前面的两个数字要合并为一个两位数一起考虑
            if (ch == '*') {
                // 弹出栈顶两个元素,分别是个位和十位的字符串
                // 先弹出个位,再弹出10位
                String digit_1 = stack.pop();
                String digit_10 = stack.pop();
                // 将合并后的两位数重新压回栈顶
                stack.push(digit_10 + digit_1);
            }
            // 如果不是*号,而是数字,则直接入栈
            else {
                stack.push(Character.toString(ch));
            }
        }

        // 最后栈中的所有元素即为数字字符串,使用dic进行从数字到字母的映射之后再合并即可
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            String numStr = stack.pop();
            result.append(dic.get(numStr));
        }

        System.out.println(result.reverse().toString());
    }
}

C++

“`C++
#include <iostream>
#include <unordered_map>
#include <stack>

using namespace std;

int main() {
// 构建数字和字母之间的映射关系
unordered_map<string, char> dic;
for (int i = 1; i <= 26; i++) {
dic[to_string(i)] = 'a' + i – 1;
}

<pre><code>string s;
cin >> s;

// 构建一个栈
stack<string> stack;

// 遍历s中所有字符
for (char ch : s) {
// 如果是*号,说明*前面的两个数字要合并为一个两位数一起考虑
if (ch == '*') {
// 弹出栈顶两个元素,分别是个位和十位的字符串
// 先弹出个位,再弹出10位
string digit_1 = stack.top();
stack.pop();
string digit_10 = stack.top();
stack.pop();
// 将合并后的两位数重新压回栈顶
stack.push(digit_10 + digit_1);
}
// 如果不是*号,而是数字,则直接入栈
else {
stack.push(string(1, ch));
}
}

// 最后栈中的所有元素即为数字字符串,使用dic进行从数字到字母的映射之后再合并即可
string result = "";
while (!stack.empty()) {
string numStr = stack.top();
stack.pop();
result = dic[numStr] + result;
}

// 输出结果
cout << result << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度:O(N)。需要一次遍历字符串s

空间复杂度:O(N)。哈希表所占空间,长度为26,可视为常数级别空间;栈所占空间最大为N

说明

华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。

机试分数越⾼评级越⾼,⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知

关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。