当前位置: 首页 > news >正文

37.构造回文字符串问题|Marscode AI刷题

1.题目

问题描述

小C手中有一个由小写字母组成的字符串 s。她希望构造另一个字符串 t,并且这个字符串需要满足以下几个条件:

  1. t 由小写字母组成,且长度与 s 相同。
  2. t 是回文字符串,即从左到右与从右到左读取相同。
  3. 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':  # 如果当前字符为 'a's[i] = 'z'  # 将其变为 'z'else: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",期望输出 "aba"print(solution(s = "abc") == 'aba')  # 输出 True 表示通过测试# 测试样例2,输入 "cba",期望输出 "cac"print(solution(s = "cba") == 'cac')  # 输出 True 表示通过测试# 测试样例3,输入 "aaa",期望输出 "-1"print(solution(s = "aaa") == '-1')  # 输出 True 表示通过测试
  • i = (n - 1) >> 1

在代码中,i = (n - 1) >> 1 是一种计算字符串中间位置的常见方式,其中:

解释

  1. 位运算>> 1 表示右移一位,即将一个数除以 2,向下取整。

    例如:

    • 5>>1=25 >> 1 = 25>>1=2 (整数除法结果)。
    • 4>>1=24 >> 1 = 24>>1=2。
  2. 表达式含义(n - 1) >> 1 计算了字符串 sss 的中心位置的索引

    • n−1n - 1n−1:字符串的最大索引位置。
    • 右移一位相当于除以 2,得到中心索引位置。
    • 这是一个向左偏的中心索引,适用于在字符串中以双指针的方式从中心向两边遍历。
  • 为什么’a’要变成’z’? 如果字符已经是 'a',你不能再减小它,因为 'a' 是字母表中的最小字符。这将意味着要将前一位字母减小一位,为了保证t在所有符合条件的字符串中字典序尽可能大,所以将’a'要变成’z'

http://www.lryc.cn/news/524452.html

相关文章:

  • ssm-mybatisPlus学习笔记
  • 【算法学习笔记】35:扩展欧几里得算法求解线性同余方程
  • 线性规划:机器学习中的优化利器
  • Ubuntu开发中的问题
  • MAC 地址转换为标准大写格式
  • 使用插件SlideVerify实现滑块验证
  • 深入探索 Nginx 的高级用法:解锁 Web 服务器的强大潜能
  • (01)搭建开发环境
  • Win11桌面右键刷新选项在二级界面的修正方法
  • 配电室防静电地板通常用哪种
  • 【重庆市乡镇界】面图层shp格式arcgis数据乡镇名称和编码wgs84坐标无偏移内容测评
  • 68,[8] BUUCTF WEB [RoarCTF 2019]Simple Upload(未写完)
  • Windows电脑桌面记录日程安排的提醒软件
  • TiDB与Oracle:数据库之争,谁能更胜一筹?
  • USART_串口通讯中断案例(HAL库实现)
  • 【MySQL】存储引擎有哪些?区别是什么?
  • [OpenGL]实现屏幕空间环境光遮蔽(Screen-Space Ambient Occlusion, SSAO)
  • linux-NFS网络共享存储服务配置
  • w-form-select.vue(自定义下拉框组件)
  • ovs实现lb负载均衡
  • 机器学习-核函数(Kernel Function)
  • 计算最接近的数
  • 【QNX】QNX侧查看内存信息的方法
  • 逐笔成交逐笔委托Level2高频数据下载和分析:20250121
  • AutoSar架构学习笔记
  • 2024年智慧消防一体化安全管控年度回顾与2025年预测
  • 基于单片机的智能台灯设计
  • HJ108 求最小公倍数(Java版本)
  • 使用tritonserver完成clip-vit-large-patch14图像特征提取模型的工程化。
  • 实操演练第003讲-数据通途:客户端连接SQL Server的完美攻略