网站平台建设需求的意见,网络公司 营销型网站,重庆网站供奉战犯,怎样上百度做广告给你一个字符串 word#xff0c;由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射#xff0c;可以通过按压按键来组成单词。例如#xff0c;按键 2 对应 [a,b,c]#xff0c;我们需要按一次键来输入 由 不同 小写英文字母组成。
电话键盘上的按键与 不同 小写英文字母集合相映射可以通过按压按键来组成单词。例如按键 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 个。更新总成本并减少剩余字母数量。重复上述过程直到所有字母都被分配。
