有账号和密码怎么进公司网站后台,vs2012 网站开发,免费自己制作网站方法,网络营销与直播电商好就业吗1.题目
问题描述
小C手中有一个由小写字母组成的字符串 s。她希望构造另一个字符串 t#xff0c;并且这个字符串需要满足以下几个条件#xff1a;
t 由小写字母组成#xff0c;且长度与 s 相同。t 是回文字符串#xff0c;即从左到右与从右到左读取相同。t 的字典序要小…1.题目
问题描述
小C手中有一个由小写字母组成的字符串 s。她希望构造另一个字符串 t并且这个字符串需要满足以下几个条件
t 由小写字母组成且长度与 s 相同。t 是回文字符串即从左到右与从右到左读取相同。t 的字典序要小于 s并且在所有符合条件的字符串中字典序尽可能大。
小C想知道是否能构造出这样的字符串 t输出这样的t。如果无法构造满足条件的字符串则输出 -1。 测试样例
样例1 输入s abc 输出aba 样例2 输入s cba 输出cac 样例3 输入s aaa 输出-1 2.思路
构造回文字符串 首先我们需要构造一个字典序最大的回文字符串 t。回文字符串的特点是从左到右和从右到左相同。因此我们可以通过复制字符串的一半来构造回文字符串保证回文性质。 判断构造的回文是否满足条件 构造的回文字符串 t 字典序应该小于原始字符串 s如果满足这个条件就可以直接返回 t。 调整字典序 如果通过构造回文字符串得到的 t 字典序不满足 t s则需要从回文的中间位置开始尝试逐步减小字典序。从回文的中心开始向左逐步调整字符使得它们比原本的字符小从而保证字典序尽可能大但依然小于 s。 返回结果 如果能够找到符合条件的回文字符串 t则返回它如果无法调整使得字典序小于 s则返回 1。
3.代码
def solution(s: str) - str:# 将输入字符串转为列表方便操作s list(s)n len(s)# 定义一个函数用于将字符串调整为回文字符串def build(t):s t.copy() # 复制 t避免修改原始列表l, r 0, n - 1 # 定义双指针左指针从0开始右指针从n-1开始# 使用双指针构造回文while l r:s[r] s[l] # 将左侧字符赋值给右侧l 1r - 1return s# 尝试直接将 s 构造成回文字符串t build(s)if t s: # 如果构造的回文字符串字典序小于原字符串ans telse:# 如果直接构造的回文不满足字典序小于 s 的条件# 从回文中心开始尝试减小字典序i (n - 1) 1 # 确定中间位置向左遍历while i 0:if s[i] a: # 如果当前字符为 as[i] z # 将其变为 zelse:s[i] chr(ord(s[i]) - 1) # 将当前字符减小一个字母break # 减小成功后退出循环i - 1 # 向左移动指针if i -1: # 如果遍历完成仍无法减小字典序ans [-1] # 无法构造符合条件的字符串else:# 成功减小字典序后重新构造回文ans build(s)return .join(ans) # 返回最终结果将列表转为字符串# 测试用例
if __name__ __main__:# 测试样例1输入 abc期望输出 abaprint(solution(s abc) aba) # 输出 True 表示通过测试# 测试样例2输入 cba期望输出 cacprint(solution(s cba) cac) # 输出 True 表示通过测试# 测试样例3输入 aaa期望输出 -1print(solution(s aaa) -1) # 输出 True 表示通过测试
i (n - 1) 1
在代码中i (n - 1) 1 是一种计算字符串中间位置的常见方式其中
解释 位运算 1 表示右移一位即将一个数除以 2向下取整。 例如 5125 1 2512 整数除法结果。4124 1 2412。 表达式含义(n - 1) 1 计算了字符串 sss 的中心位置的索引 n−1n - 1n−1字符串的最大索引位置。右移一位相当于除以 2得到中心索引位置。这是一个向左偏的中心索引适用于在字符串中以双指针的方式从中心向两边遍历。
为什么’a’要变成’z’ 如果字符已经是 a你不能再减小它因为 a 是字母表中的最小字符。这将意味着要将前一位字母减小一位为了保证t在所有符合条件的字符串中字典序尽可能大所以将’a要变成’z
