E卷-刷题笔记合集🔗

九宫格按键输入

问题描述

九宫格按键输入是一种常见的文字输入方法。本题要求实现一个九宫格按键输入系统，该系统有英文和数字两种模式。默认为数字模式，数字模式下直接输出按键对应的数字。英文模式下，连续按同一个按键会依次出现该按键上的字母。如果输入"/"或其他字符，则当前字母输入循环中断。

九宫格按键字符对应关系如下：

+---+---+---+
| 1 | 2 | 3 |
| . |abc|def|
+---+---+---+
| 4 | 5 | 6 |
|ghi|jkl|mno|
+---+---+---+
| 7 | 8 | 9 |
|pqrs|tuv|wxyz|
+---+---+---+
| * | 0 | # |
|   |   |   |
+---+---+---+

输入格式

输入为一行字符串，包含数字 和字符 '#'、'/'。

输出格式

输出一行字符串，表示屏幕显示的内容。

样例输入1

123#222235/56

样例输出1

123adjjm

样例输入2

22/222

样例输出2

bc

样例输入3

22222

样例输出3

b

样例解释

数据范围

• 输入字符串长度：

题解

模拟

这道题目模拟了九宫格按键输入系统。核心思路如下：

1. 使用一个栈来存储输入的字符和中间结果。
2. 用一个变量 isEng 来跟踪当前是否处于英文模式。
3. 用 topRepeat 记录当前按键的重复次数（仅在英文模式下有效）。
4. 遍历输入字符串，根据不同的输入字符进行相应处理：
   • '#': 切换模式
   • '/': 中断当前输入
   • 数字: 根据当前模式进行处理

关键点在于正确处理模式切换和循环中断，特别是在英文模式下连续按同一个键的情况。

时间复杂度为 O(n)，其中 n 是输入字符串的长度。空间复杂度也是 O(n)，主要用于存储结果。

参考代码

• Python

def process_input(s):
    stack = []
    top_repeat = 0
    is_eng = False
    dictionary = (" ", ",.", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")

    def mapping(c, repeat):
        num = int(c)
        s1 = dictionary[num]
        i = (repeat - 1) % len(s1)
        return s1[i]

    def interrupt():
        nonlocal top_repeat
        if not is_eng or not stack or top_repeat == 0:
            return
        stack.append(mapping(stack.pop(), top_repeat))
        top_repeat = 0

    for c in s + " ":  # 添加空格作为结束标记
        if c == '#':
            interrupt()
            is_eng = not is_eng
        elif c == '/':
            interrupt()
        else:
            if not is_eng:
                stack.append(c)
            else:
                if top_repeat == 0:
                    stack.append(c)
                    top_repeat += 1
                elif c != stack[-1]:
                    interrupt()
                    stack.append(c)
                    top_repeat = 1
                else:
                    top_repeat += 1

    return "".join(stack)

# 读取输入并处理
input_string = input().strip()
print(process_input(input_string))

• C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_LEN 1001

const char* dictionary[] = {" ", ",.", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

char mapping(char c, int repeat) {
    int num = c - '0';
    const char* s1 = dictionary[num];
    int len = strlen(s1);
    return s1[(repeat - 1) % len];
}

void interrupt(char* stack, int* top, int* top_repeat, bool is_eng) {
    if (!is_eng || *top == 0 || *top_repeat == 0) return;
    stack[*top - 1] = mapping(stack[*top - 1], *top_repeat);
    *top_repeat = 0;
}

void process_input(const char* input, char* output) {
    char stack[MAX_LEN];
    int top = 0, top_repeat = 0;
    bool is_eng = false;

    for (int i = 0; input[i] != '\0'; i++) {
        char c = input[i];
        if (c == '#') {
            interrupt(stack, &top, &top_repeat, is_eng);
            is_eng = !is_eng;
        } else if (c == '/') {
            interrupt(stack, &top, &top_repeat, is_eng);
        } else {
            if (!is_eng) {
                stack[top++] = c;
            } else {
                if (top_repeat == 0) {
                    stack[top++] = c;
                    top_repeat = 1;
                } else if (c != stack[top - 1]) {
                    interrupt(stack, &top, &top_repeat, is_eng);
                    stack[top++] = c;
                    top_repeat = 1;
                } else {
                    top_repeat++;
                }
            }
        }
    }
    interrupt(stack, &top, &top_repeat, i