济南做微网站推广2023年7月最新新闻摘抄
给你一个字符串 word，由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。
现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。
返回重新映射按键后输入 word 所需的 最少 按键次数。
下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。
示例 1：
输入：word = "abcde" 输出：5 解释：图片中给出的重新映射方案的输入成本最小。 "a" -> 在按键 2 上按一次 "b" -> 在按键 3 上按一次 "c" -> 在按键 4 上按一次 "d" -> 在按键 5 上按一次 "e" -> 在按键 6 上按一次 总成本为 1 + 1 + 1 + 1 + 1 = 5 。 可以证明不存在其他成本更低的映射方案。
示例 2：
输入：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 。 可以证明不存在其他成本更低的映射方案。
题解：
class Solution:def minimumPushes(self, word: str) -> int:a, b = divmod(len(word), 8)return ((a << 2) + b) * (a + 1)class Solution:def minimumPushes(self, word: str) -> int:n = len(word)keys = 8 # 按键数量，从2到9total = 0position = 1 # 当前按键位置，从1开始remaining = nwhile remaining > 0:# 每一层最多可以分配到8个字母assign = min(keys, remaining)total += assign * positionremaining -= assignposition += 1return total
解题思路
为了最小化总按键次数，我们应尽可能将更多的字母分配到各按键的前几个位置。具体步骤如下：
确定按键数量：
- 有
8个按键（编号2到9）。分配字母到按键的位置：
- 首先，尽可能多地将字母分配到每个按键的第一个位置（每个按键最多一个字母，成本为
1）。- 如果字母数量超过
8，则将剩余的字母分配到按键的第二个位置（每个按键最多一个字母，成本为2）。- 依此类推，直到所有字母都被分配。
计算总成本：
- 对于每一层（即每个按键的位置），计算分配到该层的字母数量与其对应的成本，然后累加。
实现步骤
初始化变量：
n：字符串word的长度。keys：按键的数量，即8。total：总成本，初始为0。position：当前分配的按键位置，初始为1。remaining：剩余未分配的字母数量，初始为n。循环分配字母：
- 在每一层（按键位置）中，分配尽可能多的字母（最多
8个）。- 计算分配到当前层的字母数量
assign，即min(keys, remaining)。- 更新总成本：
total += assign * position。- 减少剩余字母数量：
remaining -= assign。- 移动到下一层：
position += 1。返回结果：
- 循环结束后，返回
total作为最小按键总成本。代码说明
函数
minimumPushes：
- 接受一个字符串
word。- 计算并返回重新映射后输入该
word所需的最少按键次数。- 使用贪心策略，优先将字母分配到每个按键的前几个位置，以降低总成本。
变量解释：
n：字符串word的长度。keys：按键数量（编号2到9共8个）。total：总按键次数。position：当前分配的按键位置（第几次按键）。remaining：剩余未分配的字母数量。逻辑流程：
- 在每一层（按键位置）中，尽可能多地分配字母（最多
8个）。- 更新总成本，并减少剩余字母数量。
- 重复上述过程，直到所有字母都被分配。