大厂测试python笔试题最全的网站python笔试题库代码题100题
下载地址 https://share.weiyun.com/gcOeOitM
资料目录
100道Python面试题
5个等待挑战的Python面试题（附答案）
python基础面试题三十一道（附详细答案）
python面试基础题十大陷阱（附详细答案）
python面试真实笔试题带答案（1-10题）
Python面试中必看的8个必考问题（附详细答案）
Python爬虫开发面试常见问题（附详细答案）
Python爬虫面试题（附详细答案）
python数据分析师面试题选（附详细答案）
Python数据挖掘试题四十道（附答案）
阿里巴巴Python开发工程师面试题（附答案）
常见的25个python面试问答（附详细答案）
Python经典面试题和答案解析
四类必须提前准备的Python程序员面试问题
出现频率最高的python面试题集锦（附详细答案）
珍藏版Python web后端开发工程师面试试题
尚观python第一阶段考试（面试真题模拟）
老男孩Python全栈7期练习题（面试真题模拟）
傲梦python笔试题及答案
python 笔试题（附带答案）
Python题库(已收录100道真题）
python第一阶段考试题
python基础试题(含答案)
PYTHON测试题和答案
Python考试题复习知识点试卷试题
python期末考试复习试卷
举例 字符串的排列
题目要求
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串
实例1
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba")
实例2
输入: s1= "ab" s2 = "eidboaoo"
输出: False
思路分析
暴力算法
以字符串“abc” 为例，它有6种排列，分别为
• abc
• acb
• bac
• bca
• cab
• cba
你可以写一个算法，找出一个字符串的所有排列，然后利用字符串的find函数，在第二个字符串中逐个查找是否存在这些排列。
上面的思路虽然笨重，但可以解决问题。
更优的解法
让我们把思路从字符串排列上移开，假如有一个字符串包含了字符串“abc”的6个人排列中的某一个，那么可以肯定的讲，在这个字符串里，一定有一个长度为3的子串，这个子串包含了a,b,c这三个字符。
至于顺序，则完全不用考虑，只要这个长度为3的子串包含了a,b,c这三个字符，那么这个子串就一定是字符串“abc”的某个排列。
算法思路如下
1. 统计第一个字符串的字符信息，存放于字典中，记录每个字符的数量
2. 遍历第二个字符串，同样统计每个字符的数量，然后和第一步中的字符信息进行比较，其实就是两个字典的比较。这里有一个需要注意的地方，遍历过程中，只能统计子串的信息，而不是从头到尾的去做统计，如果第一个字符串的长度是3，那么当第二个字符串遍历到索引5时，只能统计索引3到5这个范围内的信息
如果两个字典完全相同，就说明第二个字符串的这段子串是第一个字符串的一个排列
实例代码
def check_inclusion(s1, s2):
s1_chr_info = {}
for chr in s1:
s1_chr_info.setdefault(chr, 0)
s1_chr_info[chr] += 1
s2_chr_info = {}
start_index = 0 # 连续空间开始的位置
for index, chr in enumerate(s2):
if chr not in s1_chr_info:
s2_chr_info.clear()
start_index = index+1
continue
# 右侧进
s2_chr_info.setdefault(chr, 0)
s2_chr_info[chr] += 1
# 左侧出
left_index = index - len(s1)
if left_index >= start_index and s2[left_index] in s1_chr_info \
and s2[left_index] in s2_chr_info :
s2_chr_info[s2[left_index]] -= 1
if is_dict_same(s1_chr_info, s2_chr_info):
return True
return False
def is_dict_same(dict_1, dict_2):
"""
dict_1 是第一个字符串的统计信息，以它为基准进行判断
:param dict_1:
:param dict_2:
:return:
"""
if len(dict_1) != len(dict_2):
return False
for k, v in dict_1.items():
if k not in dict_2:
return False
if v != dict_2[k]:
return False
return True
if __name__ == '__main__':
print(check_inclusion("ab", "eidbaooo"))
print(check_inclusion("abcd", "eidbadcooo"))
print(check_inclusion("abcd", "eicwdbardcooo"))
|