当前位置：首页 > article >正文

【C++】P1765 手机

article 2025/2/4 16:29:18

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯问题描述
- 题目内容
- - 示例：
- 键盘布局
💯我的做法
- 思路
- 问题与优化
- 我的代码实现
- 分析与问题
💯老师的做法
- 思路
- 老师的代码实现
- 分析
- 优点
💯对比与总结
- 相同点
- 不同点
💯扩展
- 1. **扩展键盘布局**：
- 2. **空间优化**：
💯小结

在这里插入图片描述

💯前言

在这篇文章中，我们将分析一个关于手机键盘按键次数计算的问题。通过对比两种不同的解法——自己的解法和老师的解法，深入理解这个问题的本质，优化思路，并通过一些技术细节扩展来提升解决方案的效率和可读性。
C++ 参考手册

💯问题描述

P1765 手机
在这里插入图片描述

题目内容

题目要求我们计算在普通手机键盘上输入一个句子所需要的最少按键次数。每个数字键对应多个字母，而按下相同数字键的次数决定了字符的输出。比如，要输入字母 x，就需要按数字键 9 两次。输入空格时，按键 0 一次即可。

给定输入的句子，我们需要计算出在键盘上打出这个句子所需的按键总数。

输入格式：

一行句子，仅包含英文小写字母和空格，且不超过 200 个字符。

输出格式：

一行一个整数，表示按键盘的总次数。

示例：

输入：

i have a dream

输出：

键盘布局

题目中的手机键盘布局如下所示：

在这里插入图片描述

键盘上每个数字键下有多个字母。对于输入的每个字母，我们要计算它所需要的按键次数。空格对应数字键 0，按一次即可。

💯我的做法

我最初的做法使用了一个逐步推算字符按键次数的方法，采用了基于字符范围判断来计算按键次数。具体做法如下：

思路

通过字符的 ASCII 值来判断字母所属的数字键。
对于每个字符，按下对应的数字键次数根据字符在该数字键中的位置来决定。例如：
- 对于字母 a, b, c，按 1 次键 2；
- 对于字母 d, e, f，按 1 次键 3；
- 对于字母 p, q, r, s，按 4 次键 7；
- 空格需要按 1 次键 0。

问题与优化

我的方法中使用了条件语句来逐步判断每个字符属于哪个数字键，然后根据字母在该键中的位置来推算按键次数。然而，这种方法对于字母的映射并不直观，容易出错，尤其是在处理字母范围时，代码的可维护性较差。

我的代码实现

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    int count = 0;
    getline(cin, s);
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] >= 'a' && s[i] <= 'o')
        {
            count += (((s[i] - 'a') % 3) + 1);
        }
        else if(s[i] >= 'p' && s[i] <= 's')
        {
            count += ((s[i] - 'o') % 5);
        }
        else if(s[i] >= 't' && s[i] <= 'v')
        {
            count += ((s[i] - 's') % 4);
        }
        else if(s[i] >= 'w' && s[i] <= 'z')
        {
            count += ((s[i] - 'v') % 5);
        }
        else
        {
            count += 1;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

分析与问题

条件判断繁琐：每个字符根据其范围被分配到不同的按键次数，这种方法比较冗长且容易出错，特别是在字符范围的界定上。
维护困难：如果要扩展或修改键盘布局，修改代码的地方会很多，维护起来不方便。

💯老师的做法

老师的做法则采用了更简洁且高效的解决方案。通过定义一个数组 count 来映射每个字母到它所需的按键次数。每个字母的按键次数在数组中已经预先设定好。

思路

使用数组 count[26] 来记录每个字母的按键次数，字母的索引是通过 c - 'a' 计算的。
遍历输入的句子，对于每个字符，如果是空格，则加 1；如果是字母，则直接根据 count 数组的值进行累加。

老师的代码实现

在这里插入图片描述

#include <iostream>
#include <string>
using namespace std;

int count[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4}; 

int main()
{
    string s;
    int sum = 0;
    getline(cin, s);
    for(auto c : s)
    {
        if(c == ' ') 
            sum += 1; // 空格只需按一次0
        else
            sum += count[c - 'a']; // 字母的按键次数
    }
    cout << sum << endl;
    return 0;
}

分析

简洁高效：通过数组 count 预设每个字母的按键次数，避免了多次条件判断，使得代码更加简洁。
时间复杂度 O(n)：遍历字符串并通过数组索引查找按键次数，时间复杂度为 O(n)，其中 n 是输入句子的长度。
可扩展性好：如果要改变按键布局，只需要修改 count 数组即可，不需要修改逻辑代码，维护起来更加方便。

优点

通过数组直接映射字母到按键次数，减少了代码的复杂度。
代码逻辑清晰，容易理解，并且易于扩展。

💯对比与总结

相同点

目标一致：两者的目标都是计算出输入句子的按键次数。
逐字符遍历：两者都遍历了输入的每个字符，并根据字符计算按键次数。

不同点

实现方式：
- 我的做法通过条件判断字符的范围来计算按键次数，代码较长且复杂。
- 老师的做法通过预设数组来直接获取每个字母的按键次数，代码简洁且高效。
代码可读性与维护性：
- 我的代码虽然能完成任务，但由于存在多个条件判断，代码不易扩展和维护。
- 老师的代码通过数组映射的方式，代码更加简洁，易于维护和修改。
执行效率：
- 两者的时间复杂度均为 O(n)，但是老师的做法由于减少了条件判断，执行效率略高。