华为OD机试 - 九宫格按键输入 - 逻辑分析（Java 2023 B卷 200分）

题目描述

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

输入描述

输入范围为数字0~9和字符#、/。输出屏幕显示。例如在数字模式下，输入1234，显示1234；在英文模式下，输入1234，显示,adg。

输出描述

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

解题思路

这个问题可以通过状态机来解决。我们需要维护当前模式（数字模式或英文模式）以及当前按键的连续按击次数。根据输入字符的不同，我们更新状态并生成相应的输出。

代码实现

Java

import java.util.*;

public class NineKeyInput {
    private static final String[] DIGITS = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
    private static final String[] LETTERS = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public String processInput(String input) {
        boolean isNumberMode = true;
        StringBuilder output = new StringBuilder();
        int index = 0;
        while (index < input.length()) {
            char ch = input.charAt(index);
            if (ch == '#') {
                isNumberMode = !isNumberMode;
                index++;
            } else if (ch == '/') {
                index++;
            } else if (Character.isDigit(ch)) {
                int digit = ch - '0';
                if (isNumberMode) {
                    output.append(DIGITS[digit]);
                    index++;
                } else {
                    int count = 0;
                    while (index < input.length() && input.charAt(index) == ch) {
                        count++;
                        index++;
                    }
                    String letters = LETTERS[digit];
                    output.append(letters.charAt((count - 1) % letters.length()));
                }
            } else {
                index++;
            }
        }
        return output.toString();
    }

    public static void main(String[] args) {
        NineKeyInput processor = new NineKeyInput();
        System.out.println(processor.processInput("123#222235/56")); // 123adjjm
    }
}

Python

class NineKeyInput:
    DIGITS = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
    LETTERS = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    def process_input(self, input_str):
        is_number_mode = True
        output = []
        index = 0
        while index < len(input_str):
            ch = input_str[index]
            if ch == '#':
                is_number_mode = not is_number_mode
                index += 1
            elif ch == '/':
                index += 1
            elif ch.isdigit():
                digit = int(ch)
                if is_number_mode:
                    output.append(self.DIGITS[digit])
                    index += 1
                else:
                    count = 0
                    while index < len(input_str) and input_str[index] == ch:
                        count += 1
                        index += 1
                    letters = self.LETTERS[digit]
                    output.append(letters[(count - 1) % len(letters)])
            else:
                index += 1
        return ''.join(output)

processor = NineKeyInput()
print(processor.process_input("123#222235/56"))  # 123adjjm

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class NineKeyInput {
private:
    vector<string> DIGITS = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
    vector<string> LETTERS = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    string processInput(string input) {
        bool isNumberMode = true;
        string output;
        int index = 0;
        while (index < input.length()) {
            char ch = input[index];
            if (ch == '#') {
                isNumberMode = !isNumberMode;
                index++;
            } else if (ch == '/') {
                index++;
            } else if (isdigit(ch)) {
                int digit = ch - '0';
                if (isNumberMode) {
                    output += DIGITS[digit];
                    index++;
                } else {
                    int count = 0;
                    while (index < input.length() && input[index] == ch) {
                        count++;
                        index++;
                    }
                    string letters = LETTERS[digit];
                    output += letters[(count - 1) % letters.length()];
                }
            } else {
                index++;
            }
        }
        return output;
    }
};

int main() {
    NineKeyInput processor;
    cout << processor.processInput("123#222235/56") << endl; // 123adjjm
    return 0;
}

JavaScript

class NineKeyInput {
    constructor() {
        this.DIGITS = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];
        this.LETTERS = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    }

    processInput(input) {
        let isNumberMode = true;
        let output = '';
        let index = 0;
        while (index < input.length) {
            const ch = input[index];
            if (ch === '#') {
                isNumberMode = !isNumberMode;
                index++;
            } else if (ch === '/') {
                index++;
            } else if (/\d/.test(ch)) {
                const digit = parseInt(ch);
                if (isNumberMode) {
                    output += this.DIGITS[digit];
                    index++;
                } else {
                    let count = 0;
                    while (index < input.length && input[index] === ch) {
                        count++;
                        index++;
                    }
                    const letters = this.LETTERS[digit];
                    output += letters[(count - 1) % letters.length];
                }
            } else {
                index++;
            }
        }
        return output;
    }
}

const processor = new NineKeyInput();
console.log(processor.processInput("123#222235/56")); // 123adjjm

复杂度分析

• 时间复杂度: O(n)，其中n是输入字符串的长度。我们需要遍历整个字符串一次来处理每个字符。
• 空间复杂度: O(1)，除了输出字符串外，我们只使用了常数空间来存储模式和当前按键的连续按击次数。

总结

我们使用了状态机来处理这个问题，通过维护当前模式和按键的连续按击次数，能够有效地生成相应的输出。这种方法简单直观，适用于处理这种模式切换和按键映射的问题。