欢迎交流学习~~
专栏： 蓝桥杯Python组刷题日寄
蓝桥杯进阶系列：
🏆 Python | 蓝桥杯进阶第一卷——字符串
🔎 Python | 蓝桥杯进阶第二卷——贪心
💝 Python | 蓝桥杯进阶第三卷——动态规划
✈️ Python | 蓝桥杯进阶第四卷——图论
🌞 Python | 蓝桥杯进阶第五卷——数论
💎 Python | 蓝桥杯进阶第六卷——搜索
🎁 字符串的修改
时间限制：
1s
内存限制：
128MB
题目描述：
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
对任给的两个字符串 A 和 B，计算出将字符串 A 变换为字符串 B 所用的最少字符操作次数。
输入描述：
第一行为字符串 A；第二行为字符串 B；字符串 A 和 B 的长度均小于 200。
输出描述：
只有一个正整数，为最少字符操作次数。
样例输入：
sfdxbqw
gfdgw
样例输出：
4
解题思路
本题思路如下：
- 求解两字符串的最长公共子序列，得到其长度
L； - 计算最少字符操作次数
本题思路的核心在于 求解两个字符串的最长公共子序列。
可以选择用循环暴力求解，但是时间复杂度过高，容易超时。因此我们这里可以选用时间复杂度更低的动态规划方法：
dp[i][j]表示a[:i-1]和b[:j-1]的最长公共子序列的长度i>0, j>0，对应dp数组的大小为dp[l1+1][l2+1]，l1和l2为两个字符串的长度；i=0或j=0表示空字符串，此时公共子序列长度都为0，因此我们将dp数组都初始化为0；- 状态转移具体见代码。
而对于计算最终结果，其计算方式为：max(l1, l2) - L。
因为，如果想将较长的字符串变为较短的字符串，除了最长公共子序列，其余字符都需要变化。
参考代码
a = input()
b = input()
l1 = len(a)
l2 = len(b)
# dp数组,
# dp[i][j]表示a[:i-1]和b[:j-1]中最长公共子序列的长度(i>0, j>0)
# i=0 和 j=0 表示空字符串，初始化dp数组为全0
dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]
for i in range(1, l1+1):
for j in range(1, l2+1):
if a[i-1] == b[j-1]:
# a的第i-1个字符和b的第j-1个字符相同
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
res = max(l1, l2) - dp[-1][-1]
print(res)
🌲 ISBN码
题目：
时间限制：
1s
内存限制：
128MB
题目描述：
每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括 9 位数字、1 位识别码和 3 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4 就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 670 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以 1 加上次位数字乘以 2……以此类推，用所得的结果 mod 11，所得的余数即为识别码，如果余数为 10，则识别码为大写字母 X。例如ISBN号码 0-670-82162-4 中的识别码 4 是这样得到的：对 067082162 这 9 个数字，从左至右，分别乘以1，2，...,9 ,再求和，即 0×1+6×2+……+2×9=158，然后取158 mod 11的结果 4 作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出你认为是正确的ISBN号码。
输入描述：
输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。
输出描述：
输出共一行，假如输入的ISBN号码的识别码正确，那么输出 Right ，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符 -）。
样例输入：
0-670-82162-4
0-670-82162-0
样例输出：
Right
0-670-82162-4
解题思路
本题思路比较简单，注意细节的处理：
- 字符串以
-分割； - 当计算出的识别码为
10时，将其转换为X；
参考代码
while True:
try:
raw = input()
s = ''.join(raw.split('-'))
id = 0
for i in range(len(s)-1):
id += int(s[i]) * (i + 1)
id %= 11
id = str(id)
if id == '10':
id = 'X'
if id == s[-1]:
print('Right')
else:
print(raw[:-1] + id)
except:
break
🚀 完美的代价
时间限制：
1s
内存限制：
128MB
题目描述：
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如：对于 mamad：
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入描述：
第一行是一个整数 N，表示接下来的字符串的长度(N < = 8000)
第二行是一个字符串，长度为 N，只包含小写字母
输出描述：
如果可能，输出最少的交换次数。
否则输出 Impossible
样例输入：
5
mamad
样例输出：
3
解题思路
本题利用双指针，其中头指针 head 从前向后遍历，尾指针 tail 从后向前遍历。
退出循环的条件：
- 字符串长度为偶数，但是有频数为奇数的字母
- 字符串长度为奇数，但是有多于
1个的频数为奇数的字母
具体思路见参考代码。
参考代码
n = int(input())
s = list(input())
count = 0 # 记录交换次数
flag = 0 # 标记是否有字母频数为奇数
res = True # 标记是否为Impossible(是Impossible置为False)
# 双指针
L = n - 1 # 头指针搜索范围，到倒数第2个
for head in range(L):
# 对于每一个s[head]，用尾指针去搜索是否有相同的字母s[tail]
for tail in range(L, head - 1, -1):
# 指针tail搜索完毕，没有发现s[head] == s[tail]
# 说明该字母频数为奇数 1，且该字母在回文序列中一定在中间
if head == tail:
# 如果字符串长度为偶数
# 字符串长度为奇数，但是已经有 flag == 1
if n%2 == 0 or flag == 1:
res = False
break
flag = 1
# (n//2 - head) 为将该字母移动到中间位置的交换次数
count += n//2 - head
# 发现了 s[head] == s[tail]
elif s[head] == s[tail]:
# 交换位置
for i in range(tail, L):
s[i], s[i+1] = s[i+1], s[i]
count += 1
L -= 1
break
# 如果是impossible，退出外层循环
if res == False:
break
if res == False:
print('Impossible')
else:
print(count)
💡 字符串的展开
时间限制：
1s
内存限制：
128MB
题目描述：
在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于 d-h 或者 4-8 的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为 defgh 和 45678。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
- 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号
-，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。 - 参数
p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号*来填充。 - 参数
p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串d-h应扩展为deeefffgggh。减号两边的字符不变。 - 参数
p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串d-h应扩展为dggffeeh。 - 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：
d-e应输出为de，3-4应输出为34。如果减号右边的字符按照 ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：d-d应输出为d-d，3-1应输出为3-1。
输入描述：
输入包括两行：
第 1 行为用空格隔开的 3 个正整数，一次表示参数 p1，p2，p3。
第 2 行为一行字符串，仅由数字、小写字母和减号 - 组成。行首和行末均无空格。
数据规模和约定
100%的数据满足：1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串长度不超过 100
输出描述：
输出只有一行，为展开后的字符串.
样例输入：
1 2 1
abcs-w1234-9s-4zz
样例输出：
abcsttuuvvw1234556677889s-4zz
解题思路
- 符号
-只会在s[1:len(s)-1]之间（s为输入字符串），因此要在这个范围内遍历，找到符号-并将其展开； - 满足展开的条件，即要判断左右两边的字符的ASCII码关系；
- 之后根据
p3->p1->p2的判断顺序对展开字符进行修改。
具体见代码。
参考代码
p1, p2, p3 = map(int, input().split())
s = input()
res = s[0]
# '-' 只会在s[1:len(s)-1]中间，因此s的首尾不需要变化
for i in range(1, len(s)-1):
left, mid, right = s[i-1], s[i], s[i+1]
# 遇到 '-' 并且左右字符满足如下条件：
# 条件1：left<right
# 条件2：(left>='0' and right<='9') or (left>='a' and right<='z')
if mid == '-' and left < right and ((left >= '0' and right <= '9') or (left >= 'a' and right <= 'z')):
## 判断顺序：p3 -> p1 -> p2
## p3
if p3 == 1:
# 顺序
index_j = [j for j in range(ord(left)+1, ord(right))]
else:
# 逆序
index_j = [j for j in range(ord(right)-1, ord(left), -1)]
## p1
for j in index_j:
# chr()转为字符
tmp = chr(j)
if p1 == 2:
# 变为大写
tmp = tmp.upper()
elif p1 == 3:
# 变为 '*'
tmp = '*'
## p2
# 重复 p2 次
res += tmp * p2
else:
res += mid
# 尾巴
res += s[-1]
print(res)
🍞 正则问题
时间限制：
1s
内存限制：
128MB
题目描述：
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如：((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是 6。
输入描述：
一个由 x()| 组成的正则表达式。输入长度不超过 100，保证合法。
输出描述：
这个正则表达式能接受的最长字符串的长度。
样例输入：
((xx|xxx)x|(x|xx))xx
样例输出：
6
解题思路
该问题是利用 深度优先遍历 的思想，具体实现见下面的参考代码。
这里我们以样例逐步说明算法原理，将参考代码进行简单修改，可以帮助我们理解在哪一层搜索：
# 测试代码
s = '((xx|xxx)x|(x|xx))xx'
i = 0
floor = 0
def dfs():
global i, floor
print(f'此时: i = {i}')
floor += 1
print(f'进入一层，此时的层数为 {floor}')
res = 0
while i < len(s):
# 遇到 '('，递归调用函数，对接下的 'x' 计数
if s[i] == '(':
i += 1
res += dfs()
i += 1
print(f'此时: i = {i}')
# 遇到 ')'，返回计数结果
elif s[i] == ')':
floor -= 1
print(f'退出一层，此时的层数为 {floor}')
return res
# 遇到 'x'，计数+1，索引后移
elif s[i] == 'x':
i += 1
print(f'此时: i = {i}')
res += 1
# 遇到 '|'，返回左右两边的较大值
elif s[i] == '|':
i += 1
res = max(res, dfs())
return res
dfs()
输出结果：
此时: i = 0
进入一层，此时的层数为 1
此时: i = 1
进入一层，此时的层数为 2
此时: i = 2
进入一层，此时的层数为 3
此时: i = 3
此时: i = 4
此时: i = 5
进入一层，此时的层数为 4
此时: i = 6
此时: i = 7
此时: i = 8
退出一层，此时的层数为 3
退出一层，此时的层数为 2
此时: i = 9
此时: i = 10
此时: i = 11
进入一层，此时的层数为 3
此时: i = 12
进入一层，此时的层数为 4
此时: i = 13
此时: i = 14
进入一层，此时的层数为 5
此时: i = 15
此时: i = 16
退出一层，此时的层数为 4
退出一层，此时的层数为 3
此时: i = 17
退出一层，此时的层数为 2
退出一层，此时的层数为 1
此时: i = 18
此时: i = 19
此时: i = 20
参考代码
s = list(input().strip())
i = 0
def dfs():
global i
res = 0
while i < len(s):
# 遇到 '('，递归调用函数，对接下的 'x' 计数
if s[i] == '(':
i += 1
res += dfs()
i += 1
# 遇到 ')'，返回计数结果
elif s[i] == ')':
return res
# 遇到 'x'，计数+1，索引后移
elif s[i] == 'x':
i += 1
res += 1
# 遇到 '|'，返回左右两边的较大值
elif s[i] == '|':
i += 1
res = max(res, dfs())
return res
print(dfs())
文章出处登录后可见！
