刷题笔记合集🔗

九宫格按键输入

问题描述

九宫格按键输入，输出显示内容，有英文和数字两个模式，默认是数字模式，数字模式直接输出数字，英文模式连续按同一个按键会依次出现这个按键上的字母，如果输入"/"或者其他字符，则循环中断。

字符对应关系如下：

• 按键 1 对应：",."
• 按键 2 对应："abc"
• 按键 3 对应："def"
• 按键 4 对应："ghi"
• 按键 5 对应："jkl"
• 按键 6 对应："mno"
• 按键 7 对应："pqrs"
• 按键 8 对应："tuv"
• 按键 9 对应："wxyz"
• 按键 0 对应：" "（空格）

要求输入一串按键，输出屏幕显示内容。

输入格式

输入范围为数字 和字符'#'、'/'。

输出格式

输出屏幕显示的内容。说明：

• '#'用于切换模式，默认是数字模式，执行'#'后切换为英文模式；
• '/'表示延迟，例如在英文模式下，输入 22/222，显示为 bc；
• 英文模式下，多次按同一键，例如输入 22222，显示为 b。

样例输入

123#222235/56

样例输出

123adjjm

数据范围

• 输入字符数不超过
• 输入只包含数字 和字符'#'、'/'

题解

这道题是模拟九宫格键盘输入的问题，关键在于理解模式切换和输入逻辑。

首先，我们需要解析题目给出的九宫格按键规则：

1. 有数字模式和英文模式两种状态
2. 默认是数字模式，数字模式直接输出数字
3. '#'用于切换模式
4. 英文模式下，连续按同一个按键会循环显示该按键上的字母
5. '/'或其他非当前按键字符表示循环中断

实现这个问题的关键是正确处理状态切换和循环中断。一个简单而有效的方法是使用栈结构来处理：

1. 使用一个栈来存储输出结果
2. 使用一个布尔变量记录当前是否为英文模式
3. 使用一个计数器记录当前按键的重复次数

处理逻辑如下：

• 如果遇到'#'，先处理可能的循环中断，然后切换模式
• 如果遇到'/'，处理循环中断
• 对于其他字符：
  • 数字模式下直接加入栈
  • 英文模式下，检查是否与上一个按键相同
    • 如果相同，增加重复计数
    • 如果不同，处理循环中断，然后将新按键加入栈

循环中断的处理：

• 如果当前是英文模式且有重复计数
• 根据重复次数确定应显示的字母
• 将栈顶元素替换为对应字母

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

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
s = input()

# 字符映射表
char_map = [" ", ",.", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

def solve_keypad_input(s):
    # 添加一个空格作为最后的处理触发器
    s += " "
    
    # 初始化变量
    stack = []
    is_eng_mode = False  # 默认是数字模式
    repeat_count = 0     # 重复次数
    
    for c in s:
        if c == '#':
            # 处理循环中断
            handle_interrupt(stack, is_eng_mode, repeat_count)
            # 切换模式
            is_eng_mode = not is_eng_mode
            repeat_count = 0
        elif c == '/':
            # 处理循环中断
            handle_interrupt(stack, is_eng_mode, repeat_count)
            repeat_count = 0
        else:
            # 数字模式
            if not is_eng_mode:
                # 数字模式直接输出数字
                if c.isdigit():
                    stack.append(c)
            else:
                # 英文模式
                if c.isdigit():
                    # 如果栈为空或者没有正在重复的字符
                    if not stack or repeat_count == 0:
                        stack.append(c)
                        repeat_count = 1
                    # 检查是否与上一个字符相同
                    elif stack[-1] == c:
                        repeat_count += 1
                    else:
                        # 不同字符，处理之前的输入
                        handle_interrupt(stack, is_eng_mode, repeat_count)
                        stack.append(c)
                        repeat_count = 1
    
    # 移除最后添加的空格处理
    return ''.join(stack[:-1])

def handle_interrupt(stack, is_eng_mode, repeat_count):
    # 只有在英文模式且有重复按键的情况下才需处理
    if is_eng_mode and stack and repeat_count > 0:
        # 获取最后的数字
        digit = int(stack.pop())
        # 获取对应的字符
        chars = char_map[digit]
        # 计算应显示的字符索引（循环）
        idx = (repeat_count - 1) % len(chars)
        # 添加对应字符
        stack.append(chars[idx])

# 调用并输出
print(solve_keypad_input(s))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 字符映射表
const string char_map[] = {" ", ",.", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

// 处理循环中断
void handleInterrupt(vector<char>& stack, bool isEngMode, int& repeatCount) {
    // 只有在英文模式且有重复按键的情况下才需处理
    if (isEngMode && !stack.empty() && repeatCount > 0) {
        // 获取最后的数字
        char lastChar = stack.back();
        stack.pop_b