美文网首页
【教3妹学编程-算法题】输入单词需要的最少按键次数 I

【教3妹学编程-算法题】输入单词需要的最少按键次数 I

作者: 程序员小2 | 来源:发表于2024-02-12 16:34 被阅读0次
    瑟瑟发抖

    3妹:2哥,新年好鸭~
    2哥 : 新年好,3妹这么早啊
    3妹:是啊,新年第一天要起早,这样就可以起早一整年
    2哥 :得,我还不了解你,每天晒到日上三竿
    3妹:嘿嘿嘿嘿,一年是有300多天起的比较晚~
    2哥:3妹,过完年什么时候回来啊
    3妹:最少也要初七吧,好不容易回家一趟多陪陪父母。
    2哥:好吧,回家也也要记得每天刷题啊,今天有一道“最少”的题目, 让我们先做一下吧~

    吃瓜

    题目:

    给你一个字符串 word,由 不同 小写英文字母组成。

    电话键盘上的按键与 不同 小写英文字母集合相映射,可以通过按压按键来组成单词。例如,按键 2 对应 ["a","b","c"],我们需要按一次键来输入 "a",按两次键来输入 "b",按三次键来输入 "c"。

    现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母,但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。

    返回重新映射按键后输入 word 所需的 最少 按键次数。

    下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1,*,# 和 0 不 对应任何字母。


    image.png

    示例 1:


    image.png
    输入:word = "abcde"
    输出:5

    解释:图片中给出的重新映射方案的输入成本最小。
    "a" -> 在按键 2 上按一次
    "b" -> 在按键 3 上按一次
    "c" -> 在按键 4 上按一次
    "d" -> 在按键 5 上按一次
    "e" -> 在按键 6 上按一次
    总成本为 1 + 1 + 1 + 1 + 1 = 5 。
    可以证明不存在其他成本更低的映射方案。

    示例 2:


    image.png

    输入:word = "xycdefghij"
    输出:12
    解释:图片中给出的重新映射方案的输入成本最小。
    "x" -> 在按键 2 上按一次
    "y" -> 在按键 2 上按两次
    "c" -> 在按键 3 上按一次
    "d" -> 在按键 3 上按两次
    "e" -> 在按键 4 上按一次
    "f" -> 在按键 5 上按一次
    "g" -> 在按键 6 上按一次
    "h" -> 在按键 7 上按一次
    "i" -> 在按键 8 上按一次
    "j" -> 在按键 9 上按一次
    总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。
    可以证明不存在其他成本更低的映射方案。

    提示:

    1 <= word.length <= 26
    word 仅由小写英文字母组成。
    word 中的所有字母互不相同。

    思路:

    思考

    设 nums\textit{nums}nums 的异或和为 sss。

    由于各个字母互不相同,所以均匀分配到这 8 个按键。

    设字符串长度为 n,k=⌊n/8⌋,那么先分配给每个按键 k 个字母,总按键次数为

    8⋅(1+2+⋯+k)=4k(k+1)
    剩余的 n mod 8个字母需要按 k+1次。

    所以答案为

    4k(k+1)+(n mod 8)(k+1)=(4k+n mod 8)(k+1)

    java代码:

    class Solution {
        public int minimumPushes(String word) {
            int n = word.length();
            int k = n / 8;
            return (k * 4 + n % 8) * (k + 1);
        }
    }
    

    相关文章

      网友评论

          本文标题:【教3妹学编程-算法题】输入单词需要的最少按键次数 I

          本文链接:https://www.haomeiwen.com/subject/yxsdadtx.html