数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找合成字符串中特定索引处的字符
假设，我们给定一个字符串 'input_str'。现在，我们需要确定给定字符串的所有可能的子字符串，然后将所有子字符串按字典序一个接一个地连接到另一个字符串中。我们还提供了一个整数值 k。我们的任务是从连接后的字符串中返回索引 k 处的字符。
因此，如果输入类似于 input_str = 'pqrs'，k = 6，则输出将为 p
给定字符串的按字典序排列的子字符串为 p、pq、pqr、pqrs、q、qr、qrs、r、rs、s。
如果我们连接这些字符串，它将变成 ppqpqrpqrsqqrqrsrrss。在位置 6 处，字符为 'p'。（索引从 0 开始）。
为了解决这个问题，我们将遵循以下步骤：
- stk_list := 一个新的列表，其中包含一个元组，该元组包含一个空字符串和 input_str 中所有字符的列表
- 当 stk_list 不为空时，执行以下操作
- pre := 从 stk_list 中删除最后一个元素
- temp := 从 stk_list 中删除最后一个元素
- 如果 k < pre 的大小，则
- 返回 pre[k]
- k := k - pre 的大小
- input_sorted := 一个新的列表，其中包含元组，这些元组包含 input_str 的字符及其在 input_str 中的位置
- 根据元组的第二个值按降序对列表 input_sorted 进行排序
- i := 0
- 当 i < input_sorted 的大小时，执行以下操作
- val := input_sorted[i, 0]
- temp1 := [input_sorted[i, 1]]
- j := i + 1
- 当 j < input_sorted 的大小且 input_sorted[j, 0] 与 val 相同时，执行以下操作
- 将 input_sorted[j, 1] 插入到 temp1 的末尾
- j := j + 1
- 将 (pre+val, temp1) 插入到 stk_list 的末尾
- i := j
- 返回 null
示例
让我们看看以下实现以获得更好的理解：
def solve(input_str, k):
stk_list = [("",list(range(len(input_str))))]
while stk_list:
pre, temp = stk_list.pop()
if k < len(pre):
return pre[k]
k -= len(pre)
input_sorted = sorted([(input_str[i],i+1) for i in temp if i < len(input_str)], reverse=True)
i = 0
while i < len(input_sorted):
val = input_sorted[i][0]
temp1 = [input_sorted[i][1]]
j = i + 1
while j < len(input_sorted) and input_sorted[j][0]== val:
temp1.append(input_sorted[j][1])
j += 1
stk_list.append((pre+val, temp1))
i = j
return None
print(solve('pqrs', 6))输入
'pqrs', 6
输出
p
更新于: 2021年10月11日
86 次浏览
广告