主机托管网站,关于网站建设的投标书,做私人小网站赚钱吗,企业网站的价值体现是在博客主页#xff1a;誓则盟约系列专栏#xff1a;IT竞赛 专栏关注博主#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出#xff0c;及时修改感谢大家点赞#x1f44d;收藏⭐评论✍ 2663.字典序最小的美丽字符串【困难】
题目#xff1a;
如果一个字符串满…博客主页誓则盟约系列专栏IT竞赛 专栏关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍ 2663.字典序最小的美丽字符串【困难】
题目
如果一个字符串满足以下条件则称其为 美丽字符串
它由英语小写字母表的前 k 个字母组成。它不包含任何长度为 2 或更长的回文子字符串。
给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
请你找出并返回一个长度为 n 的美丽字符串该字符串还满足在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串则返回一个空字符串。
对于长度相同的两个字符串 a 和 b 如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大则字符串 a 的字典序大于字符串 b 。
例如abcd 的字典序比 abcc 更大因为在不同的第一个位置第四个字符上 d 的字典序大于 c 。 示例 1
输入s abcz, k 26
输出abda
解释字符串 abda 既是美丽字符串又满足字典序大于 abcz 。
可以证明不存在字符串同时满足字典序大于 abcz、美丽字符串、字典序小于 abda 这三个条件。示例 2
输入s dc, k 4
输出
解释可以证明不存在既是美丽字符串又字典序大于 dc 的字符串。 提示
1 n s.length 1054 k 26s 是一个美丽字符串 分析问题 由题意知返回的s中不能存在长度为2或3以及更长的回文串这句话什么意思呢?长度为2的回文串指的就是两个字母一样的字符串那长度为3或者更长的回文串都有一个共同的特点中间必然存在长度为3的一个回文串也就是说存在下标i使得 ls[i]ls[i-2],所以我们判断是否存在回文串只需要判断对于每个下标i是否存在ls[i]ls[i-1] or ls[i]ls[i-2] 即可。 其次我们返回的字符串还要求 字典序比原s的大还得是所有符合题意美丽字符串里面的字典序最小的那个。那么我们就可以从后往前去遍历因为最后的字母对字典序的影响最小最后的字母如果没有找到合适的那么就往前一个字母找到合适的就可以直接返回。否则返回空字符串。
不过要注意题目给的s本身就是一个美丽字符串。 代码实现
class Solution:def smallestBeautifulString(self, s: str, k: int) - str:a ord(a)k as list(map(ord, s))n len(s)i n - 1s[i] 1 # 从最后一个字母开始while i n:if s[i] k: # 超过范围if i 0: return # 无法进位# 进位s[i] ai - 1s[i] 1elif i and s[i] s[i - 1] or i 1 and s[i] s[i - 2]:s[i] 1 # 如果 s[i] 和前面的字符形成回文串就继续增加 s[i]else:i 1 # 检查 s[i] 是否和后面的字符形成回文串return .join(map(chr, s)) 总结
代码详解 a ord(a) 和 k a 获取字符 a 的 ASCII 值并对 k 进行相应调整。s list(map(ord, s)) 将输入字符串 s 中的字符转换为对应的 ASCII 值以便进行数值操作。从字符串末尾 i n - 1 开始将当前位置的字符值 s[i] 增加 1。如果 s[i] 超过给定范围等于 k 且无法进位i 0则返回空字符串否则进位将当前位置重置为 aASCII 值为 a并向前一位 i - 1 进行处理。如果 s[i] 与前一个字符 s[i - 1] 相同或者与前两个字符 s[i - 2] 相同形成回文串则继续增加 s[i] 的值。如果没有形成回文串则向后移动位置 i 1 继续检查。最后将处理后的 ASCII 值列表转换回字符并连接成字符串返回。 考点 对 ASCII 值的理解和操作。字符串的遍历和修改。回文串的判断和处理。边界情况的考虑如进位和无法得到结果的情况。 反思 代码的逻辑较为复杂需要仔细考虑各种边界情况和特殊情况在编写时容易出错。对于回文串的判断和处理可以思考是否有更简洁或高效的方式。在处理进位和字符范围时要确保逻辑的严密性避免出现错误结果。 收获 学会了如何通过 ASCII 值来操作字符灵活处理字符串中的字符变化。深入理解了字符串遍历和修改的方法以及如何根据特定条件进行调整。提升了对复杂逻辑的分析和处理能力特别是在涉及边界情况和多种条件判断时。意识到在处理类似问题时需要全面考虑各种可能的情况进行充分的测试以确保代码的正确性。 “自身拥有越丰富他在别人身上所能发现得到的就越少。” ——《人类的智慧》
