数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找应用操作后的字典序最小字符串
假设我们有一个只包含数字字符的字符串 s，以及两个值 a 和 b。我们可以对 s 应用以下两种操作中的任意一种，任意次数，并且可以按任意顺序进行：
将 'a' 加到 s 的所有奇数位置的项 (从 0 开始索引)。如果数字是 9，则添加任何值后会循环回 0。
将 's' 向右旋转 b 个位置。
因此，我们必须找到通过对 s 应用上述操作任意多次可以获得的字典序最小字符串。
例如，如果输入为 s = "5323" a = 9 b = 2，则输出为 2050，因为如果我们按照以下步骤：
- 旋转："5323"
- 添加："5222"
- 添加："5121"
- 旋转："2151"
- 添加："2050"
为了解决这个问题，我们将遵循以下步骤：
- seen := 一个新的集合
- deq := 一个新的队列，其中包含一个元素 's'
- 当 deq 不为空时，执行以下操作：
- curr := 从 deq 中删除的第一个元素
- 将 curr 插入 seen 集合
- ad := 对 curr 执行给定的加法操作
- 如果 ad 不在 seen 中，则
- 将 ad 插入 deq 的末尾
- 将 ad 插入 seen 集合
- ro := 对 curr 执行旋转操作
- 如果 ro 不在 seen 中，则
- 将 ro 插入 deq 的末尾
- 将 ro 插入 seen 集合
- 返回 seen 的最小值
示例
让我们看看下面的实现，以便更好地理解：
from collections import deque def add_(s,a): res = '' for idx, i in enumerate(s): if idx % 2 == 1: num = (int(i) + a) % 10 res += str(num) else: res += i return res def rotate_(s, b): idx = len(s)-b res = s[idx:] + s[0:idx] return res def solve(s, a, b): seen = set() deq = deque([s]) while deq: curr = deq.popleft() seen.add(curr) ad = add_(curr, a) if ad not in seen: deq.append(ad) seen.add(ad) ro = rotate_(curr, b) if ro not in seen: deq.append(ro) seen.add(ro) return min(seen) s = "5323" a = 9 b = 2 print(solve(s, a, b))
输入
"5323", 9, 2
输出
2050
更新于：2021年10月5日
浏览量：227
广告