python题目及答案对程序解释并做出答案基础python题目搜索软件
下载地址 https://share.weiyun.com/OvviwGnZ
资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题）
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题，涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全（附答案解析）
老男孩Python全栈7期练习题（面试真题模拟）
尚观python第一阶段考试（面试真题模拟）
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践（慕课版）郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)
举例 不同的子序列(超出时间限制)
题目要求
给定一个字符串S和一个字符串T，计算S的子序列中T出现的次数。
一个串的子串是指该串的一个连续的局部，如果不要求连续,则可称为它的子序列。例如abcde, acd就是abcde的一个子序列
假设 S = "rabbbit", T = "rabbit"，那么有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
思路分析
当分析问题遇到阻碍，我最喜欢从问题的边界处入手，因为边界的地方正是条件达到极值的时候，这时候，很容易就找出破绽。
T的首字母是r， 这个r恰好也是S的首字母，如果让S = "abbbitr" ，让r成为S的末尾字符，问题似乎一下子变得明朗起来，此时，S的任意子序列都不可能是“rabbit“， 因为S中r字符后的后面没有内容了，根本找不到”abbit“，顺着这个思路想下去，想从S的子序列中找到T，就必须满足S中，r的后面可以找到a，a的后面可以找到b，b的后面可以再找到一个b，b的后面可以找打一个i,i的后面可以找到t。
但这样找还是挺麻烦的，为何不把T中每个字符出现在S中的位置记录下来呢？r出现在0的位置上，b出现在2, 3, 4的位置上，用一个字典来保存T中字符在S中出现位置的信息：
{
'a': [
1
],
'i': [
5
],
'r': [
0
],
'b': [
2,
3,
4
],
't': [
6
]
}
T = "rabbit"，上面已经得到每一个字符在S中的位置，i从0到5,根据字符的位置信息挑选T[i]在S中的的合适位置，比如r，它出现的位置信息是[0],只能挑选一个位置，但是b 的位置信息是[2, 3, 4] ,有三个位置可以挑选，需要注意的是，如果T[i]这个字符挑选了位置index，那么T[i+1]这个字符在挑选位置时就不能选小于等于index。假如S=”brabbbit“, 那么在选b的位置的时候，就不能要0这个位置，因为T中a在b的前面，a已经选了2这个位置，b选到0毫无意义，这样不能构成子序列。
分析到这里，就演变成了一个寻找排列组合的问题。
示例代码
# coding=utf-8
def num_sequence(source, target):
# 先得到target的每一个字符在source中出现的位置信息
index_dict = {}
for sub_item in target:
index_dict[sub_item] = []
for index, item in enumerate(source):
if sub_item == item:
index_dict[sub_item].append(index)
print(index_dict)
index_seq = get_num_sequence(target, 0, index_dict, -1)
print(index_seq)
def get_num_sequence(target, t_index, index_dict, s_index):
"""
:param target: 目标字符串
:param t_index: 目标字符在target中的位置
:param index_dict: 目标字符串中每个字符在source中的位置
:param s_index: 上一个目标字符在S中的位置
:return:
"""
item = target[t_index]
# 如果目标字符在S中不存在
if item not in index_dict:
return []
# 得到item在S中的位置信息
index_lst = index_dict[item]
seq_lst = []
for index in index_lst:
# 如果位置比上一个目标字符所选的位置靠前或相等,就不能选
if index <= s_index:
continue
# 如果目标字符已经是最后一个字符了
if t_index == len(target) - 1:
seq_lst.append([index])
else:
# 递归调用,寻找下一个目标字符可能的位置
num_seq = get_num_sequence(target, t_index+1, index_dict, index)
for lst in num_seq:
lst.insert(0, index)
seq_lst.append(lst)
return seq_lst
if __name__ == '__main__':
source = "aabdbaabeeadcbbdedacbbeecbabebaeeecaeabaedadcbdbcdaabebdadbbaeabdadeaabbabbecebbebcaddaacccebeaeedababedeacdeaaaeeaecbe"
target = "bddabdcae"
num_sequence(source, target)
|